Arbres de recherche et files de priorité

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

définir un arbre binaire, sa profondeur et sa hauteur, et démontrer l'encadrement qui lie la hauteur au nombre de nœuds;
écrire la recherche, l'insertion et les trois cas de la suppression dans un arbre binaire de recherche, et expliquer pourquoi le parcours infixe en restitue les clés triées;
expliquer pourquoi le même ensemble de clés inséré dans un autre ordre donne un peigne de hauteur $n - 1$ , et démontrer qu'un arbre AVL, lui, reste de hauteur $O (lo g n)$ ;
appliquer les quatre cas de rotation d'un AVL et reconnaître lequel s'applique à partir des facteurs d'équilibre;
implémenter un tas binaire dans un tableau, démontrer la correction de sift_down et le coût $O (n)$ de la construction de Floyd;
utiliser une file de priorité comme une interface — celle dont les chapitres 7 et 8 auront besoin — et dire ce que heapq offre et ce qu'il n'offre pas.

Pourquoi un arbre

Deux structures qui ne savent chacune faire qu'une moitié du travail

Vous disposez, à la fin du chapitre 4, de deux manières de ranger un ensemble de clés, et aucune des deux ne fait tout.

Un tableau trié répond vite aux questions d'ordre. La recherche dichotomique y coûte $Θ (lo g n)$ comparaisons dans le pire des cas — dix comparaisons pour mille éléments, vingt pour un million, comme le rappelle le tableau des ordres de grandeur du chapitre 1 — et l'on y lit sans effort le minimum, le maximum, le successeur d'une clé ou toutes les clés comprises entre deux bornes. Mais insérer y coûte $Θ (n)$ écritures dans le pire des cas: il faut décaler d'un cran tout ce qui suit le point d'insertion. Un tableau trié est une structure pour des données qui ne bougent plus.

Une table de hachage fait exactement le contraire. Sous l'hypothèse de hachage uniforme simple, elle insère, supprime et recherche en $Θ (1)$ en moyenne, ce qui est imbattable — et elle est parfaitement incapable de répondre à «quelle est la plus petite clé?» ou «donnez-moi les clés entre 27 et 43» autrement qu'en parcourant tout, en $Θ (m + n)$ . La fonction de hachage a détruit l'ordre, et c'était même le but: une bonne fonction de hachage envoie deux clés voisines dans deux paquets sans rapport.

Il reste la liste chaînée triée, qui insère en $Θ (1)$ une fois qu'on tient la bonne case, mais qui ne sait pas la trouver autrement qu'en $Θ (n)$ , faute d'accès direct: on ne dichotomise pas une liste chaînée.

Structure	Recherche	Insertion	Minimum	Clés dans un intervalle
Tableau trié	$Θ (lo g n)$	$Θ (n)$	$Θ (1)$	$Θ (lo g n + k)$
Liste chaînée triée	$Θ (n)$	$Θ (n)$	$Θ (1)$

La dernière ligne est le programme de ce chapitre, et $k$ y désigne le nombre de clés effectivement renvoyées. Aucune case n'y est en $Θ (1)$ , et c'est le prix à payer: l'arbre de recherche équilibré n'est le meilleur sur aucune opération prise isolément, il est seulement le seul à n'être mauvais sur aucune. C'est la structure de compromis par excellence, et c'est pour cela qu'elle est partout — dans les index d'une base de données, dans les std::map et les TreeMap, dans les systèmes de fichiers.

Le vocabulaire des arbres binaires

Cette définition est récursive, et c'est sa qualité principale: presque tout ce que nous démontrerons sur les arbres se démontrera par récurrence sur la structure, en supposant le résultat acquis sur les deux sous-arbres. La récursivité du chapitre 9 d'Introduction à la programmation trouve ici son terrain naturel.

Le nombre de nœuds et la hauteur sont liés, et cet encadrement est la raison d'être de tout le chapitre.

Démonstration. Commençons par borner le nombre de nœuds situés à une profondeur donnée. Notons $n_{d}$ le nombre de nœuds de profondeur $d$ . On a $n_{0} = 1$ , puisqu'il y a une racine et une seule. Et $n_{d + 1} \leq 2 n_{d}$ , car chaque nœud de profondeur est l'enfant gauche ou l'enfant droit d'un unique nœud de profondeur , et chacun de ces derniers n'a que deux places à offrir. Par récurrence immédiate, pour tout .

Majoration. Les profondeurs vont de $0$ à $h$ par définition de la hauteur, donc

n = d = 0 \sum h n_{d} \leq d = 0 \sum h 2^{d} = 2^{h + 1} - 1,

la dernière égalité étant la somme géométrique rappelée en annexe A. L'égalité a lieu exactement quand tous les niveaux sont pleins, c'est-à-dire pour un arbre parfait.

Minoration. Pour chaque $d$ entre $0$ et $h$ , il existe au moins un nœud de profondeur $d$ : en effet, il existe par définition un nœud de profondeur $h$ , et le chemin qui le relie à la racine traverse un nœud de chaque profondeur intermédiaire. Donc $n_{d} \geq 1$ pour $0 \leq d \leq h$ , et . L'égalité a lieu quand chaque niveau ne porte qu'un nœud, c'est-à-dire pour une chaîne.

Passage à (5.2). La majoration $n \leq 2^{h + 1} - 1$ s'écrit $2^{h + 1} \geq n + 1$ , donc $h + 1 \geq lo g_{2} (n + 1)$ ; comme est entier, . La minoration donne directement .

La relation (5.2) est à retenir telle quelle, parce que c'est elle qui fixe l'enjeu. La borne de gauche dit qu'aucun arbre binaire de $n$ nœuds ne peut être plus plat que $⌈ lo g_{2} (n + 1)⌉ - 1$ : pour $n = 7$ cela fait $2$ , pour $n = 1000$ cela fait $9$ , pour un million . La borne de droite dit qu'un arbre binaire peut être aussi profond qu'une liste chaînée. Tout l'art consiste à rester près de la première.

Question 5.1

Un arbre binaire a 1000 nœuds. Que pouvez-vous affirmer sur sa hauteur, comptée en arêtes?

Un arbre en Python

Nous représentons un nœud par un petit objet à trois attributs, comme au chapitre 4 pour les maillons d'une liste chaînée. L'arbre vide est None, ce qui rend les cas de base agréables à écrire.

class Noeud:
    """Un noeud d'arbre binaire: une cle et deux sous-arbres, eventuellement None."""

    def __init__(self, cle, gauche=None, droit=None):
        self.cle = cle
        self.gauche = gauche
        self.droit = droit

Les deux fonctions les plus utiles se lisent directement sur la définition récursive:

def hauteur(racine):
    """Hauteur en aretes; -1 pour l'arbre vide."""
    if racine is None:
        return -1
    return 1 + max(hauteur(racine.gauche), hauteur(racine.droit))


def taille(racine):
    """Nombre de noeuds."""
    if racine is None:
        return 0
    return 1 + taille(racine.gauche) + taille(racine.droit)

Chacune visite chaque nœud exactement une fois et fait un travail constant par nœud: le coût est $Θ (n)$ appels récursifs, quelle que soit la forme de l'arbre. La mémoire, elle, dépend de la forme: la pile d'appels descend jusqu'à la profondeur maximale, donc $Θ (h)$ — un détail sans conséquence sur un arbre équilibré et une cause d'exception RecursionError sur une chaîne de dix mille nœuds, puisque la limite de récursion de Python est de mille appels par défaut.

