Arbres de recherche équilibrés et requêtes ordonnées

Un ensemble de clés que l’on modifie régulièrement doit souvent répondre à autre chose que « la clé 26 est-elle présente ? ». On peut vouloir la plus grande clé inférieure à 26, ou toutes les clés comprises entre 25 et 60. Un arbre de recherche équilibré conserve l’ordre des clés tout en maintenant des chemins de recherche courts. Il convient donc aux ensembles ordonnés dynamiques. Pour des données rarement modifiées, voir d’abord la recherche dichotomique. Les pages Structures de données et Algorithmes de recherche relient ces choix aux opérations à effectuer.

L’ordre porte sur des sous-arbres entiers

La définition de l’arbre binaire de recherche dans Open Data Structures suppose un ordre total sur les clés : toutes les clés du sous-arbre gauche sont inférieures à celle du nœud, et toutes celles du sous-arbre droit lui sont supérieures. On utilise ici un ensemble : insérer une clé déjà présente n’ajoute aucun nœud. Dans un arbre associant des valeurs aux clés, cette opération peut plutôt mettre à jour la valeur.

Comparer seulement chaque parent à ses enfants ne suffit pas. Avec une racine 40 et un enfant gauche 20, l’enfant droit de 20 peut être 30, mais pas 50. Même si 50 est supérieur à 20, il reste dans le sous-arbre gauche de 40. Un parcours infixe — sous-arbre gauche, nœud, sous-arbre droit — produit les clés dans l’ordre croissant.

Un tas min impose seulement que la clé d’un parent soit inférieure ou égale à celles de ses enfants. Une racine 10 avec un enfant gauche 70 et un enfant droit 20 respecte cet ordre. Le tas ne sépare pas les clés entre gauche et droite comme un arbre de recherche : une comparaison ne permet donc pas de choisir une seule direction. Le tas convient aux extractions répétées du minimum ; l’arbre de recherche permet de retrouver une clé et d’effectuer des requêtes ordonnées.

Descendre par un chemin, puis énumérer dans l’ordre

Insérons successivement 40, 20, 60, 10, 30, 50, 70, 55 :

L et R désignent les enfants gauche et droit. La recherche de 55 visite 40, 60, 50, 55, soit 4 nœuds. Si l’on atteint un enfant vide sans trouver d’égalité, la clé est absente. Pour insérer 25, on visite 40, 20, 30, puis on place le nouveau nœud à gauche de 30, à l’emplacement vide.

Les requêtes ordonnées gardent une réponse candidate pendant la descente :

Requête	Mise à jour de la candidate	Résultat après insertion de 25
Prédécesseur strict : plus grande clé inférieure à x	Si la clé courante est inférieure à x, la retenir et aller à droite ; sinon aller à gauche	predecessor(26) = 25
Borne inférieure : plus petite clé supérieure ou égale à x	Si la clé courante est supérieure ou égale à x, la retenir et aller à gauche ; sinon aller à droite	lower_bound(26) = 30
Intervalle semi-ouvert $[lo, hi)$	Parcourir dans l’ordre infixe en évitant les sous-arbres qui ne peuvent contenir de résultat	$[25,60)$ donne 25, 30, 40, 50, 55

Le prédécesseur et la borne inférieure peuvent donner une réponse même si la clé recherchée est absente. Ils renvoient None lorsqu’aucune clé ne convient. Le prédécesseur strict exclut l’égalité ; la borne inférieure l’inclut. Pour la frontière correspondante dans un tableau, voir la borne inférieure en recherche dichotomique.

Pour énumérer un intervalle, on conserve la pile du parcours infixe ou des liens vers les parents, afin de passer à la clé suivante sans repartir de la racine. L’implémentation récursive ci-dessous utilise la pile d’appels et élague selon les bornes. Pour $k$ clés produites et une hauteur $h$, une recherche isolée coûte $O(h+1)$, l’énumération coûte $O(h+1+k)$ et la pile auxiliaire occupe $O(h+1)$. Dans un arbre équilibré, l’énumération coûte donc $O(\log(n+1)+k)$ ; écrire les résultats prend déjà $O(k)$. Rechercher chaque résultat depuis la racine ajoute du travail de localisation répété.

Des insertions triées peuvent former une chaîne

