En ce qui concerne les rotations AVL

Question

Je suis en train de lire sur les arbres AVL dans les structures de données et algorithmes par Mark Allen Wesis

Supposons que le noeud à rééquilibrée est X. Il y a 4 cas que nous pourrait avoir à fixer (deux sont les images miroir des deux autres): Un insertion dans le sous-arbre gauche de l'enfant gauche de X, une insertion dans le sous-arbre droit de l'enfant gauche de X, une insertion dans la gauche arborescence de l'enfant droit de X, ou une insertion dans le sous-arbre droit de l'enfant droit de X.

L'équilibre est rétabli par la rotation des arbres.

Après sont des questions que j'ai sur extrait de texte ci-dessus.

1. Que signifie auteur par des images miroir des deux autres?
2. Quel est le cas symétrique en rotation simple et double rotation?

Merci

Answer 1

Supposons que le noeud à insérer est I. Le livre dit qu'il ya 4 cas. Prenons celui où l'enfant I est à gauche de l'enfant gauche de X:

    X
   / \
  ?   ?
 / \ / \
I  ? ?  ?

Le « miroir » de c'est quand j'est l'enfant droit de l'enfant à droite de X:

    X
   / \
  ?   ?
 / \ / \
?  ? ?  I

La raison pour cela est un « miroir » est que les rotations que vous avez à faire pour les deux cas sont les mêmes, juste avec gauche et droite inversées. La même chose vaut pour les deux autres cas où je l'enfant est à gauche de l'enfant droit de X et où I est l'enfant droit de l'enfant gauche de X.

En ce qui concerne votre deuxième question, l'idée est la même. Dans le cas symétrique, (par exemple le cas du miroir), vous faites les mêmes rotations, juste avec gauche et droite inversées.