Балансировка деревьев AVL

Question

Учитывая дерево AVL ниже:

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

Можно ли сделать один оборот вправо на 40? Сделать это примерно так:

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

Он по-прежнему соответствует свойству AVL, имеющему - + 1 высоту по сравнению с левым поддеревом.

В ответе выполняется двойное вращение, поэтому поддерево на 35 выше будет выглядеть следующим образом:

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

Я не понимаю, когда делать двойной поворот, а когда делать один поворот, если они оба не нарушают свойство высоты.

Answer 1

Если исходный вопрос был задан только с несбалансированным деревом AVL (а не с сбалансированным деревом до того, как был добавлен или удален узел), то единственное вращение является правильным ответом.

Если вопрос содержитДерево AVL до и после добавления или удаления узла, тогда алгоритм перебалансировки может привести к двойному повороту.

Answer 2

Двойное вращение может быть связано с использованием конкретного алгоритма AVL.Оба ответа для меня выглядят как действительные деревья AVL.

Answer 3

Оба ответа верны, хотя согласно литературе, которую я использую:

Это четыре типа вращений LL, RR, LR и RL. Эти вращения характеризуются ближайшим предком A вставленного узла N, у которого коэффициент баланса становится равным 2.

Получается следующая характеристика типов вращения:

1. LL: N вставляется в левое поддерево левого поддерева A
2. LR: N вставляется в правое поддерево левого поддерева A
3. RR: N вставляется вправое поддерево правого поддерева A
4. RL: N вставляется в левое поддерево правого поддерева A

Согласно этим правилам ближайший предокв вашем примере коэффициент баланса равен 2, равный 40, и вставка была сделана в левое поддерево левого поддерева 40, поэтому необходимо выполнить вращение LL.Следуя этим правилам, первым из ваших ответов будет выбранная операция.

Тем не менее оба ответа верны и зависят от используемого вами алгоритма и правил, которым он следует.