Arbre (informatique)
Image manquante
Logo_Begriffsklärung.png
Pour les articles homonymes, voir Arbre (homonymie).
| Image manquante Symbole-ordinateur.png | Cet article est une ébauche concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
Généralités
En informatique, un arbre est une structure de données récursive, représentant un arbre au sens mathématique.
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 menant pour chaque étape d'un parent à un enfant.
Chaque noeud 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 ête 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.
Un arbre binaire (plus généralement, n-aire) est un arbre dont chaque nœud possède exactement 2 (resp. n) enfants.
Par exemple, les répertoires sous la plupart des systèmes d'exploitation actuels (Microsoft Windows, Unix dont Linux et Mac OS X...) forment un arbre.
Les arbres interviennent en algorithmique pour la construction de structures de données efficaces. On utilise notamment des arbres binaires équilibrés, c'est-à-dire des arbres binaires dont pour tout nœud, les sous-branches ont environ la même hauteur. De tels arbres permettent, par exemple, de représenter des ensembles ou des fonctions avec un coût d'accès proportionnel au logarithme du nombre d'entrées présentes.
Construction
Pour construire un arbre à partir de cases ne contenant que des informations, on procède généralement ainsi:
- Créer une structure de données composée de l'étiquette (la valeur contenue dans le noeud),
- D'un lien vers chacun des noeud fils
On peut également procéder comme suit :
- Créer une structure de données composée de l'étiquette (la valeur contenue dans le noeud),
- D'un lien vers le noeud fils
- D'un autre lien vers le noeud frère
Une autre manière est de disposer
- D'une structure de données composée de l'étiquette (la valeur contenue dans le noeud),
- D'un lien vers le noeud père
et bien d'autres représentations.
Un arbre est un cas particulier de graphe qui n'a qu'une seule source et aucun cycle.
Exemples d'arbres
- les arbres phylogénétiques
- les arbres binaires
- les arbres balancés