Arbres#
Les arbres constituent l’une des structures de données les plus omniprésentes en informatique. On les retrouve dans les systèmes de fichiers, les bases de données, les compilateurs, les moteurs de jeux, les algorithmes de compression et bien d’autres domaines encore. Leur puissance vient d’une propriété fondamentale : ils permettent de représenter des hiérarchies et d’organiser l’information de façon à effectuer des recherches, des insertions et des suppressions en un temps proportionnel à leur hauteur, bien inférieur à la taille totale de la structure.
Ce chapitre couvre les fondements théoriques des arbres, les arbres binaires et leurs parcours, les arbres binaires de recherche (BST), leur dégénérescence, les arbres AVL qui y remédient, et enfin les tas qui constituent une structure remarquable à la croisée des arbres et des tableaux.
Définition formelle#
Définition 40 (Arbre)
Un arbre est un graphe acyclique connexe orienté. Plus précisément, c’est un ensemble fini \(T\) de nœuds tel que :
Il existe un nœud distingué appelé racine, noté \(r\).
Chaque nœud \(v \neq r\) possède exactement un parent.
La racine \(r\) n’a pas de parent.
Tout nœud est accessible depuis la racine par un unique chemin.
Définition 41 (Terminologie de base)
Soit \(T\) un arbre et \(v\) un nœud de \(T\).
Les fils (ou enfants) de \(v\) sont les nœuds dont \(v\) est le parent.
Le degré de \(v\) est le nombre de fils de \(v\).
Une feuille est un nœud de degré zéro (sans enfant).
Un nœud interne est un nœud de degré supérieur ou égal à un.
La profondeur de \(v\), notée \(d(v)\), est la longueur du chemin de la racine à \(v\). La racine a une profondeur de zéro.
La hauteur d’un nœud \(v\), notée \(h(v)\), est la longueur du plus long chemin de \(v\) à une feuille de son sous-arbre. Une feuille a une hauteur de zéro.
La hauteur de l’arbre est la hauteur de la racine.
Un sous-arbre enraciné en \(v\) est le sous-ensemble de \(T\) constitué de \(v\) et de tous ses descendants.
Remarque 16
Un arbre à \(n\) nœuds possède exactement \(n - 1\) arêtes. Cette propriété découle directement de la définition : chaque nœud autre que la racine a exactement un parent, donc contribue exactement une arête ; la racine ne contribue aucune arête. La somme est donc \((n - 1) \times 1 = n - 1\).
Définition 42 (Arbre binaire)
Un arbre binaire est un arbre dans lequel chaque nœud possède au plus deux fils, conventionnellement appelés fils gauche et fils droit. Un arbre binaire peut être :
Complet (full ou proper) : chaque nœud interne a exactement zéro ou deux fils.
Parfait : tous les nœuds internes ont deux fils et toutes les feuilles sont à la même profondeur.
Complet (complete) : tous les niveaux sont remplis sauf éventuellement le dernier, qui est rempli de gauche à droite.
Dégénéré (ou filiforme) : chaque nœud interne a exactement un fils, ce qui donne une structure linéaire analogue à une liste chaînée.
Remarque 17
Un arbre binaire parfait de hauteur \(h\) contient exactement \(2^{h+1} - 1\) nœuds et \(2^h\) feuilles. Plus généralement, un arbre binaire de hauteur \(h\) contient au plus \(2^{h+1} - 1\) nœuds. À l’inverse, un arbre binaire à \(n\) nœuds a une hauteur minimale de \(\lfloor \log_2 n \rfloor\), atteinte quand l’arbre est aussi équilibré que possible.
Représentations des arbres binaires#
Il existe deux représentations classiques des arbres binaires en mémoire.
Représentation chaînée#
La représentation chaînée est la plus naturelle. Chaque nœud est un objet contenant une valeur et deux pointeurs vers ses fils gauche et droit.
class NoeudBinaire:
"""Nœud d'un arbre binaire."""
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None # fils gauche
self.droit = None # fils droit
def __repr__(self):
return f"NoeudBinaire({self.valeur})"
class ArbreBinaire:
"""Arbre binaire avec représentation chaînée."""
def __init__(self):
self.racine = None
def est_vide(self):
return self.racine is None
def hauteur(self, noeud=None, _premier_appel=True):
"""Calcule la hauteur de l'arbre ou d'un sous-arbre."""
if _premier_appel:
noeud = self.racine
if noeud is None:
return -1 # convention : arbre vide a hauteur -1
return 1 + max(
self.hauteur(noeud.gauche, False),
self.hauteur(noeud.droit, False)
)
def taille(self, noeud=None, _premier_appel=True):
"""Retourne le nombre de nœuds."""
if _premier_appel:
noeud = self.racine
if noeud is None:
return 0
return 1 + self.taille(noeud.gauche, False) + self.taille(noeud.droit, False)
# Exemple : construction manuelle d'un arbre
arbre = ArbreBinaire()
arbre.racine = NoeudBinaire(1)
arbre.racine.gauche = NoeudBinaire(2)
arbre.racine.droit = NoeudBinaire(3)
arbre.racine.gauche.gauche = NoeudBinaire(4)
arbre.racine.gauche.droit = NoeudBinaire(5)
arbre.racine.droit.droit = NoeudBinaire(6)
print(f"Hauteur : {arbre.hauteur()}")
print(f"Taille : {arbre.taille()}")
Hauteur : 2
Taille : 6
Représentation par tableau#
Pour les arbres binaires complets, il existe une représentation implicite par tableau très efficace. La racine occupe l’indice \(1\) (ou \(0\) selon la convention). Pour un nœud à l’indice \(i\) :
son fils gauche est à l’indice \(2i\) (convention base 1) ou \(2i + 1\) (base 0) ;
son fils droit est à l’indice \(2i + 1\) (base 1) ou \(2i + 2\) (base 0) ;
son parent est à l’indice \(\lfloor i/2 \rfloor\) (base 1) ou \(\lfloor (i-1)/2 \rfloor\) (base 0).
Remarque 18
La représentation par tableau convient parfaitement aux tas (que nous étudierons plus loin) car elle évite les pointeurs et permet un accès en \(O(1)\) à n’importe quel nœud. En revanche, pour un arbre dégénéré à \(n\) nœuds, la représentation par tableau nécessiterait un tableau de taille \(2^n - 1\), ce qui la rend inadaptée aux arbres non complets.
Parcours des arbres binaires#
Un parcours est une façon de visiter tous les nœuds d’un arbre, chacun exactement une fois. Il existe quatre parcours classiques.
Définition 43 (Parcours préfixe (pre-order))
Dans le parcours préfixe, on visite le nœud avant ses enfants :
Visiter la racine.
Parcourir récursivement le sous-arbre gauche.
Parcourir récursivement le sous-arbre droit.
Définition 44 (Parcours infixe (in-order))
Dans le parcours infixe, on visite le nœud entre ses enfants :
Parcourir récursivement le sous-arbre gauche.
Visiter la racine.
Parcourir récursivement le sous-arbre droit.
Ce parcours produit les nœuds d’un BST dans l’ordre croissant.
Définition 45 (Parcours postfixe (post-order))
Dans le parcours postfixe, on visite le nœud après ses enfants :
Parcourir récursivement le sous-arbre gauche.
Parcourir récursivement le sous-arbre droit.
Visiter la racine.
Ce parcours est utile pour libérer de la mémoire (supprimer les fils avant le parent) ou évaluer des expressions arithmétiques.
Définition 46 (Parcours en largeur (BFS / level-order))
Le parcours en largeur visite les nœuds niveau par niveau, de gauche à droite. Il utilise une file (queue) :
Enfiler la racine.
Tant que la file n’est pas vide : défiler un nœud, le visiter, enfiler ses fils (gauche puis droit).
from collections import deque
def parcours_prefixe(noeud):
"""Parcours préfixe (récursif). Retourne la liste des valeurs."""
if noeud is None:
return []
return [noeud.valeur] + parcours_prefixe(noeud.gauche) + parcours_prefixe(noeud.droit)
def parcours_infixe(noeud):
"""Parcours infixe (récursif)."""
if noeud is None:
return []
return parcours_infixe(noeud.gauche) + [noeud.valeur] + parcours_infixe(noeud.droit)
def parcours_postfixe(noeud):
"""Parcours postfixe (récursif)."""
if noeud is None:
return []
return parcours_postfixe(noeud.gauche) + parcours_postfixe(noeud.droit) + [noeud.valeur]
def parcours_largeur(racine):
"""Parcours en largeur (BFS) — itératif avec une file."""
if racine is None:
return []
resultat = []
file = deque([racine])
while file:
noeud = file.popleft()
resultat.append(noeud.valeur)
if noeud.gauche:
file.append(noeud.gauche)
if noeud.droit:
file.append(noeud.droit)
return resultat
# Test sur notre arbre : 1
# / \
# 2 3
# / \ \
# 4 5 6
r = arbre.racine
print("Préfixe :", parcours_prefixe(r)) # 1 2 4 5 3 6
print("Infixe :", parcours_infixe(r)) # 4 2 5 1 3 6
print("Postfixe :", parcours_postfixe(r)) # 4 5 2 6 3 1
print("Largeur :", parcours_largeur(r)) # 1 2 3 4 5 6
Préfixe : [1, 2, 4, 5, 3, 6]
Infixe : [4, 2, 5, 1, 3, 6]
Postfixe : [4, 5, 2, 6, 3, 1]
Largeur : [1, 2, 3, 4, 5, 6]
Arbre binaire de recherche (BST)#
Définition 47 (Arbre binaire de recherche)
Un arbre binaire de recherche (BST, Binary Search Tree) est un arbre binaire qui satisfait la propriété BST : pour tout nœud \(v\) de valeur \(k\),
tous les nœuds du sous-arbre gauche ont des valeurs strictement inférieures à \(k\) ;
tous les nœuds du sous-arbre droit ont des valeurs strictement supérieures à \(k\).
(Les doublons peuvent être traités en autorisant l’égalité à gauche ou à droite selon les conventions.)
Cette propriété garantit que le parcours infixe d’un BST produit les valeurs dans l’ordre croissant, et qu’elle permet de retrouver un élément en suivant à chaque nœud le bon sous-arbre, comme dans une recherche dichotomique.
Opérations fondamentales#
La recherche, l”insertion et la suppression dans un BST ont toutes une complexité \(O(h)\) où \(h\) est la hauteur de l’arbre.
class BST:
"""Arbre binaire de recherche complet."""
class _Noeud:
def __init__(self, cle):
self.cle = cle
self.gauche = None
self.droit = None
def __init__(self):
self.racine = None
# ------------------------------------------------------------------ #
# Recherche
# ------------------------------------------------------------------ #
def rechercher(self, cle):
"""Retourne True si cle est dans l'arbre, False sinon. O(h)."""
return self._rechercher(self.racine, cle)
def _rechercher(self, noeud, cle):
if noeud is None:
return False
if cle == noeud.cle:
return True
elif cle < noeud.cle:
return self._rechercher(noeud.gauche, cle)
else:
return self._rechercher(noeud.droit, cle)
# ------------------------------------------------------------------ #
# Insertion
# ------------------------------------------------------------------ #
def inserer(self, cle):
"""Insère une clé dans le BST. O(h)."""
self.racine = self._inserer(self.racine, cle)
def _inserer(self, noeud, cle):
if noeud is None:
return self._Noeud(cle)
if cle < noeud.cle:
noeud.gauche = self._inserer(noeud.gauche, cle)
elif cle > noeud.cle:
noeud.droit = self._inserer(noeud.droit, cle)
# Si cle == noeud.cle : doublon ignoré
return noeud
# ------------------------------------------------------------------ #
# Minimum et maximum
# ------------------------------------------------------------------ #
def minimum(self, noeud=None):
"""Retourne la plus petite clé du sous-arbre. O(h)."""
if noeud is None:
noeud = self.racine
while noeud.gauche:
noeud = noeud.gauche
return noeud.cle
def maximum(self, noeud=None):
"""Retourne la plus grande clé du sous-arbre. O(h)."""
if noeud is None:
noeud = self.racine
while noeud.droit:
noeud = noeud.droit
return noeud.cle
# ------------------------------------------------------------------ #
# Suppression
# ------------------------------------------------------------------ #
def supprimer(self, cle):
"""Supprime une clé du BST. O(h)."""
self.racine = self._supprimer(self.racine, cle)
def _supprimer(self, noeud, cle):
if noeud is None:
return None
if cle < noeud.cle:
noeud.gauche = self._supprimer(noeud.gauche, cle)
elif cle > noeud.cle:
noeud.droit = self._supprimer(noeud.droit, cle)
else:
# Nœud trouvé : trois cas
if noeud.gauche is None:
return noeud.droit # Cas 1 & 2 : 0 ou 1 enfant
elif noeud.droit is None:
return noeud.gauche
else:
# Cas 3 : deux enfants
# Remplacer par le successeur (minimum du sous-arbre droit)
successeur_cle = self.minimum(noeud.droit)
noeud.cle = successeur_cle
noeud.droit = self._supprimer(noeud.droit, successeur_cle)
return noeud
# ------------------------------------------------------------------ #
# Parcours infixe
# ------------------------------------------------------------------ #
def infixe(self):
resultat = []
self._infixe(self.racine, resultat)
return resultat
def _infixe(self, noeud, acc):
if noeud is None:
return
self._infixe(noeud.gauche, acc)
acc.append(noeud.cle)
self._infixe(noeud.droit, acc)
def hauteur(self):
return self._hauteur(self.racine)
def _hauteur(self, noeud):
if noeud is None:
return -1
return 1 + max(self._hauteur(noeud.gauche), self._hauteur(noeud.droit))
# Démonstration
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
bst.inserer(v)
print("Infixe (doit être trié) :", bst.infixe())
print("Minimum :", bst.minimum())
print("Maximum :", bst.maximum())
print("Recherche 40 :", bst.rechercher(40))
print("Recherche 45 :", bst.rechercher(45))
bst.supprimer(30)
print("Après suppression de 30 :", bst.infixe())
print("Hauteur :", bst.hauteur())
Infixe (doit être trié) : [20, 30, 40, 50, 60, 70, 80]
Minimum : 20
Maximum : 80
Recherche 40 : True
Recherche 45 : False
Après suppression de 30 : [20, 40, 50, 60, 70, 80]
Hauteur : 2
Exemple 9 (Complexité des opérations BST)
Pour un BST équilibré à \(n\) nœuds, la hauteur vaut \(h = O(\log n)\). Toutes les opérations (recherche, insertion, suppression) s’exécutent donc en \(O(\log n)\).
Cependant, cette garantie n’est valable que si l’arbre est équilibré. Pour \(n\) insertions dans un ordre quelconque, la hauteur attendue est \(O(\log n)\) en moyenne (si les clés arrivent dans un ordre aléatoire). Mais dans le pire cas — par exemple si l’on insère des clés dans l’ordre croissant — l’arbre dégénère en une liste chaînée de hauteur \(n - 1\), et toutes les opérations deviennent \(O(n)\).
Dégénérescence du BST et arbres équilibrés#
Remarque 19
Le défaut fondamental du BST naïf est son manque de garantie sur la hauteur. Si les clés arrivent dans un ordre défavorable (trié, quasi-trié, ou alternant extrêmes et médianes), l’arbre peut dégénérer et toutes les opérations se dégradent de \(O(\log n)\) à \(O(n)\). La solution consiste à utiliser des arbres auto-équilibrés qui maintiennent automatiquement une hauteur \(O(\log n)\) après chaque modification.
Arbre AVL#
L”arbre AVL (du nom d’Adelson-Velsky et Landis, 1962) est le premier arbre binaire de recherche auto-équilibré publié dans la littérature. Il maintient l’invariant suivant.
Définition 48 (Facteur d’équilibre et invariant AVL)
Le facteur d’équilibre d’un nœud \(v\) est défini par : $\(\text{fe}(v) = h(\text{sous-arbre droit de } v) - h(\text{sous-arbre gauche de } v)\)$
Un arbre est dit AVL si, pour tout nœud \(v\), le facteur d’équilibre satisfait \(\text{fe}(v) \in \{-1, 0, +1\}\).
Sous cet invariant, on peut montrer que la hauteur d’un AVL à \(n\) nœuds est au plus \(1{,}44 \log_2 n\), ce qui garantit \(O(\log n)\) pour toutes les opérations.
Rotations#
Lorsqu’une insertion ou une suppression viole l’invariant AVL, on rétablit l’équilibre par des rotations.
Définition 49 (Rotation droite et rotation gauche)
Une rotation droite sur un nœud \(y\) déséquilibré à gauche transforme :
y x
/ \ / \
x C → A y
/ \ / \
A B B C
Définition 50 (Rotation gauche)
Une rotation gauche sur un nœud \(x\) déséquilibré à droite est le miroir de la rotation droite.
Il existe quatre cas de déséquilibre, selon que la violation survient dans le sous-arbre gauche-gauche, gauche-droit, droit-droit ou droit-gauche. Les cas « droits » nécessitent une rotation simple ; les cas « en zigzag » nécessitent une double rotation.
class NoeudAVL:
"""Nœud d'un arbre AVL stockant sa hauteur."""
def __init__(self, cle):
self.cle = cle
self.gauche = None
self.droit = None
self.hauteur = 0 # hauteur du sous-arbre enraciné ici
def hauteur_avl(n):
"""Hauteur d'un nœud AVL (None → -1)."""
return -1 if n is None else n.hauteur
def maj_hauteur(n):
n.hauteur = 1 + max(hauteur_avl(n.gauche), hauteur_avl(n.droit))
def facteur_equilibre(n):
if n is None:
return 0
return hauteur_avl(n.droit) - hauteur_avl(n.gauche)
def rotation_droite(y):
"""Rotation droite sur y ; retourne la nouvelle racine."""
x = y.gauche
B = x.droit
x.droit = y
y.gauche = B
maj_hauteur(y)
maj_hauteur(x)
return x
def rotation_gauche(x):
"""Rotation gauche sur x ; retourne la nouvelle racine."""
y = x.droit
B = y.gauche
y.gauche = x
x.droit = B
maj_hauteur(x)
maj_hauteur(y)
return y
def inserer_avl(noeud, cle):
"""Insère cle dans le sous-arbre AVL enraciné en noeud ; retourne la nouvelle racine."""
# Insertion BST standard
if noeud is None:
return NoeudAVL(cle)
if cle < noeud.cle:
noeud.gauche = inserer_avl(noeud.gauche, cle)
elif cle > noeud.cle:
noeud.droit = inserer_avl(noeud.droit, cle)
else:
return noeud # doublon ignoré
maj_hauteur(noeud)
fe = facteur_equilibre(noeud)
# Cas gauche-gauche
if fe < -1 and cle < noeud.gauche.cle:
return rotation_droite(noeud)
# Cas droit-droit
if fe > 1 and cle > noeud.droit.cle:
return rotation_gauche(noeud)
# Cas gauche-droit
if fe < -1 and cle > noeud.gauche.cle:
noeud.gauche = rotation_gauche(noeud.gauche)
return rotation_droite(noeud)
# Cas droit-gauche
if fe > 1 and cle < noeud.droit.cle:
noeud.droit = rotation_droite(noeud.droit)
return rotation_gauche(noeud)
return noeud
def infixe_avl(noeud, acc=None):
if acc is None:
acc = []
if noeud is None:
return acc
infixe_avl(noeud.gauche, acc)
acc.append(noeud.cle)
infixe_avl(noeud.droit, acc)
return acc
# Test : insertion dans l'ordre trié (pire cas pour un BST naïf)
racine_avl = None
for v in [10, 20, 30, 40, 50, 25]:
racine_avl = inserer_avl(racine_avl, v)
print("Infixe AVL :", infixe_avl(racine_avl))
print("Hauteur AVL :", racine_avl.hauteur)
print("Facteur d'équilibre de la racine :", facteur_equilibre(racine_avl))
Infixe AVL : [10, 20, 25, 30, 40, 50]
Hauteur AVL : 2
Facteur d'équilibre de la racine : 0
Tas (Heap)#
Définition 51 (Tas binaire)
Un tas binaire (ou binary heap) est un arbre binaire complet qui satisfait la propriété de tas :
Tas-max : la valeur de chaque nœud est supérieure ou égale à celle de ses fils. La racine contient le maximum.
Tas-min : la valeur de chaque nœud est inférieure ou égale à celle de ses fils. La racine contient le minimum.
Grâce à la structure complète, le tas se représente naturellement par un tableau sans pointeurs.
Remarque 20
La propriété de tas est strictement plus faible que la propriété BST. Elle garantit uniquement que chaque nœud est supérieur (ou inférieur) à ses fils, sans imposer un ordre global gauche-droite. En contrepartie, le tas permet d’accéder au maximum (ou minimum) en \(O(1)\) et de l’extraire en \(O(\log n)\), ce qui en fait la structure idéale pour implémenter une file de priorité.
Représentation par tableau#
Pour un tas stocké dans un tableau indexé à partir de \(0\) :
La racine est à l’indice \(0\).
Le fils gauche du nœud \(i\) est à l’indice \(2i + 1\).
Le fils droit du nœud \(i\) est à l’indice \(2i + 2\).
Le parent du nœud \(i\) est à l’indice \(\lfloor (i - 1) / 2 \rfloor\).
Opérations fondamentales#
class TasMax:
"""Tas-max implémenté sur un tableau Python."""
def __init__(self):
self._data = []
def __len__(self):
return len(self._data)
def _parent(self, i):
return (i - 1) // 2
def _gauche(self, i):
return 2 * i + 1
def _droit(self, i):
return 2 * i + 2
def _echanger(self, i, j):
self._data[i], self._data[j] = self._data[j], self._data[i]
def _percoler_haut(self, i):
"""Fait remonter l'élément i jusqu'à sa position correcte."""
while i > 0:
p = self._parent(i)
if self._data[i] > self._data[p]:
self._echanger(i, p)
i = p
else:
break
def _percoler_bas(self, i, n=None):
"""Fait descendre l'élément i jusqu'à sa position correcte."""
if n is None:
n = len(self._data)
while True:
plus_grand = i
g = self._gauche(i)
d = self._droit(i)
if g < n and self._data[g] > self._data[plus_grand]:
plus_grand = g
if d < n and self._data[d] > self._data[plus_grand]:
plus_grand = d
if plus_grand == i:
break
self._echanger(i, plus_grand)
i = plus_grand
def inserer(self, valeur):
"""Insère une valeur dans le tas. O(log n)."""
self._data.append(valeur)
self._percoler_haut(len(self._data) - 1)
def maximum(self):
"""Retourne le maximum sans l'extraire. O(1)."""
if not self._data:
raise IndexError("Tas vide")
return self._data[0]
def extraire_max(self):
"""Extrait et retourne le maximum. O(log n)."""
if not self._data:
raise IndexError("Tas vide")
max_val = self._data[0]
dernier = self._data.pop()
if self._data:
self._data[0] = dernier
self._percoler_bas(0)
return max_val
@classmethod
def depuis_liste(cls, lst):
"""Construit un tas à partir d'une liste en O(n) par heapify."""
tas = cls()
tas._data = list(lst)
n = len(tas._data)
# Partir du dernier nœud interne et percoler vers le bas
for i in range(n // 2 - 1, -1, -1):
tas._percoler_bas(i)
return tas
# Test
tas = TasMax()
for v in [3, 1, 4, 1, 5, 9, 2, 6]:
tas.inserer(v)
print("Maximum :", tas.maximum())
print("Extraction successive :", end=' ')
resultats = []
while len(tas) > 0:
resultats.append(tas.extraire_max())
print(resultats) # doit être trié en ordre décroissant
# Heapify en O(n)
tas2 = TasMax.depuis_liste([3, 1, 4, 1, 5, 9, 2, 6])
print("Tableau heapifié :", tas2._data)
print("Racine (max) :", tas2.maximum())
Maximum : 9
Extraction successive : [9, 6, 5, 4, 3, 2, 1, 1]
Tableau heapifié : [9, 6, 4, 1, 5, 3, 2, 1]
Racine (max) : 9
Remarque 21
Python propose le module heapq en bibliothèque standard, qui implémente un tas-min. Pour obtenir un tas-max, on stocke les négations des valeurs. heapq.heappush(h, x) et heapq.heappop(h) opèrent toutes les deux en \(O(\log n)\), et heapq.heapify(lst) construit le tas en \(O(n)\) grâce à l’algorithme de Floyd.
import heapq
# heapq implémente un tas-min
tas_min = []
for v in [3, 1, 4, 1, 5, 9, 2, 6]:
heapq.heappush(tas_min, v)
print("Extraction min successive :", end=' ')
while tas_min:
print(heapq.heappop(tas_min), end=' ')
print()
# Heapify en O(n)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(lst)
print("Heapify O(n) :", lst)
Extraction min successive : 1 1 2 3 4 5 6 9
Heapify O(n) : [1, 1, 2, 3, 5, 9, 4, 6]
Implémentation Rust#
En Rust, les arbres binaires s’expriment naturellement avec les enums récursifs et les Box<T> pour allouer les fils sur le tas (heap).
use std::fmt;
/// Nœud d'un arbre binaire de recherche générique.
#[derive(Debug)]
enum Arbre<T: Ord> {
Vide,
Noeud {
cle: T,
gauche: Box<Arbre<T>>,
droit: Box<Arbre<T>>,
},
}
impl<T: Ord + fmt::Debug> Arbre<T> {
fn vide() -> Self {
Arbre::Vide
}
fn inserer(self, nouvelle_cle: T) -> Self {
match self {
Arbre::Vide => Arbre::Noeud {
cle: nouvelle_cle,
gauche: Box::new(Arbre::Vide),
droit: Box::new(Arbre::Vide),
},
Arbre::Noeud { cle, gauche, droit } => {
if nouvelle_cle < cle {
Arbre::Noeud {
cle,
gauche: Box::new(gauche.inserer(nouvelle_cle)),
droit,
}
} else if nouvelle_cle > cle {
Arbre::Noeud {
cle,
gauche,
droit: Box::new(droit.inserer(nouvelle_cle)),
}
} else {
// Doublon : on retourne l'arbre inchangé
Arbre::Noeud { cle, gauche, droit }
}
}
}
}
fn contient(&self, cible: &T) -> bool {
match self {
Arbre::Vide => false,
Arbre::Noeud { cle, gauche, droit } => {
if cible == cle {
true
} else if cible < cle {
gauche.contient(cible)
} else {
droit.contient(cible)
}
}
}
}
fn hauteur(&self) -> usize {
match self {
Arbre::Vide => 0,
Arbre::Noeud { gauche, droit, .. } => {
1 + gauche.hauteur().max(droit.hauteur())
}
}
}
fn infixe(&self) -> Vec<&T> {
match self {
Arbre::Vide => vec![],
Arbre::Noeud { cle, gauche, droit } => {
let mut res = gauche.infixe();
res.push(cle);
res.extend(droit.infixe());
res
}
}
}
}
fn main() {
let valeurs = vec![50, 30, 70, 20, 40, 60, 80];
let arbre = valeurs
.into_iter()
.fold(Arbre::vide(), |acc, v| acc.inserer(v));
println!("Infixe : {:?}", arbre.infixe());
println!("Hauteur : {}", arbre.hauteur());
println!("Contient 40 : {}", arbre.contient(&40));
println!("Contient 45 : {}", arbre.contient(&45));
}
L’utilisation d’un enum récursif avec Box<Arbre<T>> est idiomatique en Rust : le Box permet de rompre la récursivité en allouant dynamiquement chaque nœud. La propriété d’ownership garantit que la libération mémoire se fait automatiquement lorsque l’arbre sort de portée, sans ramasse-miettes.
Résumé#
Ce chapitre a présenté les structures d’arbres dans toute leur richesse :
Un arbre est un graphe acyclique connexe avec une racine distinguée. Un arbre à \(n\) nœuds possède \(n - 1\) arêtes. La hauteur, la profondeur et le degré caractérisent la structure locale et globale.
Les arbres binaires admettent deux représentations : chaînée (pointeurs gauche/droit) pour les arbres de forme quelconque, et tableau implicite (très efficace en cache) pour les arbres complets.
Les quatre parcours — préfixe, infixe, postfixe et en largeur — permettent de visiter tous les nœuds selon différents ordres, chacun adapté à un usage particulier.
Le BST garantit \(O(\log n)\) en moyenne mais peut dégénérer en \(O(n)\) sur des entrées défavorables. Le parcours infixe d’un BST produit les clés en ordre croissant.
L”AVL corrige ce défaut en maintenant un facteur d’équilibre dans \(\{-1, 0, +1\}\) via des rotations. La hauteur reste \(O(\log n)\) dans tous les cas.
Le tas binaire est un arbre complet stocké dans un tableau ; il offre un accès en \(O(1)\) au maximum (ou minimum) et une extraction en \(O(\log n)\), ce qui en fait la brique de base des files de priorité et du tri par tas.
En Rust, les arbres s’implémentent naturellement avec des enums récursifs et
Box<T>, le compilateur garantissant la sécurité mémoire sans coût de ramasse-miettes.
Le chapitre suivant étend la notion d’arbre aux graphes généraux, qui abandonnent les contraintes de hiérarchie et permettent de modéliser des réseaux, des dépendances et de nombreux problèmes combinatoires.