Arbres AVL

Un arbre AVL est un arbre binaire tel que la différence des hauteurs des deux sous-arbres ne dépasse pas 1. La hauteur d'un arbre est définie récursivement de la manière suivante :

• La hauteur $H(t)$ est $0$ si $t$ est l'arbre vide,
• La hauteur $H(t)$ d'un arbre $t$ non vide est $1+\texttt{max}(H(t.l), H(t.r))$ où $t.l$ et $t.r$ indiquent les sous-arbres gauche et droit de $t$ respectivement.

La condition AVL d'un arbre $t$ est donc respectée si et seulement si $\vert H(t.l) - H(t.r)\vert \le 1$. Un arbre binaire de recherche $t$ est un arbre AVL si et seulement si la condition AVL est respectée dans chaque sous-arbre de $t$ (y compris dans $t$).

L'arbre présenté dans la figure 23.12 n'est pas un arbre AVL, car le sous-arbre dont la racine est 33 ne respecte pas la condition AVL. En effet, le sous-arbre gauche de ce sous-arbre a une hauteur nulle tandis que son sous-arbre droit a une hauteur de $3$. Tous les autres sous-arbres de l'arbre de la figure 23.12 respectent la condition AVL.

La hauteur d'un arbre AVL est $O(\texttt{log} n)$ où $n$ est le nombre d'éléments de l'arbre. En conséquence, les opérations de recherche, d'insertion et de suppression ont aussi une complexité asymptotique de $O(\texttt{log} n)$.

La recherche dans un arbre AVL est identique à celle d'un arbre binaire de recherche (voir section 23.4.1). L'insertion et la suppression nécessitent des modifications supplémentaires pour que la condition AVL soit respectée dans chaque sous-arbre.

Ces modifications dépendent de quelques observations cruciales :

• l'insertion ou la suppression d'un élément dans un arbre binaire de recherche peut changer la profondeur d'un sous-arbre quelconque d'au plus $1$ ,
• l'insertion ou la suppression d'un élément dans un arbre peut provoquer une violation de la condition AVL uniquement sur le chemin compris entre la racine et le point d'insertion ou de suppression.

Il suffit alors, après une insertion ou une suppression, de vérifier si la condition AVL est respectée. Si ce n'est pas le cas, la différence de profondeur des deux sous-arbres ne dépasse pas $2$. Il nous faut donc une méthode pour transformer un arbre binaire dont les deux sous-arbres sont des arbres AVL, mais dont la racine ne respecte pas la condition AVL car la différence de profondeur entre les deux sous-arbre est exactement $2$.

Cette méthode utilise la notion de rotation. La rotation est une réorganisation locale des nuds autour de la racine de l'arbre. Il y a deux types de rotations, la rotation à droite et la rotation à gauche. Les deux sont symétriques. La figure 23.14 montre la rotation à droite d'un arbre binaire. Cette rotation nécessite l'existence d'un sous-arbre gauche non vide. De la même façon, la rotation à gauche nécessite l'existence d'un sous-arbre de droite non vide. Les sous-arbres indiqués par des triangles sont des arbres arbitraires et peuvent être vides.

Figure 23.14: Rotation à droite

La première chose à vérifier est qu'après la transformation, l'arbre est toujours un arbre binaire de recherche, à savoir que tous les nuds du sous-arbre gauche sont inférieurs à la racine et que la racine est inférieure à tous les nuds du sous-arbre droit, et ceci pour tous les nuds de l'arbre. Il s'agit de vérifier qu'après la transformation il est vrai que :

• tous les nuds du sous-arbre $A$ sont inférieurs à $y$,
• tous les nuds du sous-arbre $B$ sont supérieurs à $y$ mais inférieurs à $x$,
• $y$ est inférieur à $x$,
• tous les nuds du sous-abre $C$ sont supérieurs à $x$.

C'est clairement le cas, car ce sont les mêmes conditions qui garantissent que l'arbre avant la transformation est un arbre binaire de recherche.

