Arbres binaires de recherche

I/ Définition

1) Arbre binaire de recherche

Un arbre binaire de recherche est un arbre binaire dont tous les nœuds portent des étiquettes numériques rangées dans l'ordre croissant, au sens suivant : l'étiquette portée par un nœud est à la fois plus grande que toutes les étiquettes de son enfant gauche, et plus petite que toutes les étiquettes de son enfant droit.

2) Exemple

3) Représentation en Python

La classe BST ressemble à la classe Arbre des arbres binaires, à ceci près que l'étiquette n'est plus une chaîne de caractères mais un nombre.

On peut donc créer l'arbre ci-dessus avec

T = BST(34)
T.greffe_gauche(BST(5))
T.G.greffe_gauche(BST(2))
T.G.G.greffe_gauche(BST(1))
T.G.G.greffe_droite(BST(3))
T.G.greffe_droite(BST(13))
T.G.D.greffe_gauche(BST(8))
T.G.D.greffe_droite(BST(21))
T.greffe_droite(BST(233))
T.D.greffe_gauche(BST(89))
T.D.G.greffe_gauche(BST(55))
T.D.G.greffe_droite(BST(144))
T.D.greffe_droite(BST(610))
T.D.D.greffe_gauche(BST(377))
T.D.D.greffe_droite(BST(987))

II/ Algorithmes

On considère la classe BST suivante :

class BST():
    def __init__(self,label):
        self.label = label
        self.G = None
        self.D = None
    def greffe_gauche(self,greffe):
        self.G = greffe
    def greffe_droite(self,greffe):
        self.D = greffe
    def __repr__(self):
        return str(self.G).replace('None','.')+str(self.label)+str(self.D).replace('None','.')

1) Recherche

Comme les étiquettes d'un arbre binaire de recherche sont triées dans l'ordre croissant, on peut effectuer une recherche dichotomique. On le fait sous forme d'une méthode appelée dedans :

class BST():
    ...
    def dedans(self,clef):
        if self.label==clef:
            return True
        elif self.label>clef and self.G is not None:
            return self.G.dedans(clef)
        elif self.label<clef and self.D is not None:
            return self.D.dedans(clef)
        else:
            return False

Dans le cas d'un arbre équilibré, cet algorithme est de coût logarithmique : le nombre de comparaisons à effectuer ne dépasse pas la hauteur de l'arbre, et celle-ci est le nombre de chiffres binaires de la taille de l'arbre.

2) Insertion

On propose l'algorithme récursif suivant :

• Si l'élément à insérer est plus petit que l'étiquette de la racine, on l'insère dans l'enfant gauche.
• S'il est plus grand que l'étiquette de la racine, on l'insère dans l'enfant droit.
• Insérer un élément dans un arbre vide, c'est donner cet élément comme étiquette à l'arbre (qui du coup n'est plus vide).

class BST():
    ...
    def ajouter(self,clef):
        assert not self.dedans(clef)
        if self.label>clef:
            if self.G is None:
                self.greffe_gauche(BST(clef))
            else:
                self.G.ajouter(clef)
        elif self.label<clef:
            if self.D is None:
                self.greffe_droite(BST(clef))
            else:
                self.D.ajouter(clef)
        else:
            self=BST(clef)

Le script suivant permet alors de construire l'arbre binaire de recherche :

T = BST(1)
for n in [2,3,5,8,13,21,34,55,89,144,233,377,610,987]:
    T.ajouter(n)

Mais cela ne garantit pas que l'arbre obtenu soit équilibré :

En insérant les éléments dans un ordre aléatoire, on a un arbre plus équilibré que le cas unaire ci-dessus. Par exemple :

La recherche d'une clé dans un dictionnaire se fait en simulant le hasard par une fonction de hachage (en Python, hash()). Une table de hachage est un arbre mais pas binaire. Cependant elle mène à la notion d'arbre de Merkle qui est bien binaire.