Types d'arbres binaires
Objectifs
Distinguer les différentes catégories d'arbres binaires (plein, complet, parfait, équilibré) et comprendre leurs propriétés caractéristiques ainsi que leurs applications.
Prérequis
Notions de base sur les arbres binaires, hauteur, niveaux et nœuds internes.
Arbre binaire plein (Full Binary Tree)
Un arbre binaire plein (ou arbre binaire strict) est un arbre binaire dans lequel chaque nœud a 0 ou 2 enfants. Autrement dit, tous les nœuds, à l'exception des feuilles, ont exactement deux enfants.
Exemples d'arbres binaires pleins
Dans un arbre binaire plein, le nombre de feuilles est égal au nombre de nœuds internes plus un :
\[ \boxed{L = I + 1} \]où :
- \(L\) = nombre de feuilles (nœuds sans enfants)
- \(I\) = nombre de nœuds internes (nœuds ayant deux enfants)
A
/ \
B C
/ \ \
D E F
/ \ \
G H I
Feuilles (L) = 5 (G, H, E, F, I) Nœuds internes (I) = 4 (A, B, C, D) Vérification : 5 = 4 + 1 ✓
Arbre binaire complet (Complete Binary Tree)
Un arbre binaire complet est un arbre binaire dans lequel tous les niveaux sont complètement remplis, sauf peut-être le dernier niveau, et le dernier niveau a toutes ses clés aussi à gauche que possible.
Exemples d'arbres binaires complets
- Un arbre binaire complet peut être représenté efficacement par un tableau (implémentation des tas binaires).
- Pour un nœud à l'indice \(i\) (en indexation 1) :
- Enfant gauche : indice \(2i\)
- Enfant droit : indice \(2i + 1\)
- Parent : indice \(\lfloor i/2 \rfloor\)
Les arbres binaires complets sont utilisés pour implémenter les tas binaires (heap), structures de données fondamentales pour les files de priorité et l'algorithme de tri par tas (heapsort).
Arbre binaire parfait (Perfect Binary Tree)
Un arbre binaire parfait est un arbre binaire dans lequel tous les nœuds internes ont deux enfants et toutes les feuilles sont au même niveau.
Exemples d'arbres binaires parfaits
Pour un arbre binaire parfait de hauteur \(h\) (avec la racine à la hauteur \(1\)) :
\[ \boxed{N = 2^{h} - 1} \]où \(N\) est le nombre total de nœuds.
Autres propriétés :
- Nombre de feuilles : \(L = 2^{h-1}\)
- Nombre de nœuds internes : \(I = 2^{h-1} - 1\)
- Hauteur : \(h = \log_2(N + 1)\)
Un arbre parfait est à la fois plein et complet. C'est la structure la plus équilibrée possible pour une hauteur donnée.
Arbre binaire équilibré (Balanced Binary Tree)
Un arbre binaire équilibré est un arbre binaire dont la hauteur est \(O(\log n)\), où \(n\) est le nombre de nœuds. Cette propriété garantit des opérations de recherche, d'insertion et de suppression efficaces.
Exemples d'arbres binaires équilibrés (AVL et rouge-noir)
- Arbre AVL : Maintient la hauteur en \(O(\log n)\) en s'assurant que la différence entre les hauteurs des sous-arbres gauche et droit est au plus 1 (facteur d'équilibre \(\in \{-1, 0, 1\}\)).
- Arbre rouge-noir (Red-Black Tree) : Maintient la hauteur en \(O(\log n)\) en respectant des propriétés de coloration :
- Chaque nœud est rouge ou noir
- La racine est noire
- Pas deux nœuds rouges adjacents
- Chaque chemin racine → feuille contient le même nombre de nœuds noirs
Pour les arbres binaires de recherche équilibrés (AVL, rouge-noir) :
\[ \boxed{T_{\text{recherche}} = O(\log n)} \] \[ \boxed{T_{\text{insertion}} = O(\log n)} \] \[ \boxed{T_{\text{suppression}} = O(\log n)} \]Ces performances sont optimales pour une structure de données dynamique basée sur les comparaisons.
Comparaison des types d'arbres binaires
| Type d'arbre | Caractéristique principale | Propriété clé | Application typique |
|---|---|---|---|
| Plein (Full) | Chaque nœud a 0 ou 2 enfants | \(L = I + 1\) | Arbres d'expression, arbres binaires stricts |
| Complet (Complete) | Tous niveaux remplis sauf dernier, tassé à gauche | Représentation compacte par tableau | Tas binaires (heap), heapsort |
| Parfait (Perfect) | Tous nœuds internes ont 2 enfants, toutes feuilles au même niveau | \(N = 2^h - 1\) | Structure idéale théorique |
| Équilibré (Balanced) | Hauteur \(O(\log n)\) | Recherche, insertion, suppression en \(O(\log n)\) | AVL, arbres rouge-noir, B-arbres |
Hiérarchie et relations
- Un arbre parfait est toujours plein et complet.
- Un arbre complet n'est pas nécessairement plein.
- Un arbre plein n'est pas nécessairement complet.
- Un arbre équilibré (AVL, rouge-noir) n'est pas nécessairement parfait, mais garantit une hauteur logarithmique.
Arbre parfait
├── Arbre plein (tous les nœuds internes ont 2 enfants)
└── Arbre complet (niveaux remplis, tassé à gauche)
Arbre équilibré → hauteur = O(log n) (AVL, Rouge-Noir)
L'essentiel en bref
- Arbre plein (full) : chaque nœud a 0 ou 2 enfants. Relation \(L = I + 1\).
- Arbre complet (complete) : tous les niveaux remplis sauf le dernier, tassé à gauche. Représentation par tableau possible.
- Arbre parfait (perfect) : tous les nœuds internes ont 2 enfants ET toutes les feuilles au même niveau. \(N = 2^h - 1\).
- Arbre équilibré (balanced) : hauteur \(O(\log n)\). AVL et arbres rouge-noir garantissent cette propriété.
- Les arbres équilibrés offrent les meilleures performances pour les dictionnaires dynamiques (\(O(\log n)\) en recherche, insertion, suppression).
- Utilisez un tas binaire (arbre complet) pour les files de priorité.
- Utilisez un AVL ou rouge-noir pour les ensembles/dictionnaires avec des opérations fréquentes.
- Utilisez un arbre plein pour représenter des expressions arithmétiques binaires.
Un peu d'histoire
Les arbres AVL ont été inventés en 1962 par Georgy Adelson-Velsky et Evgenii Landis (d'où le nom AVL). Les arbres rouge-noir ont été introduits par Rudolf Bayer en 1972 sous le nom d'"arbres binaires symétriques" et ont été popularisés par Leonidas Guibas et Robert Sedgewick en 1978. Ces structures équilibrées sont aujourd'hui utilisées dans les bibliothèques standard de nombreux langages (C++ STL `std::map`, Java `TreeMap`).
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.