Arbres binaires de recherche

En informatique, un arbre binaire de recherche est une structure de données. Décryptage avec Olivier, professeur de numérique et sciences informatiques.

Attention, ce cours nécessite de connaître quelques notions de programmation orientée objet.

Téléchargez le support de cours en PDF.

Structure de dictionnaire

Qu’est-ce qu’un dictionnaire ?

Un dictionnaire est un ensemble d’entrées constituées de clés associées à des données. Toutes les clés présentes dans un dictionnaire sont distinctes. Exemple : un dictionnaire de langues comporte des entrées (mots). Ces mots sont associés à leurs données (leurs définitions).

Pour interroger et modifier un dictionnaire de manière efficace, il faut utiliser un tableau qui contient toutes les clés nécessaires. Les données doivent êtres triées (comme un dictionnaire classé par ordre alphabétique) pour éviter de parcourir une à une les valeurs. 

Pourquoi utiliser la méthode dichotomique ?

En informatique, on va utiliser alors la méthode dichotomique. Elle consiste à ouvrir le dictionnaire au milieu, regarder le mot et le comparer aux mots que l’on cherche à trouver : soit c’est le mot que l’on cherche, soit on continue la recherche dans la première ou dans la deuxième moitié du dictionnaire. Dans ce cas-là, la complexité est de l’ordre du O(log₂ n).

Pour un dictionnaire de 60 000 mots triés, le O(log₂ n) sera égal à 16. En effet, avec la méthode de recherche dichotomique, on aura seulement besoin de regarder 16 mots, et non 60 000. Voilà pourquoi cette méthode est efficace.

Comment modifier un dictionnaire ?

Si on veut ajouter ou supprimer un mot : 

- Dans le cas d’un dictionnaire non trié, il faudra parcourir intégralement le livre pour s’assurer au préalable que le mot n’est pas déjà présent dans le dictionnaire. S’il n’est pas présent, il faudra le placer à la fin.

- Dans le cas du tableau trié, la recherche dichotomique va nous permettre de savoir rapidement si le mot est présent et d’identifier sa position. Si le mot n’est pas présent, il faudra faire de la place. On va avoir besoin de décaler tous les mots. Ce n’est pas idéal.

Pour être plus efficace, on utilise alors la structure de données, appelée « arbre binaire. ».  

Arbres binaires

Qu’est-ce qu’un arbre binaire ?

Un arbre binaire est une structure arborescente où chaque nœud de l’arbre contient une valeur. Chaque nœud peut avoir éventuellement un sous arbre gauche et un sous arbre droit.

Cela se traduit en Python à l’aide d’une classe. La « clé » est la valeur, « gauche » ou « droite » sont les sous arbre. S’il n’y a pas d’arbre, on va utiliser une valeur spéciale, qu’on appelle « None ».

a.gauche.droite = ArbreBinaire(3) → Cela signifie qu’on ajoute au sous arbre gauche, un sous arbre à droite d’une valeur de 3.

Qu’est-ce qu’un parcours infixe ?

Pour parcourir un arbre binaire, il faut faire un parcours infixe. Dans un parcours infixe, on va commencer par s’intéresser aux valeurs présentes dans le sous arbre gauche (4, 2, 3). Puis, on va prendre la valeur du nœud courant (5), et ensuite on parcourra le sous arbre droit (8). On parle de parcours infixe lorsque la valeur du nœud courant est traitée entre le sous arbre gauche et le sous arbre droit.

Donc, le parcours va s’écrire en Python, à l’aide d’une fonction récursive :

def parcours_infixe(arbre): → on a une fonction parcours infixe avec l’arbre qu’on veut parcourir.

if arbre != None:  → Si arbre n’est pas égale à « None », alors :

parcours_infixe(arbre.gauche) → On parcourt le sous arbre gauche, à l’aide d’un récursif à la même fonction.

print(arbre.clé) → Puis, on va traiter la valeur courante de l’arbre qu’on est en train de voir.

parcours_infixe(arbre.droit) → Enfin, on va parcourir le sous arbre droit, à l’aide d’un appel à la fonction « parcours infixe ».

Donc, cette fonction permet de voir, une à une, les différentes valeurs présentes dans l’arbre en se déplaçant de la gauche vers la droite.