Selon la convention de hauteur d’Open Data Structures, la hauteur compte les arêtes entre la racine et le nœud réel le plus profond. Un arbre à un seul nœud a une hauteur de 0. En insérant 1, 2, 3, 4, 5, 6, 7 dans cet ordre, chaque nouvelle clé part à droite : on obtient une chaîne de hauteur 6. Retrouver 7 demande de visiter 7 nœuds. Plus généralement, $n$ clés croissantes donnent une hauteur de $n-1$ et une recherche linéaire en bout de chaîne. La construction visite au total $0+1+\cdots+(n-1)=n(n-1)/2$ nœuds déjà présents.

Un ordre de recherche correct ne garantit donc pas une hauteur logarithmique. L’algorithme d’équilibrage doit imposer un invariant supplémentaire sur la forme de l’arbre, puis le rétablir après chaque modification.

Une rotation modifie les liens et conserve l’ordre

Open Data Structures décrit les rotations et leurs opérations sur les pointeurs à la section 7.2. Une rotation droite fait de l’enfant gauche la racine locale, et de l’ancienne racine son enfant droit. Le schéma 1 représente l’état initial, le schéma 2 l’état après rotation :

Le sous-arbre intermédiaire 30 doit passer de la droite de 20 à la gauche de 40. Ses clés sont comprises entre 20 et 40 : les deux rattachements respectent donc l’ordre de recherche. La séquence infixe reste 10, 20, 30, 40, 60. Le raisonnement vaut aussi pour des sous-arbres entiers : les clés de gauche sont inférieures à 20, celles du milieu se trouvent entre 20 et 40, et celles de droite sont supérieures à 40. Une rotation gauche effectue les changements inverses.

Une rotation modifie un nombre constant de liens et coûte $O(1)$. L’appelant doit rattacher la nouvelle racine locale à son parent, ou remplacer la racine de l’arbre. Une implémentation qui conserve des pointeurs vers les parents, des tailles de sous-arbres ou d’autres champs doit aussi les mettre à jour. La rotation préserve l’ordre de recherche ; l’invariant d’équilibrage détermine les rotations à effectuer.

Les couleurs d’un arbre rouge-noir limitent sa hauteur

Les arbres rouge-noir garantissent, pour un arbre non vide, des recherches, insertions et suppressions en $O(\log n)$ dans le pire cas. Les invariants rouge-noir de la section 9.2 permettent de contrôler la structure :

• Chaque nœud réel est rouge ou noir, la racine est noire et les enfants vides sont considérés comme des nœuds NIL noirs.
• Les enfants d’un nœud rouge sont noirs : deux nœuds rouges ne peuvent pas être adjacents.
• Tous les chemins allant d’un nœud à un NIL descendant contiennent le même nombre de nœuds noirs.

Pour les comptes de l’exemple, $b$ désigne le nombre de nœuds noirs réels sur un chemin de la racine à NIL, racine comprise et NIL exclu. L’interdiction de deux rouges adjacents limite un chemin maximal à une alternance de noirs et de rouges. L’égalité des comptes noirs impose une profondeur correspondante à toutes les branches. Un décompte récursif donne au moins $2^b-1$ nœuds réels, tandis qu’un chemin jusqu’au nœud le plus profond contient au plus $2b$ nœuds réels. On obtient ainsi une borne de hauteur pratique :

$$h \le 2\log_2(n+1), \qquad n\ge 1.$$

C’est une borne supérieure, sans obligation d’avoir autant de nœuds à gauche qu’à droite. L’implémentation du livre impose aussi une condition d’inclinaison à gauche : si l’enfant gauche est noir, l’enfant droit doit être noir. Les trois conditions précédentes sont les contraintes rouge-noir générales vérifiées ici.

Une insertion ajoute d’abord une feuille rouge selon l’ordre de recherche, ce qui conserve le compte des nœuds noirs de chaque chemin. Elle répare ensuite les éventuelles arêtes rouge-rouge et colore la racine en noir. Pour la première clé insérée dans un arbre vide, il faut aussi rendre la nouvelle racine noire : le compte noir de tous les chemins augmente alors de 1. Partons d’une racine noire 30 avec un enfant gauche rouge 20, puis insérons 10 en rouge. L’arête 20—10 viole l’invariant. Une rotation droite en 30, suivie du passage de 20 au noir et de 30 au rouge, donne une racine noire 20 avec deux enfants rouges, 10 et 30. Chaque chemin contient 1 nœud noir réel, et la hauteur passe de 2 à 1. Le code qui suit exécute et vérifie ce cas précis de réparation.

Supprimer un nœud ayant deux enfants

