À retenir
- La racine est le sommet de la hiérarchie.
- Chaque élément (nœud) a exactement un seul parent, sauf la racine.
- Les feuilles sont les éléments terminaux qui n'ont pas d'enfants.
Un arbre est une façon d'organiser des données sous forme de hiérarchie, à l'image d'un arbre généalogique ou d'un organigramme. On part d'un point unique appelé la racine, qui se divise en plusieurs branches menant à d'autres éléments, sans que les chemins ne se croisent ou ne forment de boucles.
Étymologie
Du latin arbor. Le terme a été adopté en informatique car la structure visuelle des données, avec ses ramifications partant d'un tronc commun, rappelle celle du végétal. Particularité : en informatique, on dessine souvent l'arbre « à l'envers », avec la racine en haut.
Exemples d'usage
- L'explorateur de fichiers de votre ordinateur (Disque C: > Utilisateurs > Documents).
- La structure DOM d'une page web qui organise les balises HTML.
- Les menus déroulants d'un logiciel qui se divisent en sous-menus.
Cas d'usage
On utilise les arbres pour classer des informations hiérarchiques, accélérer les recherches dans les bases de données (index), ou encore permettre à une intelligence artificielle de prendre des décisions via un « arbre de choix ».
Bonnes pratiques
Il est crucial de veiller à ce que l'arbre soit équilibré. Si une branche est beaucoup plus longue que les autres, l'ordinateur mettra plus de temps à trouver l'information, perdant ainsi l'avantage de cette structure.
Synonymes
Antonymes
Conseil
Pour bien comprendre, visualisez votre disque dur : chaque dossier est un nœud et chaque fichier est une feuille. Si vous comprenez comment naviguer dans vos dossiers, vous comprenez la logique des arbres informatiques.
Questions fréquentes
Quelle est la différence entre un arbre et un graphe ?
Un arbre est un graphe simplifié : il n'a pas de cycle (on ne peut pas revenir en arrière par un autre chemin) et tout est relié à une seule racine.
Qu'est-ce qu'un arbre binaire ?
C'est un modèle où chaque nœud peut avoir au maximum deux descendants (souvent appelés fils gauche et fils droit).