Définitions récursives des arbres
Objectifs
Comprendre la nature récursive des structures arborescentes et maîtriser les définitions formelles des arbres enracinés, des arbres binaires étendus, des arbres binaires complets ainsi que leurs propriétés fondamentales.
Prérequis
Notions de base sur les graphes, la récursivité et les arbres binaires.
Arbre enraciné
Un arbre enraciné est un ensemble de sommets contenant un sommet distingué appelé racine, et d'arêtes reliant ces sommets, formant une structure hiérarchique sans cycle.
L'ensemble des arbres enracinés peut être défini de manière récursive par les étapes suivantes :
- Cas de base : Un seul sommet \(r\) est un arbre enraciné.
- Étape récursive : Soient \(T_1, T_2, \ldots, T_n\) des arbres enracinés disjoints avec des racines \(r_1, r_2, \ldots, r_n\) respectivement. Le graphe formé par une nouvelle racine \(r\) (n'appartenant à aucun des \(T_i\)) et des arêtes reliant \(r\) à chaque racine \(r_i\) est également un arbre enraciné.
Exemple : construction récursive d'un arbre enraciné
Dans cette définition, l'ordre des sous-arbres \(T_1, T_2, \ldots, T_n\) n'est pas significatif. Il s'agit d'un arbre enraciné non ordonné (arbre libre avec racine).
Arbre binaire étendu
Un arbre binaire étendu (ou arbre binaire généralisé) est un arbre binaire où chaque nœud a exactement 0 ou 2 enfants, et où les enfants absents sont représentés par des feuilles externes (ou nœuds vides).
L'ensemble des arbres binaires étendus peut être défini de manière récursive par :
- Cas de base : L'ensemble vide \(\emptyset\) est un arbre binaire étendu.
- Étape récursive : Si \(T_1\) et \(T_2\) sont des arbres binaires étendus disjoints, alors il existe un arbre binaire étendu, noté \(T_1 \cdot T_2\), constitué d'une racine \(r\) avec :
- un sous-arbre gauche \(T_1\) (relié à la racine si \(T_1 \neq \emptyset\)),
- un sous-arbre droit \(T_2\) (relié à la racine si \(T_2 \neq \emptyset\)).
Exemple : arbre binaire étendu avec nœuds externes (carrés)
Les arbres binaires étendus sont particulièrement utiles pour représenter des expressions arithmétiques ou pour l'étude des arbres de décision, où chaque feuille externe correspond à un cas terminal.
Arbre binaire complet
Un arbre binaire complet (ou arbre binaire strict) est un arbre binaire où chaque nœud interne possède exactement deux enfants.
L'ensemble des arbres binaires complets peut être défini récursivement par :
- Cas de base : Un seul sommet \(r\) (une feuille) est un arbre binaire complet.
- Étape récursive : Si \(T_1\) et \(T_2\) sont des arbres binaires complets disjoints, alors l'arbre noté \(T_1 \cdot T_2\), constitué d'une racine \(r\) avec sous-arbre gauche \(T_1\) et sous-arbre droit \(T_2\), est également un arbre binaire complet.
Exemple : arbre binaire complet (chaque nœud interne a 2 enfants)
La différence fondamentale entre arbre binaire étendu et arbre binaire complet réside dans la gestion des feuilles :
- Dans un arbre étendu, les feuilles externes (vides) sont explicitement représentées.
- Dans un arbre complet, toutes les feuilles sont des nœuds réels, et chaque nœud interne a exactement deux enfants.
Hauteur d'un arbre binaire complet
La hauteur \(h(T)\) d'un arbre binaire complet \(T\) est définie récursivement par :
- Cas de base : \(h(T) = 0\) pour l'arbre réduit à un seul sommet \(r\).
- Étape récursive : Si \(T = T_1 \cdot T_2\), alors \[ \boxed{h(T) = 1 + \max\bigl(h(T_1), h(T_2)\bigr)} \]
A
/ \
B C
/ \ \
D E F
h(D) = 0, h(E) = 0, h(F) = 0 h(B) = 1 + max(0,0) = 1 h(C) = 1 + max(0,0) = 1 h(A) = 1 + max(1,1) = 2
Nombre de sommets dans un arbre binaire complet
Soit \(n(T)\) le nombre de sommets dans un arbre binaire complet \(T\). La fonction \(n(T)\) est définie récursivement par :
- Cas de base : \(n(T) = 1\) pour l'arbre réduit à un seul sommet \(r\).
- Étape récursive : Si \(T = T_1 \cdot T_2\), alors \[ \boxed{n(T) = 1 + n(T_1) + n(T_2)} \]
Pour un arbre binaire complet de hauteur \(h\), le nombre de sommets vérifie :
\[ n(T) \ge 2h + 1 \quad \text{et} \quad n(T) \le 2^{h+1} - 1 \]Le minimum est atteint pour un arbre filiforme (chaque nœud interne a un enfant feuille), le maximum pour un arbre parfait (tous les niveaux remplis).
Comparaison des types d'arbres
| Type d'arbre | Caractéristique principale | Définition récursive |
|---|---|---|
| Arbre enraciné | Un nœud distingué (racine), ordre non significatif | \(T = r \cup \{T_1, T_2, \ldots, T_n\}\) |
| Arbre binaire étendu | Feuilles externes (vides) représentées, 0 ou 2 enfants | \(T = \emptyset\) ou \(T = T_1 \cdot T_2\) |
| Arbre binaire complet | Chaque nœud interne a exactement 2 enfants | \(T = \text{feuille}\) ou \(T = T_1 \cdot T_2\) |
Propriétés supplémentaires
Dans un arbre binaire complet (strict) :
\[ \boxed{L = I + 1} \]où \(L\) est le nombre de feuilles et \(I\) le nombre de nœuds internes.
Pour un arbre binaire complet de hauteur \(h\) :
\[ h + 1 \le n(T) \le 2^{h+1} - 1 \]et réciproquement :
\[ \lceil \log_2(n(T) + 1) \rceil - 1 \le h(T) \le n(T) - 1 \]L'essentiel en bref
- Arbre enraciné : \(T = r \cup \{T_1, \ldots, T_n\}\) avec \(T_i\) des arbres enracinés disjoints.
- Arbre binaire étendu : \(T = \emptyset\) (cas vide) ou \(T = T_1 \cdot T_2\) avec \(T_1, T_2\) étendus.
- Arbre binaire complet : \(T = \text{feuille}\) ou \(T = T_1 \cdot T_2\) avec \(T_1, T_2\) complets.
- Hauteur : \(h(\text{feuille}) = 0\), \(h(T_1 \cdot T_2) = 1 + \max(h(T_1), h(T_2))\)
- Nombre de sommets : \(n(\text{feuille}) = 1\), \(n(T_1 \cdot T_2) = 1 + n(T_1) + n(T_2)\)
La récursivité est au cœur de la manipulation des arbres. Pour concevoir des algorithmes sur les arbres (parcours, recherche, insertion, suppression), pensez toujours en termes de cas de base (arbre vide ou feuille) et d'étape récursive (combinaison des résultats des sous-arbres).
Un peu d'histoire
Les définitions récursives des arbres ont été formalisées par Donald Knuth dans The Art of Computer Programming (Volume 1, 1968). Cette approche récursive est fondamentale pour comprendre et implémenter correctement les structures arborescentes en programmation.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.