Table des Matières
1. Qu'est-ce qu'un Arbre Enraciné ?
En théorie des graphes, un arbre est un graphe connexe sans cycle. Un arbre enraciné est simplement un arbre dans lequel un sommet particulier a été choisi comme racine. Ce seul choix donne à tous les autres nœuds un « haut » (vers la racine) et un « bas » (à l'opposé), transformant un arbre ordinaire en une hiérarchie.
Un fait utile : un arbre à n nœuds possède toujours exactement n - 1 arêtes, et il existe exactement un chemin entre deux nœuds quelconques, ni plus ni moins.
2. Terminologie Clé
- Racine : le nœud le plus haut ; le seul sans parent.
- Parent / Enfant : si une arête relie A (plus proche de la racine) à B, alors A est le parent et B l'enfant.
- Frères : des nœuds partageant le même parent.
- Feuille : un nœud sans enfant, une « extrémité » de l'arbre.
- Nœud interne : tout nœud ayant au moins un enfant.
- Ancêtre / Descendant : nœuds sur le chemin vers la racine / vers le bas depuis un nœud.
- Profondeur : le nombre d'arêtes de la racine à un nœud. La racine a une profondeur de 0.
- Hauteur : la plus grande distance d'un nœud jusqu'à une feuille. La hauteur de l'arbre est celle de sa racine.
- Sous-arbre : un nœud avec tous ses descendants.
3. Arbres Enracinés ou Non
Un arbre non enraciné décrit seulement quels nœuds sont connectés : il n'y a ni haut ni bas. Dès que l'on choisit une racine, le même ensemble d'arêtes acquiert une direction : les arêtes sont désormais comprises comme pointant à l'opposé de la racine, de sorte qu'un arbre enraciné se comporte comme un type particulier de graphe orienté. Choisir une racine différente produit une hiérarchie différente à partir du même arbre sous-jacent.
Voir les Arbres en Mouvement
Construisez un arbre enraciné et regardez les parcours DFS et BFS s'allumer nœud par nœud. La profondeur, la hauteur et les liens parent-enfant prennent soudain tout leur sens.
Ouvrir le Visualiseur4. Comment les Arbres Enracinés sont Représentés
Il existe trois façons courantes de stocker un arbre enraciné en code :
- Tableau des parents : stocke le parent de chaque nœud dans un tableau (
parent[i]). Compact et idéal pour « remonter vers la racine ». - Listes d'enfants : chaque nœud contient la liste de ses enfants, la représentation la plus souple pour les parcours.
- Enfant-gauche / frère-droit : un encodage de style binaire qui stocke tout arbre n-aire avec seulement deux pointeurs par nœud.
5. Types d'Arbres Enracinés
- Arbre binaire : chaque nœud a au plus deux enfants, un « gauche » et un « droit ».
- Arbre binaire de recherche (ABR) : un arbre binaire maintenu trié, donc les recherches prennent O(log n) lorsqu'il est équilibré.
- Arbre n-aire : les nœuds peuvent avoir un nombre quelconque d'enfants, comme un dossier de système de fichiers.
- Arbres équilibrés (AVL, rouge-noir, B-arbres) maintiennent automatiquement une hauteur faible pour garantir des opérations rapides.
6. Parcourir un Arbre Enraciné
Visiter tous les nœuds s'appelle un parcours, et il existe deux grandes familles :
- En profondeur (DFS) : descendre le plus loin possible avant de revenir en arrière. Pour les arbres binaires, on distingue les variantes préfixe, infixe et postfixe.
- En largeur (BFS) : visiter tous les nœuds d'un niveau avant de descendre, aussi appelé parcours par niveaux.
Si cela vous semble familier, c'est parce que ce sont les mêmes stratégies utilisées sur les graphes généraux. Voir notre analyse de BFS vs DFS.
7. Applications Concrètes
- Systèmes de fichiers : dossiers et fichiers forment un arbre enraciné, avec le répertoire racine au sommet.
- Le DOM HTML : chaque page web est un arbre enraciné d'éléments, y compris celle que vous lisez.
- Bases de données : les B-arbres et B+-arbres alimentent les index qui accélèrent les requêtes.
- Compilateurs : le code source est analysé en un arbre syntaxique abstrait (AST).
- Arbres de décision et tas : les modèles d'apprentissage automatique et les files de priorité reposent sur des arbres enracinés.
Foire Aux Questions
Quelle est la différence entre un arbre enraciné et non enraciné ?
Un arbre non enraciné indique seulement quels nœuds sont connectés. Un arbre enraciné désigne un nœud comme racine, donnant à l'arbre une hiérarchie avec des relations parent-enfant et un sommet clair.
Quelle est la différence entre la profondeur et la hauteur d'un arbre ?
La profondeur est la distance de la racine jusqu'à un nœud donné (la racine a une profondeur de 0). La hauteur est la distance d'un nœud jusqu'à sa feuille la plus profonde ; la hauteur de l'arbre est celle de la racine.
Un arbre enraciné est-il un graphe orienté ?
On peut le voir ainsi. Une fois la racine choisie, chaque arête est implicitement orientée à l'opposé de la racine, donnant à chaque nœud non racine exactement un parent.
Combien d'arêtes possède un arbre à n nœuds ?
Exactement n - 1. Ajouter une arête supplémentaire créerait un cycle, or un arbre n'en a aucun par définition.