Rotation des arbres binaires de recherche

Introduction

Définition : L’arbre binaire de recherche (ABR) est une structure de donnée particulière permettant de stocker des objets dans la mémoire de façon à ce que la complexité de recherche soit inférieure à celle d’une liste chaînée quelconque.

Elle suit les propriétés suivante :

  • Le sous-arbre droit de sa racine ne doit contenir que des étiquettes supérieures à la valeur de l'étiquette de la racine.
  • Le sous-arbre gauche, quant à lui doit contenir des étiquettes exclusivement inférieures à la racine.

Maintenant que nous savons ce qu'est un arbre binaire de recherche (ABR), nous allons nous intéresser au concept d'équilibre d'un ABR.
En effet, ce concept est très important afin d'avoir une meilleure complexité sur les opérations de recherches, d'insertions ainsi que de suppression d'éléments. Nous montrerons quelles sont les corrélations entre hauteur et complexité d'un arbre, puis nous proposerons une méthode de rééquilibrage d'un arbre de recherche, et enfin nous verrons une implémentation particulière d'un ABR (AVL) permettant de conserver un arbre d’équilibre partiel.

Durant tout le long du billet, nous avons mis un code couleur relatif à chaque type de paragraphe :

  • Gris : Définition, propositions ou remarque importante
  • Vert : Problématique ou questionnements
  • Bleu : Utilisation d'un programme p5.js

Relation entre hauteur et ABR

Remarque : Dans un ABR, la mise en espace d'un nœud ou feuille influe directement sur la complexité des opérations de l'arbre.

Proposition 1 : Soit un arbre binaire non vide de hauteur h et possédant n nœuds. On a :

L'image ci dessous représente un comparatif d'un ABR avec un AVL.

Source : wikipedia_Binary search tree & wikipedia_AVL tree

Une telle différence de complexité s'explique par la différence de hauteur de l'arbre. Prenons par exemple un ABR dont tous les nœuds gauches sont à NULL .

Exemple 1 : Opération de recherche d'un ABR dont tous les nœud gauche sont NULL
source : http://btv.melezinek.cz/binary-search-tree.html

L'arbre ci-dessus est ainsi l'équivalent d'une liste chaînée, pour trouver l'élément 5 sur un ensemble à 5 éléments, il a fallu 5 comparaisons. Soit une complexité de O(n)

Mais qu'en est-il d'un arbre peigne gauche (dont le fils droit de chaque nœud est une feuille)?

Exemple 2 : Opération de recherche sur un arbre peigne gauche
source : http://btv.melezinek.cz/binary-search-tree.html

Pour trouver l'élément 7, il a fallu 4 comparaisons. Soit une complexité O(n+1/2)=O(hauteur)~O(n) . Ainsi la hauteur d'un arbre influe sur la complexité des opérations d'un arbre.

Ainsi plus le ratio est fort, meilleure sera la complexité de l'arbre.

Dans le cas d'un arbre équilibré, où le ratio est le plus élevé, la hauteur maximale de l'arbre est O(log N). Nous pouvons le prouver en comptant la somme des nœuds

n = 1 + 2 + 4 + 8... + 2h-1 + 2h = 2h+1 - 1

Nous obtenons h= O(log n) avec h défini comme étant la hauteur.

Remarque : Ainsi la complexité de recherche, d'insertion et de suppression d'un arbre équilibré est égale à sa hauteur maximale.

Tout ceci nous amène donc à nous poser cette question :

Comment pouvons nous modifier la structure d'un ABR de telle sorte que la hauteur soit moins importante tout en gardant les propriétés d'un ABR ?

Une solution serait d'effectuer une rotation gauche ou droite en fonction de la hauteur de ses sous-arbres.

Rotation d'un ABR

Définition : La rotation sur les arbres binaires de recherches est un procédé qui consiste à modifier la structure de l'arbre, en faisant monter et descendre des nœuds, sans en modifier la cohérence.

Proposition 1. Les rotations préservent la propriété d’arbre binaire de recherche.

Le programme p5.js ci-dessous illustre la modification de structure en effectuant une rotation gauche ou droite.

(cliquez sur le programme pour effectuer une rotation vers la droite ou vers la gauche sur le sous-arbre de plus faible hauteur maximale)

Corollaire de la définition : Il est toujours possible d'appliquer les rotations d'un arbre afin de faire remonter un nœud jusqu'à la racine de l'arbre.