La suppression dans un arbre de recherche ordinaire comporte trois cas. On détache une feuille ; on remplace un nœud ayant un seul enfant par cet enfant ; avec deux enfants, on remplace sa clé par le minimum du sous-arbre droit, son successeur strict, puis on supprime le nœud où se trouvait ce successeur.

Dans l’arbre précédent, après insertion de 25, supprimons 40. La plus petite clé du sous-arbre droit est 50 : la clé de la racine devient donc 50. Le nœud 50 d’origine n’a pas d’enfant gauche, mais possède un enfant droit 55. Pour le retirer, il faut faire de 55 l’enfant gauche de 60. La séquence infixe finale est 10, 20, 25, 30, 50, 55, 60, 70 : seule la clé 40 a disparu. Pour des enregistrements clé-valeur, il faut remplacer la valeur avec la clé ; copier uniquement la clé lui associerait le mauvais enregistrement.

Un arbre rouge-noir doit aussi rétablir ses contraintes de couleur. Si le nœud physiquement retiré est noir, certains chemins perdent un nœud noir. La réparation utilise les couleurs de l’enfant de remplacement et de son frère pour recolorer et effectuer des rotations, en propageant si nécessaire le déficit vers la racine. C’est la couleur du successeur réellement retiré qui compte, pas seulement celle du nœud portant la clé initialement demandée. Rétablir l’ordre de recherche et rétablir l’équilibre rouge-noir sont deux étapes de la suppression.

Requêtes et suppression exécutables

Ce programme implémente les opérations structurelles d’un arbre binaire de recherche ordinaire à clés entières. Une insertion répétée n’ajoute pas de nœud ; supprimer une clé absente ne change pas l’ensemble. Le champ de couleur sert à l’exemple de réparation qui suit : insert et delete n’effectuent ici aucun équilibrage rouge-noir. Les opérations récursives doivent pouvoir parcourir tout le chemin dans la pile d’appels ; une longue chaîne qui dépasse la limite de récursion de Python provoque une exception RecursionError.

from dataclasses import dataclass


@dataclass
class Node:
    key: int
    left: 'Node | None' = None
    right: 'Node | None' = None
    red: bool = False


def insert(t, x):
    if t is None:
        return Node(x)
    if x < t.key:
        t.left = insert(t.left, x)
    elif x > t.key:
        t.right = insert(t.right, x)
    return t


def search(t, x):
    path = []
    while t is not None:
        path.append(t.key)
        if x == t.key:
            return True, path
        t = t.left if x < t.key else t.right
    return False, path


def predecessor(t, x):
    best = None
    while t is not None:
        if t.key < x:
            best, t = t.key, t.right
        else:
            t = t.left
    return best


def lower_bound(t, x):
    best = None
    while t is not None:
        if t.key >= x:
            best, t = t.key, t.left
        else:
            t = t.right
    return best


def between(t, lo, hi):
    if t is None:
        return
    if lo < t.key:
        yield from between(t.left, lo, hi)
    if lo <= t.key < hi:
        yield t.key
    if t.key < hi:
        yield from between(t.right, lo, hi)


def delete(t, x):
    if t is None:
        return None
    if x < t.key:
        t.left = delete(t.left, x)
    elif x > t.key:
        t.right = delete(t.right, x)
    else:
        if t.left is None:
            return t.right
        if t.right is None:
            return t.left
        successor = t.right
        while successor.left is not None:
            successor = successor.left
        t.key = successor.key
        t.right = delete(t.right, successor.key)
    return t


def height(t):
    return -1 if t is None else 1 + max(height(t.left), height(t.right))


root = None
for x in [40, 20, 60, 10, 30, 50, 70, 55]:
    root = insert(root, x)
print('search 55:', search(root, 55))
root = insert(root, 25)
print('predecessor 26:', predecessor(root, 26))
print('lower_bound 26:', lower_bound(root, 26))
print('range [25, 60):', list(between(root, 25, 60)))
root = delete(root, 40)
print('after delete 40:', list(between(root, 0, 100)))
print('replacement:', root.key, root.right.left.key)
chain = None
for x in range(1, 8):
    chain = insert(chain, x)
print('sorted insertion:', height(chain), len(search(chain, 7)[1]))

Sortie :

search 55: (True, [40, 60, 50, 55])
predecessor 26: 25
lower_bound 26: 30
range [25, 60): [25, 30, 40, 50, 55]
after delete 40: [10, 20, 25, 30, 50, 55, 60, 70]
replacement: 50 55
sorted insertion: 6 7

