Arbres binaires de recherche

Un arbre binaire de recherche (ABR) garde ses clés en ordre : tout ce qui est à gauche d'un noeud est plus petit, tout ce qui est à droite est plus grand ou égal. Cette règle permet de chercher, d'insérer et de supprimer en suivant un seul chemin depuis la racine.

La propriété d'ordre

Pour chaque noeud x :

• toutes les clés du sous-arbre gauche sont ≤ x.clé ;
• toutes les clés du sous-arbre droit sont ≥ x.clé.

Attention : la règle porte sur tout le sous-arbre, pas seulement sur les enfants directs. Un arbre où chaque enfant gauche est plus petit que son parent n'est pas forcément un ABR.

Dans les exemples suivants, on utilise cet arbre :

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80

Recherche et insertion

On part de la racine. Si la valeur cherchée est plus petite que le noeud courant, on va à gauche ; sinon, à droite. Pour insérer, on descend de la même façon jusqu'à un pointeur NULL, et on y accroche le nouveau noeud.

Exemple : insérer 45. 45 < 50 → gauche ; 45 ≥ 30 → droite ; 45 ≥ 40 → droite ; NULL. 45 devient l'enfant droit de 40.

inserer(racine, v):
    si racine == NULL: retourner nouveau Noeud(v)
    si v < racine.cle: racine.gauche = inserer(racine.gauche, v)
    sinon:             racine.droit  = inserer(racine.droit, v)
    retourner racine

Suppression : trois cas

1. Feuille : on l'enlève simplement.
2. Un seul enfant : l'enfant prend la place du noeud.
3. Deux enfants : on copie dans le noeud la valeur de son prédécesseur (le plus grand du sous-arbre gauche), puis on supprime l'ancien prédécesseur. Celui-ci n'a jamais d'enfant droit, donc on retombe sur le cas 1 ou 2.

Exemple : supprimer 50 dans l'arbre ci-dessus. Son prédécesseur est 40 (une fois à gauche, puis à droite jusqu'au bout). On copie 40 à la racine, puis on enlève l'ancienne feuille 40.

Successeur et prédécesseur

• Successeur de x : si x a un sous-arbre droit, c'est le minimum de ce sous-arbre. Ce n'est pas forcément l'enfant droit. Le successeur de 50 est 60, pas 70.
• Prédécesseur de x : si x a un sous-arbre gauche, c'est le maximum de ce sous-arbre. Le prédécesseur de 50 est 40, pas 30.
• Si x n'a pas de sous-arbre du bon côté, il faut remonter vers les ancêtres.

Les parcours

Le parcours en ordre d'un ABR donne toujours les clés triées. C'est un bon moyen de vérifier qu'un arbre respecte la propriété d'ordre.

Reconstruire un arbre à partir de deux parcours

Avec le parcours en ordre et le post-ordre (ou le pré-ordre), on peut reconstruire l'arbre. Le dernier élément du post-ordre est la racine. On la cherche dans le parcours en ordre : ce qui est à sa gauche forme le sous-arbre gauche, ce qui est à sa droite forme le sous-arbre droit. On recommence récursivement sur chaque moitié.

Trouver le k-ième plus petit élément

Si chaque noeud garde la taille de son sous-arbre, on trouve le k-ième plus petit sans parcourir tout l'arbre. Au noeud courant, son rang dans le sous-arbre est r = taille(gauche) + 1 :

• si k = r, c'est ce noeud ;
• si k < r, on descend à gauche avec le même k ;
• si k > r, on descend à droite avec k − r.

Exemple : le 6e plus petit de l'arbre exemple. À 50, r = 3 + 1 = 4 et 6 > 4 : à droite avec k = 2. À 70, r = 1 + 1 = 2 = k : la réponse est 70.

Garder ces tailles à jour coûte O(1) par noeud modifié, donc l'insertion et la suppression restent en O(h).

Complexité

Le pire cas arrive quand on insère des valeurs déjà triées : l'arbre devient une ligne. C'est exactement le problème que règlent les arbres rouge-noir.