#Arbres et tasCopier le lien

Prérequis: tableaux et listes chaînées, piles et files (chapitres précédents), notations de complexité et coût amorti.

Objectifs:

• Énoncer l'invariant d'un tas min et le relier à sa représentation en tableau.
• Dérouler insertion et extraction à la main, case par case, en réparant l'invariant.
• Choisir entre tableau trié, BST et tas selon les opérations dominantes du programme.

#Pourquoi des arbresCopier le lien

Les structures vues jusqu'ici sont plates: un tableau, une liste chaînée, un tableau d'alvéoles. Beaucoup de données sont naturellement hiérarchiques: arborescence de fichiers, expression arithmétique, arbre de décision, tour de championnat. Mais l'arbre est aussi un outil d'organisation: quand un ordre est maintenu à l'intérieur même de la structure (arbre binaire de recherche, tas), les opérations tombent de O(n) à O(log n), ou offrent le minimum immédiatement.

Le prix de cette puissance est la hauteur h: toutes les opérations de ce chapitre coûtent O(h). Contrôler h est tout l'enjeu (complétude pour les tas, équilibrage pour les arbres de recherche, chapitre suivant).

#VocabulaireCopier le lien

• Racine: nœud sans parent, point d'entrée unique.
• Feuille: nœud sans enfants.
• Profondeur d'un nœud: nombre d'arêtes entre la racine et ce nœud.
• Hauteur d'un arbre: profondeur maximale de ses feuilles (par convention, l'arbre vide a pour hauteur −1 et la feuille isolée 0).

Un arbre binaire donne à chaque nœud au plus deux enfants, fils gauche et fils droit, distincts même s'ils sont vides (permuter les deux fils d'un arbre change l'expression qu'il encode). Un arbre binaire presque complet a tous ses niveaux remplis sauf éventuellement le dernier, lequel est rempli de gauche à droite: c'est la forme qui rend les tas représentables par un tableau, et il compte entre 2^h et 2^(h+1) − 1 nœuds, d'où h = ⌊log₂ n⌋.

#Compter les nœuds, les arcs et les feuillesCopier le lien

Deux identités reviennent dans tous les exercices de récurrence sur les arbres; les avoir en tête évite de refaire la démonstration à chaque fois.

Nombre de nœuds = nombre d'arcs + 1, pour tout arbre non vide. Démonstration par induction structurelle, en notant n(T) le nombre de nœuds et a(T) le nombre d'arcs.

• Base. L'arbre réduit à une racine: n(T) = 1 et a(T) = 0, donc 1 = 0 + 1.
• Récurrence. Soit T une racine r reliée à k sous-arbres T₁, …, T_k. Alors n(T) = 1 + Σᵢ n(Tᵢ) et a(T) = k + Σᵢ a(Tᵢ). Par hypothèse de récurrence, a(Tᵢ) = n(Tᵢ) − 1 pour chaque i, donc a(T) = k + Σᵢ n(Tᵢ) − k = Σᵢ n(Tᵢ). En reportant: n(T) = 1 + a(T).

L'intuition est immédiate une fois l'identité connue: chaque nœud sauf la racine est l'extrémité d'exactement un arc qui le relie à son parent. Il y a donc autant d'arcs que de nœuds non racines.

Hauteur et nombre de nœuds. Un arbre binaire non vide de hauteur h (avec la convention de ce chapitre: feuille isolée de hauteur 0) contient au plus 2^(h+1) − 1 nœuds, atteint par l'arbre presque complet. Preuve par récurrence sur h: pour h = 0, un seul nœud = 2¹ − 1. Pour h > 0, la racine a deux sous-arbres de hauteur au plus h − 1, donc par hypothèse au plus 2^h − 1 nœuds chacun, et le total vaut au plus 1 + 2·(2^h − 1) = 2^(h+1) − 1. Conséquence directe: tout arbre binaire à n nœuds a une hauteur au moins ⌊log₂ n⌋, et c'est exactement la borne que les tas atteignent.

#ParcoursCopier le lien

Quatre ordres de visite standards, tous en O(n): chaque nœud est visité exactement une fois.

1. Préfixe (racine, gauche, droite): sérialiser un arbre, évaluer une notation polonaise.
2. Infixe (gauche, racine, droite): rendre les clés d'un BST en ordre trié (chapitre suivant).
3. Postfixe (gauche, droite, racine): évaluation post-fixée, libération mémoire d'un arbre.
4. En largeur (niveau par niveau, de gauche à droite): exploration par distance à la racine, servie par une file.