Ajoutez le code suivant à la fin du même fichier Python. check_rb vérifie l’ordre de recherche sur chaque sous-arbre entier, les arêtes rouge-rouge et l’égalité des comptes noirs. Il renvoie le nombre de nœuds noirs à partir du nœud courant, sans compter NIL ; l’appelant vérifie séparément que la racine est noire.

def rotate_right(t):
    pivot = t.left
    assert pivot is not None
    t.left = pivot.right
    pivot.right = t
    return pivot


def check_rb(t, lo=float('-inf'), hi=float('inf')):
    if t is None:
        return 0
    assert lo < t.key < hi
    if t.red:
        assert t.left is None or not t.left.red
        assert t.right is None or not t.right.red
    left = check_rb(t.left, lo, t.key)
    right = check_rb(t.right, t.key, hi)
    assert left == right
    return left + int(not t.red)


rb = Node(30, Node(20, Node(10, red=True), red=True))
before = list(between(rb, 0, 100))
try:
    check_rb(rb)
except AssertionError:
    print('before: invariant fails')
rb = rotate_right(rb)
rb.red = False
rb.right.red = True
assert not rb.red
black_count = check_rb(rb)
assert list(between(rb, 0, 100)) == before
print('after:', rb.key, rb.left.key, rb.right.key)
print('order:', before)
print('height / black count:', height(rb), black_count)

Sortie de la partie ajoutée :

before: invariant fails
after: 20 10 30
order: [10, 20, 30]
height / black count: 1 1

Choisir entre arbre, tableau trié et table de hachage

La documentation Python de bisect distingue la recherche logarithmique de la position d’insertion de l’insertion elle-même, linéaire dans une liste. L’analyse du hachage par chaînage sépare le coût espéré de la recherche et de la suppression du coût amorti des redimensionnements. Dans le tableau, $n$ est le nombre de clés, $k$ le nombre de résultats d’un intervalle et $B$ le nombre de compartiments de la table de hachage. Comparer, hacher ou déplacer un élément est considéré comme une opération de coût constant ; les bornes vérifient $lo\le hi$. La borne amortie des redimensionnements suppose une croissance géométrique sur une suite de mises à jour commençant avec une table vide.

Opération ou propriété	Arbre de recherche rouge-noir	Tableau trié	Table de hachage par chaînage
Recherche exacte	Pire cas $O(\log(n+1))$	Pire cas $O(\log(n+1))$	Coût espéré $O(1)$, pire cas $O(n)$
Insertion ou suppression	Pire cas $O(\log(n+1))$	Pire cas $O(n)$ ; décalage d’un suffixe	Coût espéré $O(1)$ hors redimensionnement ; redimensionnement amorti $O(1)$
Prédécesseur ou borne inférieure	Pire cas $O(\log(n+1))$	Pire cas $O(\log(n+1))$	Parcours des compartiments et des clés en $O(B+n)$ sans index ordonné
Énumération ordonnée d’un intervalle	$O(\log(n+1)+k)$	$O(\log(n+1)+k)$	Parcours en $O(B+n)$, plus tri des résultats
Stockage	Nœuds, liens et couleurs ; parcours par pointeurs	Emplacements contigus compacts ; bonne localité du parcours	Compartiments et capacité libre ; aucun ordre sur les clés

Les bornes espérées du hachage supposent un hachage adapté et un taux de remplissage contrôlé. Un redimensionnement isolé peut toujours coûter $O(n)$. Un parcours visite tous les compartiments, même vides ; son coût se réduit à $O(n)$ lorsque leur nombre reste proportionnel au nombre de clés présentes. Une table qui grandit sans rétrécir peut conserver beaucoup plus de compartiments que de clés après de nombreuses suppressions. Les bornes de l’arbre comptent les comparaisons et les opérations sur les liens ; les comparaisons coûteuses de chaînes demandent un décompte distinct. Pour les décalages et la localité des tableaux, voir Tableaux et tableaux dynamiques.

Pour des recherches exactes fréquentes, une table de hachage convient généralement. Si les données sont triées par lots et rarement modifiées, un tableau trié permet directement les recherches de frontières et d’intervalles. Quand les insertions et suppressions se poursuivent en parallèle des requêtes de prédécesseur, de borne inférieure ou d’intervalle ordonné, l’arbre de recherche équilibré réunit ces opérations dans une même représentation.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.