L'arbre binaire de recherche

La propriété d'ordre

Lisez la condition une seconde fois: elle porte sur tout le sous-arbre, pas seulement sur les deux enfants. C'est l'erreur classique, et elle est indétectable sur un petit dessin: l'arbre de racine $38$ , d'enfant gauche $27$ et de petit-fils droit $40$ satisfait la condition locale en chaque nœud pris isolément — $27 < 38$ , et $40 > 27$ — sans être un ABR, puisque $40$ se trouve à gauche de $38$ tout en lui étant supérieur. Une recherche de $40$ partirait à droite et ne le trouverait jamais.

Rechercher

La recherche est le mode d'emploi de la propriété d'ordre: à chaque nœud, la comparaison élimine un sous-arbre entier.

def recherche(racine, cle):
    """Renvoie le noeud portant cle, ou None. Version iterative."""
    courant = racine
    while courant is not None:
        if cle == courant.cle:
            return courant
        courant = courant.gauche if cle < courant.cle else courant.droit
    return None

L'opération barométrique est la comparaison de clés: la boucle en fait une par nœud visité, et elle visite les nœuds d'un chemin descendant partant de la racine. Un tel chemin a au plus $h + 1$ nœuds, donc la recherche coûte au plus $h + 1$ comparaisons dans le pire des cas. Tout le sort de la structure tient dans ce $h$ : sur un arbre équilibré il vaut $Θ (lo g n)$ et la recherche est dichotomique; sur un peigne il vaut $n - 1$ et la recherche est séquentielle.

Le minimum et le maximum se lisent tout aussi directement: la plus petite clé est au bout de la branche entièrement gauche, la plus grande au bout de la branche entièrement droite.

def minimum(racine):
    """Le noeud de plus petite cle; l'arbre doit etre non vide."""
    courant = racine
    while courant.gauche is not None:
        courant = courant.gauche
    return courant

Coût: autant d'itérations que la branche gauche a d'arêtes, donc au plus $h$ , et zéro comparaison de clés — on ne compare rien, on suit des pointeurs. Une table de hachage ne sait pas faire cela du tout.

Insérer

L'insertion suit exactement le chemin qu'aurait suivi une recherche infructueuse, et accroche le nouveau nœud à la place vide où cette recherche s'est arrêtée. Le nouveau nœud est donc toujours une feuille.

def insere(racine, cle):
    """Insere cle et renvoie la nouvelle racine du sous-arbre."""
    if racine is None:
        return Noeud(cle)
    if cle < racine.cle:
        racine.gauche = insere(racine.gauche, cle)
    elif cle > racine.cle:
        racine.droit = insere(racine.droit, cle)
    return racine                      # cle deja presente: rien a faire

Une insertion fait au plus $h + 1$ comparaisons et une seule écriture de pointeur. Construire un arbre de $n$ clés par insertions successives coûte donc au plus $\sum_{i = 0}^{n - 1} (h_{i} + 1)$ comparaisons, où $h_{i}$ est la hauteur au moment de la -ième insertion — et c'est précisément cette somme qui peut valoir ou selon l'ordre dans lequel les clés arrivent.

Exemple 5.1 · L'ABR témoin du cours, construit clé par clé

Tout ce chapitre utilise l'arbre binaire de recherche témoin du cours: le tableau témoin [38, 27, 43, 3, 9, 82, 10] inséré dans cet ordre. Le programme affiche, après chaque insertion, les clés niveau par niveau et la hauteur courante.

from collections import deque


def niveaux(racine):
    """Les cles par profondeur croissante, pour lire la forme de l'arbre."""
    file = deque([(racine, 0)])
    par_niveau = {}
    while file:
        noeud, profondeur = file.popleft()
        if noeud

Le peigne, et pourquoi il faut équilibrer

Reprenons les sept clés du tableau témoin, mais insérons-les triées: $3$ , puis $9$ , puis $10$ , puis $27$ , $38$ , $43$ , $82$ . Chaque nouvelle clé est plus grande que toutes les précédentes; la recherche infructueuse qui précède son insertion part donc à droite à chaque nœud et descend jusqu'au bout de la branche droite. On obtient une chaîne de sept nœuds, de hauteur $6 = n - 1$ : c'est la borne droite de (5.2), atteinte. La structure est une liste chaînée, avec en prime un pointeur gauche toujours nul qui ne sert à rien.

Ce n'est pas un cas d'école. Des clés qui arrivent déjà triées, c'est le cas normal, pas le cas pathologique: des identifiants attribués par ordre croissant, des horodatages, un fichier de journal relu dans l'ordre, le résultat d'une requête déjà triée que l'on réindexe. Un ABR naïf est donc une structure dont le pire des cas est le cas le plus fréquent, ce qui est la pire combinaison possible.

Le coût de construction suit: insérer $n$ clés triées coûte $\sum_{i = 0}^{n - 1} i = n (n - 1) /2$ comparaisons, soit $Θ (n^{2})$ , là où le même ensemble inséré dans un ordre favorable en coûte $Θ (n lo g n)$ . Pour , c'est comparaisons contre une dizaine de milliers.

L'explorateur ci-dessous rend la chose palpable. Faites glisser le nombre de clés, puis changez l'ordre d'insertion sans y toucher: l'ensemble inséré est le même, la hauteur minimale atteignable est la même, et la hauteur obtenue passe du simple au triple.

Explorateur 5.1 · Insérer des clés et regarder la hauteur

Les dix clés sont toujours les mêmes et, pour un nombre de clés donné, l’ensemble inséré est identique dans les quatre ordres: seul l’ordre d’insertion change. Faites glisser le premier curseur pour insérer les clés une à une, puis changez d’ordre sans y toucher. La hauteur minimale affichée ne bouge pas — elle ne dépend que du nombre de clés —, tandis que la hauteur réelle passe du simple au triple. L’ordre médian, qui insère toujours la médiane de ce qui reste, atteint la borne pour tout n; l’ordre croissant donne le peigne.

Nombre de clés insérées n7

Ordre d’insertiontémoin du cours

Hauteur obtenue

4arêtes

Hauteur minimale ⌈log₂(n+1)⌉ − 1

2arêtes

Écart à la borne

Recherche la plus chère

5comparaisons

Comparaisons en moyenne (clé présente)

2,86

Dernière clé insérée

Question 5.2

On insère les entiers 1, 2, 3, …, 1000 dans cet ordre dans un arbre binaire de recherche sans équilibrage. Combien de comparaisons de clés l'ensemble de ces insertions coûte-t-il au total?

Question 5.3

Construisez l'ABR témoin du cours et mesurez-le. La classe Noeud et la fonction insere sont fournies; écrivez hauteur(racine), puis affichez sur une ligne, séparées par une espace, la hauteur en arêtes de l'ABR témoin puis celle du peigne obtenu avec les mêmes clés triées.

abr_temoin.py

Les parcours

Un arbre n'est pas ordonné dans la mémoire: le pointeur gauche d'un nœud et son pointeur droit n'ont aucune raison de pointer vers des cases voisines. Pour énumérer les clés il faut donc choisir un parcours, et le choix n'est pas anodin.

def infixe(racine, sortie=None):
    """Les cles, sous-arbre gauche d'abord, puis la racine, puis le sous-arbre droit."""
    if sortie is None:
        sortie = []
    if racine is not None:
        infixe(racine.gauche, sortie)
        sortie.append(racine.cle)
        infixe(racine.droit, sortie)
    return sortie

