Équilibrage des arbres AVL

Question

Étant donné un arbre AVL ci-dessous :

        23
       /    \     
   19        35
  /  \      /  \     
 8   20   27    40
               /
             38
             /
            36

Est-ce correct de faire une seule rotation à 40, vers la droite ? Le rendant quelque chose comme ceci :

        23
      /    \     
   19        35
  /  \      /  \     
 8   20   27    38
               /  \
             36    40

Cela continue de respecter la propriété AVL d'avoir une hauteur de +- 1 par rapport au sous-arbre de gauche.

Dans la réponse, il fait une double rotation, donc le sous-arbre à 35 ci-dessus ressemblerait à ceci après :

        23
      /    \     
   19        38
  /  \      /  \     
 8   20   35    40
         /  \
        27  36    

Je ne comprends pas quand faire une double rotation et quand faire une rotation simple si elles ne violent toutes deux pas la propriété de hauteur.

Answer 1

La double rotation peut être due à un algorithme AVL spécifique en cours d'utilisation. Les deux réponses me semblent être des arbres AVL valides.

Answer 2

Si la question initiale a été donnée avec seulement l'arbre AVL déséquilibré (et non l'arbre équilibré avant qu'un noeud ne soit ajouté ou supprimé), alors la rotation simple est une réponse valable.

Si la question fournit l'arbre AVL avant et après qu'un nœud a été ajouté ou supprimé, alors l'algorithme de rééquilibrage pourrait entraîner une double rotation.

Answer 3

Les deux réponses sont bonnes, bien que selon la littérature que j'utilise:

Il existe quatre types de rotations LL, RR, LR et RL. Ces rotations sont caractérisées par l'ancêtre le plus proche A, du nœud inséré N, dont le facteur d'équilibre devient 2.

La caractérisation des types de rotations est la suivante:

1. LL: N est inséré dans le sous-arbre gauche du sous-arbre gauche de A
2. LR: N est inséré dans le sous-arbre droit du sous-arbre gauche de A
3. RR: N est inséré dans le sous-arbre droit du sous-arbre droit de A
4. RL: N est inséré dans le sous-arbre gauche du sous-arbre droit de A

En suivant ces règles, l'ancêtre le plus proche dont le facteur d'équilibre devient 2 est 40 dans votre exemple, et l'insertion a été faite dans le sous-arbre gauche du sous-arbre gauche de 40 donc vous devez effectuer une rotation LL. En suivant ces règles, la première de vos réponses sera l'opération choisie.

Cependant, les deux réponses sont correctes et dépendent de l'algorithme que vous utilisez et des règles qu'il suit.