Comparer un parcours infixe d’un arbre binaire et d’un arbre binaire de recherche

À gauche, les valeurs affichées ne sont pas ordonnées. Dans la figure de droite, les valeurs affichées sont ordonnées. C’est donc ce deuxième type d’arbre qu’on appelle un « arbre binaire de recherche ». Avoir des valeurs ordonnées est très pratique. Cela permet d’avoir des algorithmes plus performants. Don, un arbre binaire de recherche est très pratique.

Arbres binaires de recherche

Qu’est-ce qu’un arbre binaire de recherche ?

Un arbre binaire de recherche est un arbre binaire dont le parcours infixe fournit des valeurs dans un ordre strictement croissant. En d’autres mots, la clé à la racine d’un arbre binaire de recherche (ou d’un sous arbre) est toujours :

- plus grande que les clés présentes dans son fils gauche

- plus petite que les clés présentes dans son fils droit.

Comment chercher dans un arbre binaire de recherche ?

La fonction principale de cet arbre est la fonction de recherche.

Exemple :

On veut savoir si la valeur 9 est présente dans cet arbre. On commence par la racine (4). 9 étant plus grand que 4, alors on va poursuivre la recherche dans le sous arbre droit. Là, on rencontre un 10. Ce chiffre est plus grand que 9. Alors, on va continuer à gauche. On arrive à 8 qui est plus petit que 9. On continue donc à droite. Là, on tombe sur 9, la valeur recherchée.

→ Quand on cherche une valeur, on sait qu’à chaque embranchement, on va prendre à gauche ou à droite. On n’a pas besoin de parcourir tout l’arbre.

Cela se programme en Python :  

def est_présent(arbre, valeur):

if arbre == None: → Si l’arbre est vide, il ne contient aucune valeur.

return False

elif arbre.clé == valeur: → on a trouvé la valeur qu’on était en train de chercher.

return True

Comment insérer dans un arbre binaire de recherche ?

Pour insérer une valeur, il faut d’abord réfléchir à l’endroit où devrait être la clé 3 si elle était présente dans cet arbre. On part alors de la racine 4, puis on descend à gauche car 3 est plus petit que 4. On tombe sur 2, qui est plus petit que 3. Donc, 3 devrait être dans le sous arbre droit à partir de 2. Mais, là il n’y a rien. C’est à cet endroit précisément qu’on va ajouter la nouvelle valeur.

La fonction va s’écrire de la manière suivante :

def insérer(arbre, valeur):

# On suppose que arbre != None

if arbre.clé < valeur:

# On regarde dans le sous-arbre droit

if arbre.droit == None:

arbre.droit = ArbreBinaire(valeur)

else:

insérer(arbre.droit, valeur)

elif arbre.clé > valeur: → Si on doit aller à gauche.

# On regarde dans le sous-arbre gauche

if arbre.gauche == None:

arbre.gauche = ArbreBinaire(valeur) → Si la clé égal à la valeur, alors, on s’arrête car la clé est déjà présente.

else:

insérer(arbre.gauche, valeur)

Comment rendre efficace un arbre binaire de recherche complexe ?

On peut trouver différentes formes d’arbre. 

Plus l’arbre va être de petite hauteur, plus il va être rempli vers le haut et plus les opérations seront efficaces. Il s'agit de la première figure à gauche. On a un arbre complet. Celui-ci est plus efficace. À l’inverse, on a ce qu’on appelle un « peigne » : on se dirige dans une seule direction. L’arbre à gauche contient 16 nœuds et sa hauteur est 4, c’est-à-dire qu’on va avoir 4 étapes d’appels récursifs. Dans le cas d’un peigne, sa hauteur serait de 16 étapes. Il est donc moins efficace.  

Supposons maintenant qu’on a 60 000 valeurs à insérer. Si on avait un peigne, la hauteur de l’arbre serait de 60 000 étapes. Si on avait un arbre complet, ces 60 000 valeurs donneraient un arbre de hauteur 15 étapes.

Pour restructurer au fur et à mesure l’arbre afin qu’il ne se transforme pas en peigne, on prend ce peigne par milieu, c’est-à-dire qu’on divise la hauteur par deux. Si on répète ce processus sur chaque côté, on obtient un arbre complet et on réussit à faire décroitre la hauteur de l’arbre.