Chacun de ces parcours visite chaque nœud une fois et une seule et y fait un travail constant: le coût est $Θ (n)$ , et la mémoire $Θ (h)$ pour les trois parcours en profondeur (la pile d'appels) contre $Θ (n)$ dans le pire des cas pour le parcours en largeur (la file peut contenir tout le dernier niveau, soit jusqu'à environ $n /2$ nœuds).

Le parcours infixe a, sur un ABR, une propriété qui à elle seule justifie la structure.

Démonstration. Par récurrence sur le nombre $n$ de nœuds de $A$ .

Cas de base. Si $n = 0$ , le parcours n'énumère rien, et la suite vide est triée.

Hérédité. Soit $n \geq 1$ et supposons le résultat acquis pour tout ABR de moins de $n$ nœuds. Notons $x$ la racine de $A$ , $G$ son sous-arbre gauche et $D$ son sous-arbre droit. Ces deux sous-arbres sont eux-mêmes des ABR — la propriété d'ordre est héréditaire, puisqu'elle est demandée en chaque nœud — et ils comptent chacun moins de $n$ nœuds, $x$ n'appartenant à aucun des deux. L'hypothèse de récurrence s'applique donc: le parcours infixe de $G$ produit une suite strictement croissante $u_{1} < \dots < u_{p}$ formée exactement des clés de , et celui de une suite strictement croissante formée exactement des clés de .

Par construction, le parcours infixe de $A$ produit la concaténation

u_{1}, \dots, u_{p}, x, v_{1}, \dots, v_{q} .

Il reste à vérifier que cette concaténation est strictement croissante. Les deux blocs le sont déjà; il suffit donc de contrôler les deux jonctions. À la première, $u_{p}$ est une clé de $G$ , donc $u_{p} < x$ par la propriété d'ordre en $x$ . À la seconde, $v_{1}$ est une clé de , donc pour la même raison. La suite complète est donc strictement croissante, et elle contient exactement les clés de , à savoir celles de , celle de et celles de .

Remarquez ce que la démonstration a utilisé: uniquement la propriété d'ordre en la racine, et l'hérédité de cette propriété. C'est le schéma de toutes les démonstrations de ce chapitre.

Exemple 5.2 · Les quatre parcours de l'ABR témoin

racine = construit([38, 27, 43, 3, 9, 82, 10])
print("infixe  ", infixe(racine))
print("prefixe ", prefixe(racine))
print("suffixe ", suffixe(racine))
print("largeur ", largeur(racine))

infixe   [3, 9, 10, 27, 38, 43, 82]
prefixe  [38, 27, 3, 9, 10, 43, 82]
suffixe  [10, 9, 3, 27, 82, 43, 38]
largeur  [38, 27, 43, 3, 82, 9, 10]

Question 5.4

Un parcours suffixe (gauche, droite, racine) est lancé sur l'ABR témoin du cours, celui obtenu en insérant 38, 27, 43, 3, 9, 82, 10. Remettez les sept clés dans l'ordre où il les énumère.

Glissez les éléments pour les mettre dans le bon ordre

Question 5.5

Écrivez le parcours infixe et servez-vous-en pour trier. Le programme doit afficher les clés de l'ABR témoin dans l'ordre croissant, sur une ligne, séparées par une espace. Les fonctions de tri de Python sont interdites: c'est l'arbre qui trie.

parcours_infixe.py

La suppression, et ses trois cas

Rechercher et insérer se ressemblent. Supprimer est la seule opération de l'ABR qui demande une vraie disjonction de cas, parce qu'il faut retirer un nœud sans casser la propriété d'ordre et sans détacher ses descendants.

Soit $x$ le nœud à supprimer. Trois cas, selon son nombre d'enfants.

Cas 1 — $x$ est une feuille. On le détache, point final. Aucun descendant à recaser, et la propriété d'ordre ne peut pas être violée par une suppression de feuille: retirer des éléments d'un sous-arbre ne compromet aucune des inégalités, qui sont toutes de la forme «toutes les clés de tel sous-arbre sont inférieures à telle clé».

Cas 2 — $x$ n'a qu'un enfant. On remplace $x$ par cet enfant, c'est-à-dire qu'on fait pointer le parent de $x$ directement sur lui. Toutes les clés de ce sous-arbre étaient déjà du bon côté de tous les ancêtres de $x$ — elles étaient dans le sous-arbre de $x$ —, donc elles y restent.

Cas 3 — $x$ a deux enfants. On ne peut pas le détacher: ses deux sous-arbres ne tiennent pas dans la place unique qu'il laisse. On ne supprime donc pas le nœud, on remplace sa clé par celle de son successeur — la plus petite clé strictement supérieure, c'est-à-dire le minimum de son sous-arbre droit — puis on supprime récursivement ce successeur du sous-arbre droit. Et cette seconde suppression, elle, retombe toujours dans le cas 1 ou le cas 2: le minimum d'un sous-arbre n'a par définition pas d'enfant gauche.

def supprime(racine, cle):
    """Supprime cle et renvoie la nouvelle racine du sous-arbre."""
    if racine is None:
        return None
    if cle < racine.cle:
        racine.gauche = supprime(racine.gauche, cle)
    elif cle > racine.cle:
        racine.droit = supprime(racine.droit, cle)
    else:
        if racine.gauche is None:          # cas 1 et cas 2
            return racine.droit
        if racine.droit is

Le coût est celui d'une descente, plus, dans le cas 3, celui d'une seconde descente pour trouver et retirer le successeur: au plus $2 (h + 1)$ comparaisons, donc $Θ (h)$ . Les deux premières lignes du bloc else traitent d'un seul geste les cas 1 et 2, puisque renvoyer racine.droit quand le sous-arbre gauche est vide couvre aussi bien la feuille (racine.droit vaut None) que le nœud à un seul enfant.

Exemple 5.3 · Les trois cas de suppression sur l'ABR témoin

Partons chaque fois de l'ABR témoin intact et supprimons une clé choisie pour illustrer un cas. Le programme affiche le parcours préfixe, qui décrit la forme de l'arbre, et le parcours infixe, qui doit rester trié.

