AVL équilibrage

Question

Étant donné un arbre AVL ci-dessous:

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

Est-il autorisé à faire une seule rotation à 40, à droite? Faire quelque chose comme ceci:

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

encore tot il est conforme propriété AVL d'avoir -. + 1 hauteur par rapport à la sous-arbre gauche

Dans la réponse, il fait une double rotation de sorte que le sous-arbre à 35 serait au-dessus de ressembler à 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 seule rotation si les deux ne violent pas la propriété de hauteur.

Answer 1

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

Answer 2

Si la question initiale a été donnée avec seulement l'arbre asymétrique AVL (et non l'arbre équilibré avant un nœud a été ajouté ou supprimé), la seule rotation est une réponse valable.

Si la question fournit l'arbre AVL avant et après un noeud a été ajouté ou supprimé, l'algorithme de rééquilibrage pourrait entraîner la double rotation se produise.

Answer 3

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

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

La caractérisation suivante des types de rotation, on obtient:

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

Selon ces règles, l'ancêtre le plus proche dont le facteur de l'é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 de sorte que vous devez effectuer une rotation de LL. Suite à ces règles, la première de vos réponses sera l'opération choisie.

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