Revue de presse Arbre_%28informatique%29
Arbre (informatique)
Un article de Wikipédia, l'encyclopédie libre.
Sommaire |
[] Généralités
En informatique, un arbre est une structure de données récursive générale, représentant un arbre au sens mathématique. C'est un cas particulier de graphe qui n'a qu'une seule source et aucun cycle.
Dans un arbre, on distingue deux catégories d'éléments :
- les feuilles, éléments ne possédant pas de fils dans l'arbre ;
- les n?uds internes, éléments possédant des fils (sous-branches).
La racine de l'arbre est le n?ud ne possédant pas de parent.
La hauteur d'un arbre est la longueur du plus grand chemin de la racine à une feuille.
Chaque n?ud possède une étiquette, qui est en quelque sorte le « contenu » de l'arbre. L'étiquette peut être très simple: un nombre entier, par exemple. Elle peut également être aussi complexe que l'on veut : un objet, une instance d'une structure de données, un pointeur, etc. Il est presque toujours obligatoire de pouvoir comparer les étiquettes selon une relation d'ordre total, afin d'implanter les algorithmes sur les arbres.
Par exemple, les dossiers de Windows 98 et MS-DOS forment un arbre.
Les arbres sont en fait rarement utilisés en tant que tels, mais de nombreux types d'arbres avec une structure plus restrictive existent et sont couramment utilisés en algorithmique, notamment pour gérer des bases de données, ou pour l'indexation de fichiers. Ils permettent alors des recherches rapides et efficaces. Nous vous en donnons ici les principaux exemples :
- Les arbres binaires dont chaque n?ud a au plus deux fils : ils sont en fait utilisés sous forme d'arbres binaires de recherche, de tas, d'AVL, ou encore d'arbres rouge-noir. Les deux derniers exemples sont des cas particuliers d'arbres équilibrés, c'est-à-dire d'arbres dont les sous-branches ont environ la même hauteur.
- Les arbres n-aires qui sont une généralisation des arbres binaires : chaque n?ud a au plus n fils. Les arbres 2-3-4 et les arbres B en sont des exemples d'utilisation et sont eux aussi des arbres balancés.
[] Construction
Pour construire un arbre à partir de cases ne contenant que des informations, on peut procéder de l'une des trois façons suivantes :
- Créer une structure de données composée de :
- l'étiquette (la valeur contenue dans le n?ud),
- un lien vers chaque n?ud fils,
- un arbre particulier, l'arbre vide, qui permettra de caractériser les feuilles. Une feuille a pour fils des arbres vides uniquement.
- Créer une structure de données composée de :
- l'étiquette (la valeur contenue dans le n?ud),
- un lien vers le « premier » n?ud fils (n?ud fils gauche le cas échéant),
- un autre lien vers le n?ud frère (le « premier » n?ud frère sur la droite le cas échéant).
- Créer une structure de données composée de :
- l'étiquette (la valeur contenue dans le n?ud),
- un lien vers le n?ud père.
On note qu'il existe d'autres types de représentation propres à des cas particuliers d'arbres. Par exemple, le tas est représenté par un tableau d'étiquettes.
[] Parcours
[] Parcours en largeur
Le parcours en largeur correspond à un parcours par niveau de n?uds de l'arbre. Un niveau est un ensemble de n?uds internes ou[1] de feuilles situés à la même « distance »[2] du n?ud racine ? on parle aussi de n?ud ou de feuille de même hauteur dans l'arbre considéré. L'ordre de parcours d'un niveau donné est habituellement conféré, de manière récursive, par l'ordre de parcours des n?uds parents ? n?uds du niveau immédiatement supérieur.
Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, C, D, E, F puis G.
- ? Le « ou » est large : un niveau peut recouvrir à la fois des n?uds et des feuilles ; en effet, toutes les feuilles d'un arbre ne sont pas nécessairement situées à la même « distance » du n?ud racine.
- ? La notion de distance est relative dans ce contexte : elle correspond usuellement au nombre d'arcs ? ou d'arêtes ? composant le plus court chemin depuis le n?ud racine jusqu'au n?ud considéré, interne ou feuille. En théorie, elle peut être plus élaborée. Un arbre étant un graphe particulier, ses arcs ou arêtes peuvent être pondérés. Cette pondération peut servir à l'évaluation d'une mesure entre deux n?uds quelconques de l'arbre. On parle de longueur du (plus court) chemin entre deux n?uds d'un arbre, la longueur étant distincte de la différence des hauteurs respectives.
[] Parcours en profondeur
Le parcours en profondeur est un parcours récursif sur un arbre. Il existe trois ordres pour cette méthode de parcours.
[] Parcours en profondeur préfixé
Dans ce mode de parcours, le n?ud courant est traité avant le traitement des n?uds gauches et droits. Ainsi, si l'arbre précédent est utilisé, le parcours sera A, B, D, E, C, F puis G.
[] Parcours en profondeur infixé
Dans ce mode de parcours, le n?ud courant est traité entre le traitement des n?uds gauches et droits. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, B, E, A, F, C puis G.
[] Parcours en profondeur suffixé
Dans ce mode de parcours, le n?ud courant est traité après le traitement des n?uds gauches et droits. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C puis A. Ce mode de parcours correspond à une notation polonaise inversée.
[] Exemples d'arbres
- Les arbres binaires;
- Les arbres B (B-Tree);
- Les arbres équilibrés;
- Les arbres syntaxiques;
- Les tas;
- Les arbres couvrants;
- Les octrees;
- Les Arbres AVL;
- Les Arbres bicolore.
La source est wikipedia http://fr.wikipedia.org/wiki/ Arbre (informatique)