for cle in [82, 43, 38]:
    racine = construit([38, 27, 43, 3, 9, 82, 10])
    racine = supprime(racine, cle)
    print(cle, "prefixe", prefixe(racine),

Le successeur ou le prédécesseur: choisir toujours le même déséquilibre

Rien n'oblige à prendre le successeur dans le cas 3; le prédécesseur — le maximum du sous-arbre gauche — conviendrait tout aussi bien, par symétrie. Mais choisir toujours le successeur déséquilibre l'arbre à la longue: chaque suppression retire un nœud du sous-arbre droit et jamais du gauche, et une observation classique, vérifiée expérimentalement de longue date, montre qu'une alternance prolongée d'insertions et de suppressions asymétriques fait croître la profondeur moyenne d'un ABR non équilibré bien au-delà des $Θ (lo g n)$ attendus. La parade usuelle — alterner successeur et prédécesseur — est une bricole; la vraie réponse est l'équilibrage de la section suivante. Notez aussi que la version ci-dessus écrase la clé du nœud au lieu de le déplacer: si un code extérieur détenait une référence sur ce nœud, il regarde maintenant une autre clé. Une implémentation de bibliothèque déplace le nœud lui-même.

Question 5.6

Dans l'ABR témoin du cours, on supprime la racine 38 par la méthode du successeur. Que devient la racine, et pourquoi la seconde suppression est-elle facile?

Équilibrer: les arbres AVL

Le peigne a une cause précise: rien, dans l'insertion, ne surveille la forme de l'arbre. L'idée des arbres AVL — Adelson-Velsky et Landis, 1962, les premiers arbres équilibrés de l'histoire — est d'ajouter une contrainte locale, vérifiable en chaque nœud en temps constant, et assez forte pour borner la hauteur globale.

La contrainte est étonnamment faible: elle autorise un sous-arbre à être plus haut que son frère, simplement pas de plus d'une arête. On pourrait craindre qu'une telle liberté, accumulée sur $h$ niveaux, laisse l'arbre dériver. Le théorème suivant dit que non.

Démonstration. Nous raisonnons dans l'autre sens: au lieu de majorer la hauteur à $n$ fixé, minorons le nombre de nœuds à hauteur fixée. Notons $N (h)$ le nombre minimal de nœuds d'un arbre AVL de hauteur $h$ . Un arbre AVL de hauteur $h$ comportant $n$ nœuds vérifie donc $n \geq N (h)$ , et il suffira de minorer $N (h)$ .

Une récurrence sur $N$ . Un arbre AVL de hauteur $0$ est une feuille seule, donc $N (0) = 1$ . Un arbre AVL de hauteur $1$ a une racine et au moins un enfant, donc $N (1) = 2$ . Soit maintenant $h \geq 2$ et $A$ un arbre AVL de hauteur $h$ ayant le moins de nœuds possible. Sa racine a deux sous-arbres et , dont l'un au moins est de hauteur — sinon ne serait pas de hauteur . Disons . La contrainte AVL en la racine impose alors . De plus et sont eux-mêmes des arbres AVL, donc ils comptent respectivement au moins et nœuds. En comptant la racine:

N (h) = 1 + N (h - 1) + N (h - 2), N (0) = 1, N (1) = 2. (5.3)

L'égalité, et non seulement l'inégalité, vaut parce que la borne est atteinte: l'arbre formé d'une racine, d'un arbre minimal de hauteur $h - 1$ à gauche et d'un arbre minimal de hauteur $h - 2$ à droite est bien un AVL de hauteur $h$ , et il a exactement ce nombre de nœuds.

La borne grossière. Comme $N$ est croissante, $N (h - 1) \geq N (h - 2)$ , donc $N (h) > 2 N (h - 2)$ . En itérant depuis $N (0) = 1$ et , on obtient pour tout . Alors , d'où , c'est-à-dire . La hauteur est donc au plus le double de l'optimum: c'est déjà , et c'est tout ce dont le reste du chapitre a besoin.

La borne fine. Montrons par récurrence forte que $N (h) \geq φ^{h}$ , où $φ$ est l'unique racine positive de $φ^{2} = φ + 1$ , soit $φ \approx 1, 618$ . Pour , . Pour , . Soit et supposons l'inégalité acquise pour et . Alors

N (h) = 1 + N (h - 1) + N (h - 2) \geq 1 + φ^{h - 1} + φ^{h - 2} = 1 + φ^{h - 2} (φ + 1) = 1 + φ^{h} \geq φ^{h},

où l'on a utilisé $φ + 1 = φ^{2}$ . De $n \geq N (h) \geq φ^{h}$ on tire $h \leq lo g_{φ} n$ , et le changement de base donne , puisque .

Les rotations

Reste à maintenir la contrainte. Après une insertion, seuls les nœuds situés sur le chemin de la racine à la nouvelle feuille ont pu voir leur facteur d'équilibre changer, et ce chemin compte au plus $h + 1$ nœuds. On remonte donc ce chemin en recalculant les hauteurs, et dès qu'un nœud $x$ sort de la contrainte — $∣ b (x)∣ = 2$ —, on le réarrange par une rotation.

def rotation_droite(y):
    """y penche a gauche: son enfant gauche x remonte."""
    x = y.gauche
    y.gauche = x.droit
    x.droit = y
    maj_hauteur(y)                 # y d'abord: il est devenu l'enfant
    maj_hauteur(x)
    return x                       # la nouvelle racine du sous-arbre


def rotation_gauche(x):
    """x penche a droite: son enfant droit y remonte."""
    y = x.droit
    x.droit = y.gauche
    y.gauche = x
    maj_hauteur(x)
    maj_hauteur(y)
    return

Une rotation modifie trois pointeurs et deux hauteurs: son coût est $Θ (1)$ , indépendamment de la taille des sous-arbres déplacés, qui ne sont jamais parcourus. C'est cette gratuité qui rend l'équilibrage abordable.

Les quatre cas

Soit $x$ le nœud déséquilibré le plus profond sur le chemin d'insertion. Quatre configurations, nommées d'après la direction des deux premiers pas menant de $x$ vers la feuille insérée.

Cas	$b (x)$	Facteur de l'enfant du côté lourd	Correction
Gauche-gauche	$+ 2$	$+ 1$	rotation droite sur $x$
Droite-droite	$- 2$	$- 1$	rotation gauche sur $x$
Gauche-droite	$+ 2$	$- 1$	rotation gauche sur l'enfant gauche, puis rotation droite sur

Les deux premiers cas sont symétriques l'un de l'autre, les deux derniers aussi: il n'y a donc que deux situations à comprendre, la simple et la double. Et la raison pour laquelle la double est nécessaire tient en une phrase: une rotation simple appliquée à un cas gauche-droite échange les deux déséquilibres sans les résoudre — l'arbre penche alors de l'autre côté, toujours de deux crans. La première rotation sert à ramener le cas gauche-droite à un cas gauche-gauche, que la seconde règle.

L'insertion complète tient alors en quelques lignes, à condition de se rappeler qu'elle renvoie la racine du sous-arbre, laquelle peut avoir changé.

def insere_avl(racine, cle):
    """Insertion dans un AVL: insertion d'ABR, puis reequilibrage en remontant."""
    if racine is None:
        return Noeud(cle)
    if cle < racine.cle:
        racine.gauche = insere_avl(racine.gauche, cle)
    elif cle > racine.cle:
        racine.droit = insere_avl(racine.droit, cle)
    else:
        return racine
    return equilibre(racine)


def equilibre(x):
    """Remet un noeud dans la contrainte AVL; renvoie la racine du sous-arbre."""
    maj_hauteur(x)

Le coût d'une insertion AVL: au plus $h + 1$ comparaisons pour descendre, au plus $h + 1$ appels à equilibre pour remonter, et au plus une rotation simple ou double au total. Ce dernier point mérite d'être souligné: après une insertion, la première rotation effectuée en remontant rétablit la hauteur que le sous-arbre avait avant l'insertion, de sorte qu'aucun ancêtre n'est plus déséquilibré. Une insertion AVL coûte donc $O (lo g n)$ comparaisons et $O (1)$ rotations. La suppression, elle, peut en exiger jusqu'à $O (lo g n)$ : le rééquilibrage d'un sous-arbre y diminue parfois sa hauteur, ce qui propage le problème vers la racine.

Exemple 5.4 · Le tableau témoin inséré dans un AVL

Insérons les sept clés du tableau témoin, dans l'ordre du cours, dans un AVL. Le programme signale les rotations et affiche les niveaux.

insere 38 : aucune rotation, hauteur 0, niveaux {0: [38]}
insere 27 : aucune rotation, hauteur 1, niveaux {0: [38], 1: [27]}
insere 43 : aucune rotation, hauteur 1, niveaux {0: [38], 1: [27, 43]}
insere  3 : aucune rotation, hauteur 2, niveaux {0: [38], 1: [27, 43], 2: [3]}
insere  9 : gauche-droite en 27, hauteur 2, niveaux {0: [38], 1: [9, 43], 2: [3, 27]}
insere 82 : aucune rotation, hauteur 2, niveaux {0: [38], 1: [9, 43], 2: [3, 27, 82]}
insere 10 : aucune rotation, hauteur 3, niveaux {0: [38], 1: [9, 43], 2: [3, 27, 82], 3: [10]}

Une seule rotation dans toute la construction, et c'est une rotation double, celle de la figure 5.2: à l'arrivée de $9$ , le nœud $27$ se retrouve avec un sous-arbre gauche de hauteur $1$ (la chaîne $3 \to 9$ ) et un sous-arbre droit vide, donc $b (27) = 1 - (- 1) = 2$ ; et son enfant gauche penche à droite, . Cas gauche-droite. On tourne à gauche sur , puis à droite sur , et remonte avec et pour enfants.

AVL n'est pas la seule réponse, et pas toujours la meilleure

Ce chapitre traite les AVL parce que leur démonstration de hauteur est la plus courte et la plus instructive. Ce ne sont pas les arbres équilibrés les plus employés. Les arbres rouge-noir relâchent la contrainte — la plus longue branche vaut au plus deux fois la plus courte, soit $h \leq 2 lo g_{2} (n + 1)$ — et font donc moins de rotations à l'insertion, ce qui les rend préférables quand les écritures dominent; ce sont eux que l'on trouve dans les bibliothèques standard de C++ et de Java. Les AVL, plus rigides, restent plus plats et donc meilleurs quand les lectures dominent. Les arbres B du chapitre sur les bases de données, enfin, abandonnent le degré 2: un nœud y porte des centaines de clés pour tenir dans un bloc disque. Aucune de ces structures ne rend les autres obsolètes; elles optimisent des coûts différents, et l'honnêteté impose de dire lequel.

Le tas binaire

Un arbre de recherche fait beaucoup de choses. Souvent, on en veut une seule: le plus petit élément, encore et encore, tandis que de nouveaux éléments arrivent. C'est le besoin d'un ordonnanceur de tâches, d'une simulation à événements discrets, de l'algorithme de Dijkstra au chapitre 7 et de celui de Prim au chapitre 8. Pour ce besoin-là, une structure beaucoup plus simple suffit, et elle n'a même pas besoin de pointeurs.

Deux conséquences de la complétude méritent d'être dites tout de suite. D'abord, un arbre complet de $n$ nœuds est de hauteur exactement $⌊ lo g_{2} n ⌋$ : c'est la borne gauche de (5.2), atteinte par construction, et elle est garantie sans aucun effort d'équilibrage. Ensuite, la représentation en tableau supprime les pointeurs, ce qui divise la mémoire par trois et rend les accès contigus — le modèle RAM du chapitre 1 ne voit pas cette différence, votre processeur si.

La propriété de tas est plus faible que celle d'un ABR, et c'est délibéré. Dans un tas, on ne sait pas chercher une clé quelconque autrement qu'en parcourant tout le tableau, en $Θ (n)$ : rien ne dit si une clé donnée est à gauche ou à droite. Tout ce qu'on sait, par transitivité de la propriété locale le long d'un chemin descendant, c'est que la racine est le minimum de tout le tas. C'est peu, et c'est exactement ce qu'on demandait.

Remonter: `sift_up` et l'insertion

Insérer consiste à placer la nouvelle clé dans la première case libre — ce qui préserve la complétude, puisqu'on remplit de la gauche vers la droite — puis à la faire remonter tant qu'elle est plus petite que son parent.

def sift_up(t, i):
    """Fait remonter t[i] jusqu'a ce que son parent lui soit inferieur ou egal."""
    while i > 0:
        parent = (i - 1) // 2
        if t[i] < t[parent]:
            t[i], t[parent] = t[parent], t[i]
            i = parent
        else:
            return


def insere_tas(t, cle):
    """Ajoute cle au tas t, en place."""
    t.append(cle)
    sift_up(t, len(t)

Chaque tour de boucle fait une comparaison et au plus un échange, et fait remonter d'un niveau: il y a donc au plus $⌊ lo g_{2} n ⌋$ tours, et l'insertion coûte $O (lo g n)$ comparaisons dans le pire des cas. Dans le cas favorable — la nouvelle clé est plus grande que son parent — elle en coûte une seule, ce qui explique une observation de la section suivante.

Descendre: `sift_down` et l'extraction

L'extraction du minimum est plus délicate. On ne peut pas simplement retirer la racine: l'arbre se scinderait en deux. On déplace donc la dernière feuille à la racine — ce qui préserve la complétude — et on la fait redescendre à sa place.

def sift_down(t, i, n):
    """Fait descendre t[i] jusqu'a ce que le sous-arbre enracine en i soit un tas."""
    while True:
        gauche, droit = 2 * i + 1, 2 * i + 2
        plus_petit = i
        if gauche < n and t[gauche] < t[plus_petit]:
            plus_petit = gauche
        if droit < n and t[droit] < t[plus_petit]:

Chaque tour fait au plus deux comparaisons de clés et descend d'un niveau: l'extraction coûte donc au plus $2 ⌊ lo g_{2} n ⌋$ comparaisons, soit $O (lo g n)$ . Le paramètre n n'est pas redondant avec len(t): il permettra au tri par tas de travailler sur un préfixe du tableau.

Une remarque avant de démontrer quoi que ce soit: sift_down compare la clé au plus petit des deux enfants, jamais à un seul. L'erreur qui consiste à comparer d'abord à l'enfant gauche et à n'examiner l'enfant droit qu'en cas d'échec produit un tableau qui viole la propriété de tas et personne ne s'en aperçoit avant que les extractions ne sortent dans le désordre.

Démonstration. Nous utilisons la caractérisation locale de la propriété de tas: un sous-arbre est un tas si et seulement si sa racine est inférieure ou égale à ses enfants directs et si ses deux sous-arbres sont des tas. Cette équivalence est immédiate sur la définition, et elle entraîne par récurrence que la racine d'un tas est inférieure ou égale à tous ses descendants, chaque chemin descendant donnant une chaîne d'inégalités.

Terminaison. À chaque tour de boucle où l'on ne sort pas, on affecte à $i$ l'indice d'un enfant, donc la profondeur de $i$ augmente strictement d'une unité. Comme la profondeur est majorée par $⌊ lo g_{2} n ⌋$ , il y a au plus $⌊ lo g_{2} n ⌋ - profondeur (i)$ tours, chacun coûtant au plus deux comparaisons de clés — d'où le décompte annoncé. La boucle se termine soit en atteignant une feuille, soit plus tôt.

Conservation des éléments. La seule modification du tableau est un échange de deux cases, qui ne change pas le multiensemble des valeurs présentes; et les deux cases échangées appartiennent toujours au sous-arbre enraciné en $i$ , puisque l'une est $i$ et l'autre l'un de ses enfants.

Correction. Montrons la propriété par récurrence forte sur la hauteur $k$ du sous-arbre enraciné en $i$ .

Si $k = 0$ , le nœud $i$ est une feuille: les tests gauche < n et droit < n échouent tous deux, plus_petit vaut $i$ , la fonction retourne aussitôt et le sous-arbre, réduit à un nœud, est un tas.

Soit $k \geq 1$ , et supposons la propriété acquise pour toute hauteur strictement inférieure. Par hypothèse du théorème, les deux sous-arbres de $i$ sont des tas. Les deux premiers if calculent plus_petit comme l'indice d'une plus petite valeur parmi t[i] et celles de ses enfants existants. Deux cas.

Si plus_petit == i, alors t[i] est inférieure ou égale à ses enfants; comme ses deux sous-arbres sont déjà des tas, la caractérisation locale conclut: le sous-arbre enraciné en $i$ est un tas, et la fonction retourne sans rien modifier.

Si plus_petit == m avec $m \neq = i$ , notons $v$ l'ancienne valeur de t[i] et $w$ celle de t[m], avec $w < v$ et $w$ minimale parmi les trois. Après l'échange, t[i] vaut $w$ , qui est inférieure ou égale à la valeur de chacun des deux enfants de $i$ : celle de l'enfant resté en place n'a pas bougé et était supérieure ou égale à par minimalité, et celle de l'enfant vaut désormais . La condition locale est donc satisfaite en . Le sous-arbre de l'enfant non touché est resté un tas. Quant au sous-arbre enraciné en : ses deux propres sous-arbres n'ont pas été modifiés et étaient des tas — puisque le sous-arbre enraciné en en était un —, seule sa racine a changé, et vaut maintenant . Il est donc dans l'état exact que l'hypothèse du théorème exige, à une hauteur . La boucle poursuit avec , ce qui est précisément l'appel récursif; l'hypothèse de récurrence forte s'applique et le sous-arbre enraciné en devient un tas, sans que ses éléments changent — donc sans que la condition locale rétablie en soit remise en cause, car elle ne porte que sur les valeurs des racines des deux sous-arbres, et la racine du sous-arbre de ne peut qu'y diminuer ou rester égale.

Le sous-arbre enraciné en $i$ est donc un tas. $□$

Construire un tas: la méthode de Floyd

Comment transformer un tableau quelconque en tas? La méthode évidente insère les éléments un à un, au prix de $O (lo g n)$ comparaisons chacun, soit $O (n lo g n)$ au total. La méthode de Floyd (1964) fait mieux: elle travaille en place, en appelant sift_down sur chaque nœud interne, de bas en haut.

def construit_tas(t):
    """Transforme la liste t en tas, en place (methode de Floyd)."""
    for i in range(len(t) // 2 - 1, -1, -1):
        sift_down(t, i, len(t))

La boucle part de $⌊ n /2 ⌋ - 1$ , le dernier nœud interne, et remonte jusqu'à $0$ . Les feuilles sont ignorées: un sous-arbre à un nœud est déjà un tas. L'ordre décroissant des indices garantit l'hypothèse du théorème 5.4 — quand on traite $i$ , les indices $2 i + 1$ et $2 i + 2$ , qui sont strictement supérieurs à $i$ , ont déjà été traités et enracinent donc des tas.

Exemple 5.5 · La construction de Floyd sur le tableau témoin

Voici les trois appels à sift_down et l'état du tableau après chacun.

t = [38, 27, 43, 3, 9, 82, 10]
for i in range(len(t) // 2 - 1, -1, -1):
    sift_down(t, i, len

Démonstration. Le coût d'un appel sift_down sur un nœud dépend de la hauteur de ce nœud, pas de la taille de l'arbre: d'après le théorème 5.4, un nœud de hauteur $k$ coûte au plus $2 k$ comparaisons, puisque sift_down descend d'un niveau par tour et qu'il ne peut pas descendre plus bas que le fond de son propre sous-arbre. Le coût total est donc

C (n) \leq k \geq 0 \sum 2 k \cdot ν_{k}, (5.4)

où $ν_{k}$ est le nombre de nœuds de hauteur $k$ . Toute la démonstration consiste à majorer $ν_{k}$ , puis à sommer.

Étape 1: majorer le nombre de nœuds de hauteur $k$ . Affirmons que $ν_{k} \leq n / 2^{k}$ .

Soit $x$ un nœud de hauteur $k$ , situé à la profondeur $d$ dans l'arbre, et soit $H = ⌊ lo g_{2} n ⌋$ la hauteur de l'arbre entier. Le sous-arbre enraciné en $x$ a pour hauteur $k$ , donc $d + k \leq H$ . Or l'arbre est : tous ses niveaux sont pleins sauf éventuellement le dernier, celui de profondeur . Les niveaux de profondeur sont donc tous pleins, puisque . À l'intérieur du sous-arbre de , cela signifie que ses niveaux relatifs sont complets, soit nœuds, auxquels s'ajoute au moins un nœud de niveau relatif — il en existe un, sinon la hauteur de ne serait pas . Le sous-arbre de compte donc .

Deux nœuds distincts de même hauteur ne peuvent être l'un ancêtre de l'autre — un ancêtre est strictement plus haut —, donc leurs sous-arbres sont disjoints. La réunion des sous-arbres des $ν_{k}$ nœuds de hauteur $k$ compte donc au moins $ν_{k} \cdot 2^{k}$ nœuds, tous pris dans les $n$ nœuds de l'arbre:

ν_{k} \cdot 2^{k} \leq n, c’est- \overset{a}{ˋ} -dire ν_{k} \leq \frac{n}{2 ^{k}} . (5.5)

Étape 2: la somme télescopique. Il nous faut la valeur de $S = \sum_{k \geq 1} k / 2^{k}$ . Cette série converge, ses termes étant positifs et majorés par $k 2^{- k}$ , de somme finie. Calculons-la sans dérivation, par un décalage d'indice:

\frac{S}{2} = k \geq 1 \sum \frac{k}{2 ^{k + 1}} = j \geq 2 \sum \frac{j - 1}{2 ^{j}},

en posant $j = k + 1$ . Soustrayons cette égalité de la définition de $S$ . Le terme $j = 1$ de $S$ , qui vaut $1/2$ , n'a pas de vis-à-vis; pour $j \geq 2$ , les termes se retranchent deux à deux et il reste $j - (j - 1) = 1$ au numérateur:

S - \frac{S}{2} = \frac{1}{2} + j \geq 2 \sum \frac{j - ( j - 1 )}{2 ^{j}} = j \geq 1 \sum \frac{1}{2 ^{j}} = 1,

la dernière somme étant une série géométrique de raison $1/2$ et de premier terme $1/2$ . Donc $S /2 = 1$ , et

S = k \geq 1 \sum \frac{k}{2 ^{k}} = 2. (5.6)

Étape 3: conclusion. En reportant (5.5) et (5.6) dans (5.4):

C (n) \leq k \geq 1 \sum 2 k \cdot \frac{n}{2 ^{k}} = 2 n k \geq 1 \sum \frac{k}{2 ^{k}} = 2 n \cdot 2 = 4 n .

Le terme $k = 0$ a été écarté parce qu'il est nul. Le nombre d'échanges se majore de la même façon, chaque tour de boucle n'en faisant qu'un: il est au plus $2 n$ . La construction de Floyd est donc en $O (n)$ , et même en $Θ (n)$ , puisqu'elle doit au minimum lire les $n$ cases. $□$

Question 5.7

Implémentez sift_down et la construction de Floyd, et retrouvez le tas témoin du cours. Le programme doit afficher le tas obtenu puis, sur la ligne suivante, le nombre de comparaisons de clés effectuées. Le module heapq est interdit: c'est vous qui construisez le tas.

construit_tas.py

Le tri par tas

Un tas donne immédiatement un algorithme de tri, découvert par Williams en 1964: construire le tas, puis extraire le minimum $n$ fois. Dans sa version en place, on utilise un tas maximum et l'on range chaque maximum extrait à la fin du tableau, dans la zone que le tas vient de libérer.

def tri_par_tas(t):
    """Trie t en place, en ordre croissant, avec un tas maximum."""
    n = len(t)
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(t, i, n)
    for fin in range(n - 1, 0, -1):
        t[0], t[fin] = t[fin], t[0

Sur le tableau témoin, le tri par tas fait 19 comparaisons de clés: 8 pour la construction et 11 pour les six extractions. À titre de repère, les trois tris du chapitre 3 sur le même tableau en font 15 (insertion), 13 (fusion) et 11 (tri rapide, partition de Lomuto) — ces trois comptes sont fixés par le cours, celui-ci est le nôtre et vaut pour cet algorithme précis. Sur sept éléments, le tri par tas est donc le plus coûteux des quatre: ses constantes sont médiocres et son intérêt est ailleurs.

Cet intérêt est double, et il est réel. D'abord, le tri par tas est en $Θ (n lo g n)$ comparaisons dans le pire des cas — la construction coûte $O (n)$ et chacune des $n - 1$ extractions $O (lo g n)$ —, ce que le tri rapide ne garantit pas. Ensuite, il trie en place, avec $O (1)$ mémoire auxiliaire, ce que le tri fusion ne fait pas. Il est le seul des quatre à offrir les deux à la fois. En revanche il n'est pas stable, et ses accès mémoire sautent d'un bout à l'autre du tableau, ce qui le pénalise lourdement sur une machine réelle: c'est pourquoi il sert surtout de filet de sécurité, comme dans l'introsort des bibliothèques C++, qui commence en tri rapide et bascule sur le tri par tas quand la récursion devient trop profonde.

Question 5.8

Écrivez le tri par tas en place. La construction du tas maximum vous est donnée; complétez la phase d'extraction pour que le programme affiche le tableau témoin trié, puis le nombre total de comparaisons de clés. L'algorithme doit trier sur place, sans créer de seconde liste.

tri_par_tas.py

La file de priorité, interface des chapitres 7 et 8

Le type abstrait

Un tas n'est pas une fin en soi: c'est une implémentation d'un type abstrait de données que les chapitres suivants utiliseront comme une boîte noire.

Implémentation	`inserer`	`minimum`	`extraire_min`	`diminuer_priorite`	Construction de $n$ éléments
Liste non triée	$Θ (1)$	$Θ (n)$	$Θ (n)$	$Θ (1)$	$Θ (n)$
Liste triée	$Θ (n)$	$Θ (1)$

Tous les coûts sont donnés dans le pire des cas. Deux lectures de ce tableau valent d'être faites. D'abord, la liste non triée n'est pas absurde: si votre algorithme fait beaucoup d'insertions et très peu d'extractions, elle gagne. Le choix d'une structure dépend du mélange d'opérations, jamais d'une seule ligne du tableau. Ensuite, le tas binaire bat l'ABR équilibré sur minimum et sur la construction, et il perd tout le reste — la recherche d'une clé quelconque, l'énumération triée, le successeur. Ce sont deux structures pour deux problèmes.

L'opération diminuer_priorite est celle dont l'algorithme de Dijkstra a besoin au chapitre 7: quand la relaxation d'une arête améliore l'estimation $d [v]$ , il faut le dire à la file. Dans un tas binaire, elle s'implémente en écrasant la priorité puis en appelant sift_up — $O (lo g n)$ —, à condition de savoir où se trouve l'élément, ce qui suppose un dictionnaire auxiliaire de l'élément vers son indice, maintenu à chaque échange.

`heapq`, et ce qu'il ne fait pas

Python fournit le tas binaire dans le module heapq de la bibliothèque standard. Il ne définit pas de classe: ses fonctions opèrent directement sur une liste Python, exactement comme le code de ce chapitre.

import heapq

t = [38, 27, 43, 3, 9, 82, 10]
heapq.heapify(t)                 # construction de Floyd, en place, O(n)
print(t)
heapq.heappush(t, 15)            # insertion, O(log n)
print(heapq.heappop(t))          # extraction du minimum, O(log n)
print(t[0])                      # le minimum, sans le retirer, O(1)
print(heapq.nsmallest(3, t))     # les trois plus petits, tries

[3, 9, 10, 27, 38, 82, 43]
3
[9, 10, 15, 27, 38, 82, 43]
9
[9, 10, 15]

Le heapify reproduit exactement le tas témoin du cours: la bibliothèque standard implémente la construction de Floyd, et non les insertions successives.

Trois limites, qu'il vaut mieux connaître avant de s'y heurter.

heapq ne gère que les tas minimum. Pour un tas maximum, on insère les opposés et on renverse au moment de lire: heapq.heapify([-x for x in t]) donne [82, 27, 43, 3, 9, 38, 10] une fois les signes rétablis, c'est-à-dire exactement le tas maximum témoin du cours. L'astuce est standard et sans risque pour des nombres; pour des objets, il faut envelopper.

heapq n'offre pas diminuer_priorite. La parade usuelle est la suppression paresseuse: on ne modifie rien, on insère une seconde entrée avec la nouvelle priorité, et au moment d'extraire on ignore toute entrée dont la priorité ne correspond plus à celle que l'on a enregistrée par ailleurs. Le tas grossit — jusqu'à $m$ entrées pour $m$ relaxations, au chapitre 7 — mais chaque opération reste en $O (lo g m)$ , et $lo g m \leq 2 lo g n$ pour un graphe simple. C'est la version de Dijkstra que le chapitre 7 écrira, et c'est celle de la plupart des implémentations réelles.

heapq compare les éléments entiers. Pour associer une priorité à un objet, on empile des tuples (priorite, element), et Python compare d'abord les priorités; en cas d'égalité il compare les éléments, ce qui lève une exception si ceux-ci ne sont pas comparables entre eux. La parade est un compteur strictement croissant en deuxième position: (priorite, numero, element). Le compteur départage les ex æquo par ordre d'arrivée, ce qui rend la file stable, et garantit que le troisième champ n'est jamais atteint par une comparaison.

Question 5.9

Vous devez maintenir un ensemble de tâches et, à chaque étape, traiter la plus urgente, tout en ajoutant de nouvelles tâches. De temps en temps, vous devez aussi retrouver une tâche par son identifiant pour l'annuler. Quelle structure choisissez-vous?

Synthèse

La hauteur commande tout. Un arbre binaire de $n$ nœuds vérifie $⌈ lo g_{2} (n + 1)⌉ - 1 \leq h \leq n - 1$ , et chaque opération d'un arbre de recherche coûte $O (h)$ comparaisons. L'ABR témoin du cours — [38, 27, 43, 3, 9, 82, 10] inséré dans cet ordre — a pour racine 38 et pour hauteur , à cause de la chaîne dégénérée ; les mêmes clés insérées triées donnent un peigne de hauteur , c'est-à-dire une liste chaînée.

Série d'exercices du chapitre 5Exercice 1 sur 5

Question 5.10

Quelle est la hauteur minimale, en arêtes, d'un arbre binaire de 1000 nœuds?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 5.1 · Trois ordres d'insertion pour un même ensemble

On considère l'ensemble de clés ${3, 9, 10, 27, 38, 43, 82}$ , celui du tableau témoin.

Donnez la hauteur de l'ABR obtenu en insérant les clés dans l'ordre $38, 27, 43, 3, 9, 82, 10$ , puis dans l'ordre croissant, puis dans l'ordre $27, 9, 3, 10, 43, 38, 82$ .

Exercice 5.2 · Des clés en double

La définition de ce chapitre suppose les clés deux à deux distinctes, et l'insertion ignore silencieusement une clé déjà présente. On veut maintenant autoriser les doublons.

Proposez deux manières de le faire, et dites ce que chacune coûte.
Une troisième proposition consiste à relâcher la propriété d'ordre en «les clés du sous-arbre gauche sont inférieures ou égales». Montrez sur un exemple de trois nœuds qu'elle rend la recherche de toutes les occurrences d'une clé plus délicate qu'il n'y paraît.

Solution

1. Première manière: un compteur par nœud. Chaque nœud porte sa clé et le nombre d'occurrences. L'insertion d'une clé déjà présente incrémente le compteur, en $O (h)$ ; la suppression le décrémente et ne retire le nœud qu'à zéro. Le coût de toutes les opérations est inchangé, la taille de l'arbre est le nombre de clés distinctes, ce qui est un avantage net quand les doublons sont nombreux. C'est la solution à préférer par défaut.

Deuxième manière: une liste par nœud. Chaque nœud porte la clé et la liste des enregistrements qui la possèdent. C'est la même structure, adaptée au cas où les doublons portent des données différentes — un index de base de données sur un champ non unique fonctionne ainsi.

2. Prenons la clé 5 insérée trois fois, dans un arbre où les égalités partent à gauche. Selon l'ordre des autres insertions, les trois 5 peuvent former la chaîne $5 \to 5 \to 5$ descendant à gauche — mais un nœud portant 4 peut parfaitement s'intercaler: insérons 5, puis 5, puis 4. Le premier 5 est la racine; le second va à gauche; le 4 va à gauche de la racine, puis à gauche du second 5. L'arbre est en descendant à gauche. Insérons maintenant un troisième 5: il part à gauche de la racine, puis à gauche du second 5, puis de 4. Les trois 5 ne sont donc plus sur un chemin contigu, et l'on en trouve un dans le sous-arbre d'un nœud portant 4.

Exercice 5.3 · Rotations à la main

Partez de l'arbre AVL réduit au seul nœud $38$ et insérez successivement $27$ , $43$ , $82$ , $10$ , $9$ , en appliquant le rééquilibrage après chaque insertion. Donnez, après chaque insertion, la racine et la hauteur, ainsi que la rotation effectuée s'il y en a une.
Vérifiez que le parcours infixe final est croissant.

Solution

Notons $b (x)$ le facteur d'équilibre.

Insertion de 27. À gauche de 38. Racine 38, hauteur 1, $b (38) = 0 - (- 1) = 1$ : dans la contrainte, aucune rotation.

Exercice 5.4 · Le k-ième plus petit élément

On veut ajouter à l'ABR une opération selection(racine, k) qui renvoie la $k$ -ième plus petite clé, pour $0 \leq k < n$ .

Donnez une solution qui n'utilise que ce que vous savez déjà, et son coût.
On stocke maintenant dans chaque nœud la taille de son sous-arbre. Écrivez selection en $O (h)$ et justifiez le coût.
Quel est le surcoût de ce champ supplémentaire lors d'une insertion, et lors d'une rotation d'AVL?

Solution

1. Le parcours infixe produit les clés triées: il suffit de le lancer et de prendre l'élément d'indice $k$ . Le coût est dans tous les cas, ce qui est décevant pour une structure dont toutes les autres opérations sont en . On peut arrêter le parcours dès le -ième élément atteint, ce qui donne — mieux, mais toujours pour voisin de .

Exercice 5.5 · Une borne inférieure sur la construction d'un tas

Cet exercice demande des démonstrations complètes.

Démontrez que la construction d'un tas de $n$ éléments par comparaisons exige $Ω (n)$ comparaisons dans le pire des cas.
Le chapitre 3 démontre qu'un tri par comparaisons exige $Ω (n lo g n)$ comparaisons dans le pire des cas. Concilier ce résultat avec le théorème 5.5, qui construit un tas en $O (n)$ : pourquoi n'y a-t-il pas contradiction? Quantifiez en dénombrant.
En déduire une borne inférieure sur le coût total des $n$ extractions successives d'un tas, et comparez-la au décompte de l'étape ch5-g4.

Solution

Références

Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 6 pour le tas binaire, sift_down («MAX-HEAPIFY») et la démonstration en $O (n)$ de la construction, chapitre 12 pour les arbres binaires de recherche et chapitre 13 pour les arbres rouge-noir. Les indices y sont comptés à partir de 1; ce cours les compte à partir de 0, ce qui change $2 i$ et $2 i + 1$ en $2 i + 1$ et $2 i + 2$ .
Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, pour fixer le vocabulaire: «tas», «tamisage», «rotation», «arbre de recherche».
Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — sections 2.4 («Priority Queues») et 3.2–3.3, avec les arbres 2-3 et les arbres rouge-noir «penchés à gauche», nettement plus simples à implémenter que la version classique.

Objectifs du chapitre

Pourquoi un arbre

Deux structures qui ne savent chacune faire qu'une moitié du travail

Le vocabulaire des arbres binaires

Un arbre en Python

L'arbre binaire de recherche

La propriété d'ordre

Rechercher

Insérer

Le peigne, et pourquoi il faut équilibrer

Les parcours

La suppression, et ses trois cas

Équilibrer: les arbres AVL

Les rotations

Les quatre cas

Le tas binaire

Remonter: `sift_up` et l'insertion

Descendre: `sift_down` et l'extraction

Construire un tas: la méthode de Floyd

Le tri par tas

La file de priorité, interface des chapitres 7 et 8

Le type abstrait

`heapq`, et ce qu'il ne fait pas

Synthèse

Exercices

Références

La hauteur du tas

Le coût d'une extraction

Construire contre insérer

Vider la file

Objectifs du chapitre

Pourquoi un arbre

Deux structures qui ne savent chacune faire qu'une moitié du travail

Le vocabulaire des arbres binaires

Un arbre en Python

L'arbre binaire de recherche

La propriété d'ordre

Rechercher

Insérer

Le peigne, et pourquoi il faut équilibrer

Les parcours

La suppression, et ses trois cas

Équilibrer: les arbres AVL

Les rotations

Les quatre cas

Le tas binaire

Remonter: sift_up et l'insertion

Descendre: sift_down et l'extraction

Construire un tas: la méthode de Floyd

Le tri par tas

La file de priorité, interface des chapitres 7 et 8

Le type abstrait

heapq, et ce qu'il ne fait pas

Synthèse

Exercices

Références

La hauteur du tas

Le coût d'une extraction

Construire contre insérer

Vider la file

Remonter: `sift_up` et l'insertion

Descendre: `sift_down` et l'extraction

`heapq`, et ce qu'il ne fait pas