Les arbres en informatique

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)¹, 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.

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 02/11/2009 gemaakt, de laatste keer de 26/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/programmer-arbres.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.

Notes

↑ 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.

Inhoudsopgave Haut

Referenties

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut