Les Arbres Binaires de Recherche - ABR

1) Présentation

Comme son nom l’indique, un ABR a pour but de retrouver un élément.
Les opérations de base d’un ABR sont :

• La recherche d’un élément
• l’insertion d’un élément
• la suppression d’un élément

Si l’arbre est équilibré, on montre que ces opérations ont un coût faible, lié à la hauteur \(h\) de l'arbre :
\(O(h)\), soit \(O(log(n))\) pour un arbre complet.

D’où l’intérêt d’utiliser un arbre équilibré.
Dans un arbre équilibré, les hauteurs des deux sous-arbres d'un même nœud diffèrent au plus de un.

Exemples d’arbres binaires

Règle d’organisation des éléments au sein de l’Arbre Binaire de Recherche.

Les éléments de l’ABR doivent respecter un agencement particulier.
Pour tout nœud de l’arbre :

• sa valeur est strictement supérieure à la plus grande valeur de son sous-arbre gauche
• sa valeur est strictement inférieure à la plus grande valeur de son sous-arbre droit

Conséquences :

• il ne peut pas y avoir deux fois la même valeur dans un ABR.
• Le parcours infixe de l’ABR renvoie une séquence ordonnée des valeurs de l’arbre.

2) Recherche d’une valeur dans l’arbre binaire de recherche.

Algorithme de recherche d’une valeur e dans un arbre ABR = (x, filsGauche, filsDroit) :

Algorithme de recherche d'une valeur e dans un ABR

1   fonction Recherche(ABR, e)
2       Si ABR = ArbreVide
3           retourner Faux
4       Sinon
5           Si x = e
6               retourner Vrai
7           Sinon Si e < x
8               retourner Recherche(filsGauche,e)
9           Sinon
10              retourner Recherche(filsDroit,e)

On pourra de façon encore plus efficace retrouver la valeur max d'un ABR.

3) Insertion d’une valeur dans l’arbre binaire de recherche.

L’algorithme le plus simple pour insérer une valeur dans l’ABR consiste à ajouter une feuille. Autrement dit à parcourir l’ABR en respectant la relation d’ordre et quand on arrive à une feuille on ajoute un fils à cette feuille.
On suppose que e n'est pas déjà dans l'ABR.

Algorithme d'insertion d'une valeur e dans un ABR

1   fonction Insertion(ABR, e)
2       Si ABR = ArbreVide
3           retourner (e, ArbreVide, ArbreVide)
4       Sinon
7           Si e < x
8               retourner (x, Insertion(filsGauche,e), filsDroit)
9           Sinon
10              retourner (x, filsGauche, Insertion(filsDroit,e))

4) Suppression d’un élément d’un ABR (pas au programme).

On commence par rechercher le nœud à supprimer dans l'arbre à partir de sa clé. Plusieurs cas sont à considérer.

1. Suppression d'une feuille : Il suffit de l'enlever de l'arbre puisqu'elle n'a pas de fils ; voir suppression de 17
2. Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils ; voir suppression de 35
3. Suppression d'un nœud avec deux enfants : lorsque l’on a atteint le nœud à supprimer, on remplace sa valeur par le max de son sous-arbre gauche (ou le min de son sous-arbre droit). Puis on remplace le nœud dont la valeur à été déplacée par son fils gauche (fils droit si on a pris le min du sous-arbre droit) ; voir suppression de 63.

5) Evolution des ABR vers des structures à arbres équilibrés (pas au programme).

On a vu que les ABR avait une complexité peu couteuse si l’ABR était et restait équilibré. Or, même en partant d’un arbre équilibré, les méthodes d’insertion et de suppression ne garantissent pas de maintenir cet ABR équilibré.

Un certain nombre d’autres structures d’ABR ont été développées, tel que les arbres AVL, les arbres rouge-noir, les arbres 2-3, etc. Leurs méthodes d’insertion et de suppression maintiennent les ABR équilibrés, au prix d’algorithmes plus complexes.