La rotation peut être utilisée pour rééquilibrer un arbre AVL après une insertion ou une suppression. Nous allons supposer qu'une insertion a été effectuée dans le sous-arbre gauche ou qu'une suppression a été effectuée dans le sous-arbre droit. Le cas inverse est traité de manière symétrique. On suppose de plus que les deux sous-arbres sont déjà récursivement équilibrés et donc des arbres AVL, mais que la racine ne respecte pas la condition AVL. Par hypothèse, le sous-arbre gauche à une hauteur qui dépasse de $2$ celle du sous-arbre droit. Si l'on suppose que la hauteur du sous-arbre droit est $h$, la hauteur du sous-arbre gauche est donc forcément $h+2$. Nous avons donc l'un des deux cas indiqués par la figure 23.15.

Figure 23.15: Hauteurs après insertion ou suppression

Le premier cas (indiqué à gauche dans la figure 23.15) est relativement simple à corriger. Il suffit d'appliquer une rotation à droite. Ceci donne la situation de la figure 23.16. La racine respecte clairement la condition AVL.

Figure 23.16: Correction par rotation à droite

Le deuxième cas (indiqué à droite dans la figure 23.15) est plus compliqué. Puisque le sous-arbre $B$ a la profondeur $h+1$, il n'est forcément pas vide. La figure 23.17 montre une vue plus détaillée de ce cas.

Figure 23.17: Cas numéro 2 plus détaillé

Une rotation simple à droite ne résout pas le problème, car l'arbre qui en résulte n'est pas AVL. Pour résoudre ce problème, il faut appliquer une double rotation. D'abord une rotation à gauche du nud $y$, puis une rotation à droite du nud $x$. Cette opération est présentée dans les figures 23.18 et 23.19.

Figure 23.18: Correction par double rotation (1)

Figure 23.19: Correction par double rotation (2)

Pour le code de l'insertion et de la suppression, plutôt que d'utiliser le système avec deux valeurs de retours (voir section 23.4.1), nous allons utiliser un système de conditions (voir chapitre 18). Ceci simplifie le code considérablement. Deux conditions sont utilisées, element-not-in-avl (si un élément donné à la suppression n'est pas dans l'arbre) et element-already-in-avl (si un élément à l'inserer est déjà dans l'arbre).

Voici la définition de ces conditions :

(define-condition element-not-in-avl (error)
  ())

(define-condition element-already-in-avl (error)
  ())

La cellule doit être augmentée d'un champ pour stocker la hauteur :

(defstruct avlcell
  elem
  (height 1)
  (left nil)
  (right nil))

Pour déterminer la hauteur d'un arbre, il est utile de définir une fonction. Cette fonction doit donner la réponse $0$ pour l'arbre vide :

(defun avl-height (tree)
  (if tree
      (avlcell-height tree)
      0))

Après modification de la structure de l'arbre, il faut recalculer la hauteur. Il est utile de définir une fonction pour le faire. Cette fonction renvoie toujours l'argument passé plutôt qu'une valeur inutile, ce qui simplifie son utilisation :

(defun recompute-height (tree)
  (setf (avlcell-height tree)
        (1+ (max (avl-height (avlcell-left tree))
                 (avl-height (avlcell-right tree)))))
  tree)

Les deux fonctions de rotation marchent comme celles d'insertion et de suppression, à savoir qu'elles modifient la structure de l'arbre, mais c'est la valeur de retour qu'il faut utiliser. Les voici :

(defun rotate-left (tree)
  (let ((result (avlcell-right tree)))
    (setf (avlcell-right tree) (avlcell-left result)
          (avlcell-left result) (recompute-height tree))
    (recompute-height result)))

(defun rotate-right (tree)
  (let ((result (avlcell-left tree)))
    (setf (avlcell-left tree) (avlcell-right result)
          (avlcell-right result) (recompute-height tree))
    (recompute-height result)))

Deux autres fonctions peuvent être utiles. Il s'agit de tester, après insertion ou suppression, si une rotation (simple ou double) est nécessaire et dans ce cas d'effectuer la rotation ainsi que de recalculer la hauteur :

(defun possibly-rotate-right (tree)
  (cond ((<= (avl-height (avlcell-left tree))
             (1+ (avl-height (avlcell-right tree))))
         (recompute-height tree))
        ((> (avl-height (avlcell-right (avlcell-left tree)))
            (avl-height (avlcell-left (avlcell-left tree))))
         (setf (avlcell-left tree)
               (rotate-left (avlcell-left tree)))
         (recompute-height (rotate-right tree)))
        (t (recompute-height (rotate-right tree)))))

