Les arbres en informatique

Sommaire du document

Dans notre drôle de monde informatique, les arbres poussent à l'envers. En effet, nous considérons que la racine de l'arbre se trouve généralement en haut. Nous jouons au jardinier fou en modifiant la forme de l'arbre ou en déplaçant tous ses fruits. Nous passons notre temps à peinturlurer en rouge ou en noir les endroits où les branches prennent naissance, et comme des singes acrobates nous passons notre temps à essayer de parcourir l'arbre de différentes manières.

Définition d'un arbre

Un arbre est une structure de données. Comme pour un arbre naturel, nous distionguons un certain nombre d'éléments constituants :

• nœud : le nœud est le point de départ d'une ou de plusieurs branches. Nous pouvons utiliser la terminologie de la généalogie pour désigner les relations qu'il existe entre les nœuds : le parent, le grand-parent, les enfants, le fils, le frère (nœud de même niveau et de même parent), l'oncle (le frère du parent), le cousin (nœud de même niveau mais de parent différent), etc.
• racine : la racine est un nœud particulier car il ne possède pas de nœud parent.
• feuille : une feuille est un nœud particulier car il ne possède pas d'enfant.

Selon la théorie des graphes, un arbre est un graphe (généralement non orienté car nous n'avons pas de pointeur vers le parent) qui possède uneseule racine (sommet de degré nul)^[1], et n'admet pas de cycle.

En plus de ces termes, nous aurons à utiliser différentes notions relatives aux arbres :

• arête : si nous considérons l'arbre comme un graphe non orienté, nous préférerons employer le terme arête à la place de branche pour désigner le segment de droite qui relie deux nœuds.
• profondeur d'un nœud : c'est la distance d'un nœud par rapport à la racine (la racine + le nombre de nœuds entre la racine et le nœud + le nœud lui même).
• hauteur de l'arbre : c'est la profondeur de la feuille la plus basse, ou encore la plus grande profondeur parmi toutes les feuilles.
• taille de l'arbre : c'est le nombre total de nœuds présents dans l'arbre. Selon les cas, nous pouvons préciser qu'il s'agit d'une taille de l'arbre sans la racine ou sans les feuilles.

Jusqu'à présent, nous ne nous sommes préoccupés que de la structure de l'arbre, mais il est intéressant de pouvoir y placer certaines informations (il est temps que l'arbre porte ses fruits). Nous pouvons utiliser chaque nœud pour y placer de l'information. Si ces informations possèdent une manière de les comparer, la structure de l'arbre se prête assez bien à ce genre de besoin, comme nous le verrons plus tard.

Comme l'informatique est par essence dichotomique car basée sur la dualité 0-1 du binaire, nous pouvons nous pencher sur certains arbres particulier, les arbres binaires, car ils sont les plus faciles à implémenter. Nous ne devons cependant pas oublier que la définition même de la structure en arbre admet plus de deux enfants pour chaque nœud, et nous serons amenésà utiliser aussi ce genre d'arbre.

Structure générale d'un arbre binaire

Afin de répondre aux différents besoins, nous avons besoin de trois éléments :

• un moyen d'atteindre le fils de gauche
• la donnée utile, ou un moyen d'atteindre cette donnée
• un moyen d'atteindre le fils de droite

Parcourir un arbre binaire

Pour chaque nœud (y compris la racine), trois possibilités s'offrent à nous :

• Nous nous dirigeons vers la branche de gauche si elle existe (G).
• Nous nous dirigeons vers la branche de droite si elle existe (D).
• Nous traitons la valeur courante (T).

Nous pouvons combiner ces actions de différentes manières, et nous devons considérer la position du traitement de la valeur courante (T).
Ce traitement peut se faire à trois moments :

• Avant toute décision de direction (ex: TGD). Nous parlerons de traitement préfixe.
• Après la première décision (ex: GTD). Nous parlerons de traitement infixe.
• Après toute décision de direction (ex: GDT). Nous parlerons de traitement postfixe.

Notes

1. ↑ Racine : Certaines définitions de l'arbre au sens informatique différencient les arbres les arbres enracinés (qui possèdent une racine) des arbres non enracinés (qui ne possèdent pas de racine). Sans rentrer dans le débat de l'utilité d'un arbre non enraciné et de la pertinence de sa définition, je n'utiliserais le terme arbre que pour désigner des arbres enracinés.
   
   

Références

1. Graphes et arbres : lien interne, Les arbres vus au travers des graphes.
2. Red/Black Tree Demonstration : John Franco, Applet Java (version 08/01/10)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Liste des images

1. Arbre informatique _{(Référence : infobrol)}

Structure du document