Sur l'arbre ci-dessous:

1       502      /  \3     30   704    / \   /5   20 40 60

Implémentation minimale:

1from collections import deque2 3class Noeud:4    def __init__(self, valeur, gauche=None, droit=None):5        self.valeur = valeur6        self.gauche = gauche7        self.droit = droit8 9def infixe(n):10    if n is None:11        return12    infixe(n.gauche)13    print(n.valeur, end=' ')14    infixe(n.droit)

Les trois parcours en profondeur consomment O(h) en pile de récursion, le parcours en largeur O(l) où l est la largeur maximale d'un niveau (jusqu'à n). Garde d'implémentation: le test d'arrêt if n is None doit précéder tout accès aux champs du nœud, sinon l'arbre vide lève une erreur.

#Tas binairesCopier le lien

#L'invariantCopier le lien

Un tas min est un arbre binaire complet tel que chaque nœud est inférieur ou égal à ses deux enfants:

pour tout nœud i autre que la racine: valeur(parent(i)) ≤ valeur(i)

Conséquences immédiates: la racine porte le minimum global (accessible en O(1)); le chemin de n'importe quel nœud vers la racine est trié croissant. En revanche, rien n'ordonne deux sous-arbres frères: le tas n'est que partiellement trié, chercher un élément quelconque y est O(n). Un tas max inverse l'inégalité et expose le maximum.

#La représentation en tableauCopier le lien

La complétude rend les pointeurs inutiles: un simple tableau suffit, formant un tas compact.

Cet arbre est le tas min stocké dans le tableau [1, 3, 2, 7, 5, 6]: le niveau le plus bas est rempli de gauche à droite, sans trou. L'arithmétique des indices (tableau indexé à partir de 0):

Vérification sur l'exemple: parent(4) = 1 (5 a pour parent 3), gauche(2) = 5 (6 est le fils gauche de 2). L'invariant tient: 3 ≤ 7, 3 ≤ 5, 2 ≤ 6, 1 ≤ 3, 1 ≤ 2.

#Opérations et coûtsCopier le lien

Les deux réparations s'appellent tamisage: monter (sift-up) après une insertion, descendre (sift-down) après une extraction. Chacune parcourt au plus un chemin racine-feuille de longueur h = ⌊log₂ n⌋.

#Construction en O(n)Copier le lien