(defun possibly-rotate-left (tree)
  (cond ((<= (avl-height (avlcell-right tree))
             (1+ (avl-height (avlcell-left tree))))
         (recompute-height tree))
        ((> (avl-height (avlcell-left (avlcell-right tree)))
            (avl-height (avlcell-right (avlcell-right tree))))
         (setf (avlcell-right tree)
               (rotate-right (avlcell-right tree)))
         (recompute-height (rotate-left tree)))
        (t (recompute-height (rotate-left tree)))))

La fonction d'insertion peut maintenant être définie comme ceci :

(defun avl-insert (elem tree &key (test #'<) (key #'identity))
  (cond ((null tree) (make-avlcell :elem elem))
        ((funcall test
                  elem
                  (funcall key (avlcell-elem tree)))
         (setf (avlcell-left tree)
               (avl-insert elem (avlcell-left tree)
                           :test test :key key))
         (possibly-rotate-right tree))
        ((funcall test
                  (funcall key (avlcell-elem tree))
                  elem)
         (setf (avlcell-right tree)
               (avl-insert elem (avlcell-right tree)
                           :test test :key key))
         (possibly-rotate-left tree))
        (t (error 'element-not-in-avl))))

Voici finalement la fonction de suppression :

(defun avl-delete (elem tree &key (test #'<) (key #'identity))
  (cond ((null tree) (error 'element-not-in-avl))
        ((funcall test
                  elem
                  (funcall key (avlcell-elem tree)))
         (setf (avlcell-left tree)
               (avl-delete elem (avlcell-left tree)
                             :test test :key key))
         (possibly-rotate-left tree))
        ((funcall test
                  (funcall key (avlcell-elem tree))
                  elem)
         (setf (avlcell-right tree)
               (avl-delete elem (avlcell-right tree)
                             :test test :key key))
         (possibly-rotate-right tree))
        ((null (avlcell-left tree)) (avlcell-right tree))
        ((null (avlcell-right tree)) (avlcell-left tree))
        (t (labels ((delete-largest (tree)
                      (if (null (avlcell-right tree))
                          (values (avlcell-left tree)
                                  (avlcell-elem tree))
                          (multiple-value-bind (rtree elem)
                              (delete-largest (avlcell-right tree))
                            (setf (avlcell-right tree) rtree)
                            (values (possibly-rotate-right tree)
                                    elem)))))
             (multiple-value-bind (ltree elem)
                 (delete-largest (avlcell-left tree))
               (setf (avlcell-left tree) ltree
                     (avlcell-elem tree) elem)
               tree)))))

Alors que la complexité asymptotique des opérations de recherche, d'insertion et de suppression dans un arbre AVL est $O(\texttt{log} n)$, le facteur multiplicatif est assez considérable. Pour être rentable par rapport à un conteneur dont la complexité est $O(n)$, comme une liste ou un vecteur, l'arbre AVL doit contenir au moins une centaine d'éléments.

Ce qui coûte cher dans la manipulation d'un arbre AVL est la garantie que chaque opération peut être effectuée avec une complexité de $O(\texttt{log} n)$. On peut faire mieux si on peut se contenter d'une performance probabiliste, à savoir que probablement la plupart des opérations coûtent $O(\texttt{log} n)$.

De plus, si on possède une connaissance de la façon dont sont effectuées les opérations, par exemple que les éléments de deux insertions ou de deux suppressions consécutives ne sont pas très éloignés dans l'ordre défini sur le domaine, un vecteur avec trou (voir section 23.3.4) ou un conteneur similaire peut être plus avantageux par rapport à un arbre AVL.

Un autre problème avec les arbres AVL est le surcoût de consommation de mémoire non négligeable avec au moins 4 (probablement 5 avec l'en-tête) mots de perte par élément. Un arbre AVL avec quelques milliers d'éléments peut donc facilement remplir le cache du processeur, alors qu'un vecteur peut stocker plusieurs dizaines de milliers d'éléments sans remplir le cache. Bien sûr, le cache est un problème uniquement si le conteneur est parcouru entièrement et relativement souvent.