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)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.
Deutsche Übersetzung
Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.
Vielen Dank im Voraus.
Dokument erstellt 02/11/2009, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/programmer-arbres.html
Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.
- ↑ 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.
Referenzen
Graphes et arbres : lien interne, Les arbres vus au travers des graphes.
-
Red/Black Tree Demonstration : John Franco, Applet Java
(version 08/01/10)
Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.