Tamiser dès la racine après chaque insertion donne O(n log n); or une construction directe fait mieux. En partant du dernier nœud interne (indice n//2 − 1) vers la racine, on tamise chaque sous-arbre sur des arbres déjà bien formés. Il y a au plus ⌈n / 2^(h+1)⌉ nœuds de hauteur h, chacun coûtant O(h):

1·(n/4) + 2·(n/8) + 3·(n/16) + … ≤ n · Σ h/2^(h+1) = n · 1 = O(n)

La série vaut exactement 1: la majorité des nœuds sont des feuilles quasi gratuites, et le coût se concentre sur les rares nœuds hauts. D'où la règle pratique: pour remplir un tas d'un coup, construire (O(n)); pour ajouter quelques éléments à la volée, inserer (O(log n) chacun).

#Implémentation en PythonCopier le lien

1class TasMin:2    """Tas min binaire représenté par un tableau indexé à partir de 0."""3 4    def __init__(self):5        self.t = []6 7    def _parent(self, i):8        return (i - 1) // 29 10    def _gauche(self, i):11        return 2 * i + 112 13    def _droit(self, i):14        return 2 * i + 2

Vérification à rejouer:

1tas = TasMin()2for x in [9, 4, 7, 1, 3]:3    tas.inserer(x)4print(tas.t)                              # [1, 3, 7, 9, 4]5print([tas.extraire_min() for _ in range(tas.taille)])6# [1, 3, 4, 7, 9]: les extractions rendent les éléments en ordre croissant

Le sift-down compare au plus petit des deux enfants (et pas à l'enfant gauche systématiquement): descendre vers le plus grand laisserait le parent au-dessus d'un enfant plus petit et l'invariant serait cassé dès l'échange.

#Tri par tasCopier le lien

La trace ci-dessus est déjà un tri: construire un tas max, puis échanger n − 1 fois la racine (maximum courant) avec la dernière case non triée et tamiser. Résultat: O(n log n) garanti dans le pire cas, en place, O(1) de mémoire annexe, mais non stable et peu amical pour le cache (la numérotation saute entre niveaux). C'est le tri de repli quand le tri rapide dégénère et que la mémoire interdit le tri fusion.

#Files de priorité et heapqCopier le lien

Le tas est l'implémentation standard de la file de priorité: insérer un élément avec une priorité, retirer à chaque fois l'élément le plus prioritaire. La bibliothèque Python heapq fournit exactement cela (tas min):

1import heapq2 3t = [9, 4, 7, 1, 3]4heapq.heapify(t)              # construction en O(n), en place5heapq.heappush(t, 2)          # insertion6print(t[0])                   # 1: le minimum est toujours en tête, consultation O(1)7print(heapq.heappop(t))       # 1: extraction du minimum8print(heapq.nsmallest(3, t))  # [2, 3, 4]: top-K en O(n log k)

Pour une file max (priorité = valeur élevée), stocker les négatifs: heappush(t, -priorite) puis −heappop(t). Consommateurs typiques: ordonnanceur de processus, file d'événements d'une simulation, Dijkstra et Prim (plus proche sommet), fusion de k flux triés, top-K sur un flux sans tout stocker.

#Arbres équilibrés, aperçuCopier le lien

Un BST laissé à lui-même peut dégénérer en liste (hauteur n − 1, opérations O(n)). Les variantes équilibrées réparent l'arbre à chaque insertion pour garantir une hauteur logarithmique:

• AVL: la différence de hauteur entre sous-arbres gauche et droit de chaque nœud reste ≤ 1; hauteur garantie ≤ 1,44 log₂ n; rééquilibrage par rotations dès qu'un déséquilibre apparaît.
• Rouge-noir: chaque nœud porte une couleur et aucun chemin racine-feuille n'est plus de deux fois plus long qu'un autre; hauteur ≤ 2 log₂ n; rotations et recoloriations, moins strict qu'AVL donc moins de rééquilibrages.
• B-arbres: nœuds à plusieurs clés et fort facteur de branchement, pensés pour le disque (une lecture page par niveau); ce sont les index des bases de données et de nombreux systèmes de fichiers.

Ces garanties sont détaillées au chapitre suivant sur les arbres binaires de recherche.

#Exercice 1: tracer insertion et extractionCopier le lien

Soit un tas min vide. Insérez dans l'ordre 9, 4, 7, 1, 3, puis effectuez deux extractions du minimum. Donnez le tableau après chaque étape clé.

Correction (tamisages montrés):

1. 9 seul: [9].
2. Insérer 4: [9, 4], le parent de l'indice 1 vaut 9 > 4, échange: [4, 9].
3. Insérer 7: [4, 9, 7], parent 4 ≤ 7, aucun échange.
4. Insérer 1: [4, 9, 7, 1] puis deux remontées (9 > 1 puis 4 > 1): [1, 4, 7, 9].
5. Insérer 3: [1, 4, 7, 9, 3], l'indice 4 a pour parent l'indice 1 (4 > 3), échange, puis 1 ≤ 3 arrêt: [1, 3, 7, 9, 4].
6. Extraire le min (1): le dernier (4) passe en racine [4, 3, 7, 9], descente vers le plus petit enfant 3: [3, 4, 7, 9].
7. Extraire le min (3): le dernier (9) passe en racine [9, 4, 7], descente vers 4: [4, 9, 7].

À contrôler: votre implémentation doit produire exactement ces états intermédiaires. Sinon, presque toujours le sift-down qui part vers l'enfant gauche sans comparer au droit.

#Exercice 2: tas valide mais non triéCopier le lien

Le tableau [1, 3, 2, 7, 5, 6] est-il un tas min valide? Est-il trié? Réciproquement, tout tableau trié croissant est-il un tas min valide?

Correction:

1. Tas valide: vérifier l'invariant parent(i) ≤ t[i] pour i de 1 à 5. parent(1) = 0: 1 ≤ 3; parent(2) = 0: 1 ≤ 2; parent(3) = 1: 3 ≤ 7; parent(4) = 1: 3 ≤ 5; parent(5) = 2: 2 ≤ 6. Oui, tas min valide (c'est l'arbre visualisé plus haut).
2. Non trié: 3 > 2 en positions 1 et 2. Un tas n'ordonne que le long des chemins racine-feuille, jamais entre sous-arbres frères.
3. Tout tableau trié croissant est un tas min: pour tout i ≥ 1, parent(i) < i donc t[parent(i)] ≤ t[i]. Oui.

Moralité: le tas est un ordre partiel commode pour un minimum immédiat; si vous avez besoin du tri complet ou de la recherche par clé, ce n'est pas la bonne structure.

#Mini-quizCopier le lien