Относительно вращений AVL

Question

Я читаю о деревьях AVL в структурах данных и алгоритмах. Автор Mark Allen Wesis

Предположим, что перебалансированным узлом является X. Есть 4 случая, которые нам, возможно, придется исправить (двазеркальные изображения двух других): вставка в левое поддерево левого дочернего элемента X, вставка в правое поддерево левого дочернего элемента X, вставка в левое поддерево правого дочернего элемента X или вставкав правом поддереве правого потомка X.

Баланс восстанавливается с помощью поворотов деревьев.

Ниже приведены вопросы, которые у меня есть к приведенному выше фрагменту текста.

1. Что автор имеет в виду под зеркальными изображениями двух других?
2. Что такое симметричный случай в одном вращении и двойном вращении?

Спасибо

Answer 1

Предположим, что вставляемый узел - это I. В книге сказано, что есть 4 случая. Давайте возьмем тот, где я - левый потомок левого потомка X:

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

«Зеркало» этого - то, когда я - правильный ребенок правильного ребенка X:

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

Причина, по которой это «зеркало», заключается в том, что повороты, которые вы должны сделать для обоих случаев, одинаковы, только с изменением влево и вправо. То же самое относится и к двум другим случаям, когда я - левый ребенок правого ребенка X и где я - правый ребенок левого ребенка X.

Что касается вашего второго вопроса, идея та же самая. В симметричном случае (т. Е. В зеркале) вы делаете те же повороты, только с перевернутыми влево и вправо.