Il s'en suit une nouvelle problématique : Est-il toujours possible de transformer un ABR (dont toutes les clés de l'arbre sont différentes les unes des autres) en un autre ABR en utilisant le principe de rotation d'un arbre ?

Nous allons y répondre à partir d'une analyse menant vers un algorithme simpliste.

Dans le cas d'un arbre qui est vide, il est possible de convertir un arbre vide en un arbre vide.

Supposons que pour les deux ABR de 0 à n nœuds ayant les mêmes valeurs, il est toujours possible de convertir un ABR à un autre en utilisant des rotations. Nous allons prouver que pour tout ABR de n+1 clés, il est possible de convertir du premier arbre au second.

Selon le corollaire, il est toujours possible de faire remonter un nœud d'un sous-arbre.

Ainsi, s'il est possible de faire remonter un nœud d'un sous arbre, il sera possible de faire remonter l'ensemble des nœuds de telle sorte qu'il soit de la même forme que le second Arbre.

Ci-dessous le pseudo code permettant de faire en sorte que l'arbre A1 ait la même forme que l'arbre A2

Reshape(A1, A2) : 
    SI A1.hauteur==1 Then return;
    SINON Noeud n = trouveRacine(A1);
         SI n est fils gauche : 
               Applique la rotation droite
         SINON Applique la rotation gauche
         Reshape(A1.gauche,A2.gauche)
         Reshape(A1.droit, A2.droit)
    FINELSE

Soit une complexité en rotation de O(n)

Reprenons le cas d'un peigne droit, quel est le nombre minimal de rotations à effectuer pour transformer un peigne droit en peigne gauche ?

Illustration de rotation droite et gauche source : wikipedia _Tree rotation

Réponse : (hauteur maximale -1) rotations.

Remarque : Le principe de rotation d'un ABR est surtout utilisé pour réduire la hauteur maximale d'un arbre déséquilibré en descendant le sous-arbre ayant la hauteur la plus faible et remontant le sous-arbre ayant la hauteur la plus haute.

Comment pouvons nous implémenter une structure utilisant la rotation afin d'avoir un ABR qui maintient une hauteur la plus faible possible ?

Une solution serait d'implémenter un arbre AVL (Adelson-Velsky and Landis)

AVL

Définition : Un arbre binaire de recherche est un arbre AVL si, pour n’importe lequel de ses nœuds, la différence de hauteur entre ses deux fils diffère d’au plus un.

Propriété 1: La différence de hauteur d'un sous-arbre de nœuds est strictement inférieure à 2.

Propriété 2: Le rééquilibrage s'effectue lorsque la différence de deux sous-arbres d'un nœud est strictement supérieure à 1.

Après une opération d'insertion ou de suppression, un rééquilibrage par rotation s'effectue si le facteur équilibre est rompu.

Le programme p5.js représente un programme entier d'insertion et de suppression d'un nœud ou feuille d'un arbre AVL. Le rééquilibrage de l'arbre s'effectue automatiquement après l'opération d'insertion ou de suppression. Cliquez sur un noeud de l'arbre pour supprimer l'élément choisi. Cliquez sur une feuille tout en bas du programme pour insérer l'élément dans l'arbre. Si la hauteur est >5, l'arbre dépassera le cadre.

L'avantage de la structure AVL est qu'elle permet d'obtenir une complexité de recherche, d'insertion et de suppression de ~ O(log n).

L'inconvénient de cette structure est que chaque nœud doit stocker l'information de sa hauteur dans l'arbre (nécessaire dans le rééquilibrage), ce qui implique une consommation de mémoire supplémentaire de 4 octets par nœud sur un processeur x64 (en C). Cette implémentation reste très utilisée dans les bases de données dû à sa faible complexité de recherche.

Bibliographie

https://fr.wikipedia.org/wiki/Arbre_%C3%A9quilibr%C3%A9
https://fr.wikipedia.org/wiki/Arbre_AVL
https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche
https://en.wikipedia.org/wiki/Tree_rotation
https://users.cs.duke.edu/~reif/courses/alglectures/skiena.lectures/lecture10.pdf
Livre : "Introduction to Algorithms Third Edition" de Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein

Billet réalisé par LIN Christian, MARTIN Michael, LEE Victor

2 Cliquer pour recommander cet article