--- jupytext: text_representation: extension: .md format_name: myst format_version: 0.13 jupytext_version: 1.16.0 kernelspec: name: python3 display_name: Python 3 --- # Arbres ```{code-cell} python :tags: [hide-input] import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np import seaborn as sns sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1) ``` 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 ```{prf:definition} Arbre :label: definition-06-01 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. ``` ```{prf:definition} Terminologie de base :label: definition-06-02 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. ``` ```{prf:remark} :label: remark-06-01 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$. ``` ```{prf:definition} Arbre binaire :label: definition-06-03 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. ``` ```{prf:remark} :label: remark-06-02 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. ```{code-cell} python 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()}") ``` ### 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). ```{prf:remark} :label: remark-06-03 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. ```{prf:definition} Parcours préfixe (pre-order) :label: definition-06-04 Dans le **parcours préfixe**, on visite le nœud *avant* ses enfants : 1. Visiter la racine. 2. Parcourir récursivement le sous-arbre gauche. 3. Parcourir récursivement le sous-arbre droit. ``` ```{prf:definition} Parcours infixe (in-order) :label: definition-06-05 Dans le **parcours infixe**, on visite le nœud *entre* ses enfants : 1. Parcourir récursivement le sous-arbre gauche. 2. Visiter la racine. 3. Parcourir récursivement le sous-arbre droit. Ce parcours produit les nœuds d'un BST dans l'ordre croissant. ``` ```{prf:definition} Parcours postfixe (post-order) :label: definition-06-06 Dans le **parcours postfixe**, on visite le nœud *après* ses enfants : 1. Parcourir récursivement le sous-arbre gauche. 2. Parcourir récursivement le sous-arbre droit. 3. 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. ``` ```{prf:definition} Parcours en largeur (BFS / level-order) :label: definition-06-07 Le **parcours en largeur** visite les nœuds niveau par niveau, de gauche à droite. Il utilise une **file** (queue) : 1. Enfiler la racine. 2. Tant que la file n'est pas vide : défiler un nœud, le visiter, enfiler ses fils (gauche puis droit). ``` ```{code-cell} python 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 ``` ```{code-cell} python :tags: [hide-input] def dessiner_arbre(ax, noeud, x, y, dx, dy, profondeur=0, couleur_ordre=None, ordre_idx=None): """Dessine récursivement un arbre binaire sur l'axe ax.""" if noeud is None: return # Dessiner les arêtes vers les fils if noeud.gauche: ax.plot([x, x - dx], [y, y - dy], 'k-', lw=1.5, zorder=1) dessiner_arbre(ax, noeud.gauche, x - dx, y - dy, dx / 2, dy, profondeur + 1, couleur_ordre, ordre_idx) if noeud.droit: ax.plot([x, x + dx], [y, y - dy], 'k-', lw=1.5, zorder=1) dessiner_arbre(ax, noeud.droit, x + dx, y - dy, dx / 2, dy, profondeur + 1, couleur_ordre, ordre_idx) # Couleur selon l'ordre de visite couleur = '#3498db' if couleur_ordre and noeud.valeur in couleur_ordre: pos = couleur_ordre.index(noeud.valeur) t = pos / max(len(couleur_ordre) - 1, 1) couleur = plt.colormaps['plasma'](0.2 + 0.6 * t) c = plt.Circle((x, y), 0.3, color=couleur, zorder=3) ax.add_patch(c) ax.text(x, y, str(noeud.valeur), ha='center', va='center', fontsize=11, fontweight='bold', color='white', zorder=4) fig, axes = plt.subplots(1, 4, figsize=(16, 5)) titres = ['Préfixe', 'Infixe', 'Postfixe', 'Largeur'] ordres = [ parcours_prefixe(arbre.racine), parcours_infixe(arbre.racine), parcours_postfixe(arbre.racine), parcours_largeur(arbre.racine), ] for ax, titre, ordre in zip(axes, titres, ordres): ax.set_xlim(-4, 4) ax.set_ylim(-3.5, 1.5) ax.set_aspect('equal') ax.axis('off') ax.set_title(titre, fontsize=13, fontweight='bold') dessiner_arbre(ax, arbre.racine, 0, 0.8, 1.8, 1.2, couleur_ordre=ordre) ax.text(0, -3.2, '→ ' + ' '.join(map(str, ordre)), ha='center', va='center', fontsize=10, bbox=dict(boxstyle='round,pad=0.3', facecolor='#ecf0f1', edgecolor='#95a5a6')) fig.suptitle('Quatre parcours d\'un arbre binaire', fontsize=14, fontweight='bold') plt.tight_layout() plt.show() ``` ## Arbre binaire de recherche (BST) ```{prf:definition} Arbre binaire de recherche :label: definition-06-08 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. ```{code-cell} python 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()) ``` ```{prf:example} Complexité des opérations BST :label: example-06-01 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 ```{prf:remark} :label: remark-06-04 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. ``` ```{code-cell} python :tags: [hide-input] # Illustration de la dégénérescence import random def construire_bst(valeurs): bst = BST() for v in valeurs: bst.inserer(v) return bst.hauteur() tailles = [10, 50, 100, 200, 500] hauteurs_equil = [] hauteurs_trie = [] hauteurs_aleat = [] for n in tailles: valeurs = list(range(n)) hauteurs_trie.append(construire_bst(valeurs)) # pire cas random.shuffle(valeurs) hauteurs_aleat.append(construire_bst(valeurs)) # cas moyen hauteurs_equil.append(int(np.log2(n))) # borne théorique fig, ax = plt.subplots(figsize=(10, 5)) ax.plot(tailles, hauteurs_trie, 'o-', color='#e74c3c', lw=2, label='Insertions triées (pire cas) — O(n)') ax.plot(tailles, hauteurs_aleat, 's-', color='#3498db', lw=2, label='Insertions aléatoires (cas moyen) — O(log n)') ax.plot(tailles, hauteurs_equil, '^--', color='#2ecc71', lw=2, label='Borne théorique ⌊log₂ n⌋') ax.set_xlabel('Nombre de nœuds $n$') ax.set_ylabel('Hauteur de l\'arbre') ax.set_title('Dégénérescence du BST selon l\'ordre d\'insertion', fontsize=13, fontweight='bold') ax.legend() ax.grid(True, alpha=0.4) plt.tight_layout() plt.show() ``` ## 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. ```{prf:definition} Facteur d'équilibre et invariant AVL :label: definition-06-09 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**. ```{prf:definition} Rotation droite et rotation gauche :label: definition-06-10 Une **rotation droite** sur un nœud $y$ déséquilibré à gauche transforme : ``` ``` y x / \ / \ x C → A y / \ / \ A B B C ``` ```{prf:definition} Rotation gauche :label: definition-06-11 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. ```{code-cell} python 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)) ``` ```{code-cell} python :tags: [hide-input] # Comparaison des hauteurs : BST naïf vs AVL def hauteur_avl_complet(racine): return racine.hauteur if racine else -1 tailles = list(range(5, 201, 5)) h_bst_trie = [] h_avl_trie = [] h_log = [] for n in tailles: valeurs = list(range(1, n + 1)) h_bst_trie.append(construire_bst(valeurs)) racine = None for v in valeurs: racine = inserer_avl(racine, v) h_avl_trie.append(hauteur_avl_complet(racine)) h_log.append(int(np.log2(n))) fig, ax = plt.subplots(figsize=(10, 5)) ax.plot(tailles, h_bst_trie, '-', color='#e74c3c', lw=2, label='BST naïf — insertions triées (O(n))') ax.plot(tailles, h_avl_trie, '-', color='#9b59b6', lw=2, label='AVL — insertions triées (O(log n))') ax.plot(tailles, h_log, '--', color='#2ecc71', lw=1.5, label='⌊log₂ n⌋ (référence)') ax.set_xlabel('Nombre de nœuds $n$') ax.set_ylabel('Hauteur') ax.set_title('BST naïf vs AVL : hauteur avec insertions dans l\'ordre trié', fontsize=12, fontweight='bold') ax.legend() ax.grid(True, alpha=0.4) plt.tight_layout() plt.show() ``` ## Tas (Heap) ```{prf:definition} Tas binaire :label: definition-06-12 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. ``` ```{prf:remark} :label: remark-06-05 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 ```{code-cell} python 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()) ``` ```{prf:remark} :label: remark-06-06 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. ``` ```{code-cell} python 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) ``` ```{code-cell} python :tags: [hide-input] # Visualisation d'un tas-max sous forme d'arbre tas_demo = TasMax.depuis_liste([9, 8, 7, 6, 5, 4, 3, 2, 1]) data = tas_demo._data n = len(data) def pos_tas(i, n): """Calcule la position (x, y) du nœud i d'un tas affiché comme arbre.""" niveau = int(np.log2(i + 1)) largeur = 2 ** niveau pos_dans_niveau = i - (2 ** nivel - 1) if (nivel := niveau) > 0 else 0 total_noeuds_niveau = 2 ** niveau x_start = -(total_noeuds_niveau - 1) / 2 x = x_start + pos_dans_niveau y = -niveau return x, y fig, axes = plt.subplots(1, 2, figsize=(14, 5)) # --- Affichage arborescent --- ax = axes[0] ax.set_title('Tas-max (vue arborescente)', fontsize=12, fontweight='bold') ax.axis('off') positions = [] for i in range(n): niv = int(np.log2(i + 1)) nb_niv = 2 ** niv pos_niv = i - (nb_niv - 1) x = (pos_niv - (nb_niv - 1) / 2) * (8 / max(nb_niv, 1)) y = -niv * 1.5 positions.append((x, y)) for i in range(n): x, y = positions[i] g = 2 * i + 1 d = 2 * i + 2 if g < n: ax.plot([x, positions[g][0]], [y, positions[g][1]], 'k-', lw=1.5, zorder=1) if d < n: ax.plot([x, positions[d][0]], [y, positions[d][1]], 'k-', lw=1.5, zorder=1) couleur = '#e74c3c' if i == 0 else '#3498db' c = plt.Circle((x, y), 0.35, color=couleur, zorder=3) ax.add_patch(c) ax.text(x, y, str(data[i]), ha='center', va='center', fontsize=11, fontweight='bold', color='white', zorder=4) ax.set_xlim(-5, 5) ax.set_ylim(-5, 1) ax.set_aspect('equal') # --- Affichage tableau --- ax = axes[1] ax.set_title('Tas-max (représentation tableau)', fontsize=12, fontweight='bold') ax.axis('off') for i, val in enumerate(data): couleur = '#e74c3c' if i == 0 else '#3498db' rect = patches.FancyBboxPatch((i * 0.9, 0.3), 0.85, 0.85, boxstyle='round,pad=0.05', facecolor=couleur, edgecolor='white', lw=2) ax.add_patch(rect) ax.text(i * 0.9 + 0.425, 0.75, str(val), ha='center', va='center', fontsize=13, fontweight='bold', color='white') ax.text(i * 0.9 + 0.425, 0.15, str(i), ha='center', va='center', fontsize=9, color='#555555') ax.set_xlim(-0.2, n * 0.9) ax.set_ylim(-0.2, 1.4) ax.text(n * 0.9 / 2, 1.3, 'indice :', ha='center', va='center', fontsize=9, color='#555555', style='italic') fig.suptitle('Correspondance arbre ↔ tableau pour un tas', fontsize=13, fontweight='bold') plt.tight_layout() plt.show() ``` ## Implémentation Rust En Rust, les arbres binaires s'expriment naturellement avec les enums récursifs et les `Box` pour allouer les fils sur le tas (*heap*). ```rust use std::fmt; /// Nœud d'un arbre binaire de recherche générique. #[derive(Debug)] enum Arbre { Vide, Noeud { cle: T, gauche: Box>, droit: Box>, }, } impl Arbre { 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>` 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`, 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.