Дополнительные случаи в деревьях AVL

Question

Деревья AVL, кажется, имеют четыре вида преобразований: левый-левый, левый-правый, правый-левый и правый-правый. Однако, похоже, могут быть и другие обстоятельства. Я представляю это как левостороннее:

Ни левые, ни правые повороты не могут сбалансировать это дерево. Какой алгоритм можно использовать, чтобы сбалансировать его?

Answer 1

Здесь можно применять как LL, так и LR

        50
       /  \
     40    55
    /  \
  35    45
  / \   / \
34  36 44 46

После первого поворота LR:

           50
          /  \
        45   55
       /  \
     40    46
    /  \
  35    44
  / \
34  36

После второго поворота LR:

        45
       /  \
     40    50
    / \    / \
  35  44  46  55
 / \
34  36

Это действительное дерево AVL. Обратите внимание, что

В дереве AVL высоты двух дочерних поддеревьев любого узла отличаются не более чем на один

Вы также можете сделать LL очередь:

     40
    /  \
  35    50
  / \   / \
34  36 45  55
       /\
     44  46

Опять же, это действительное дерево AVL.

Answer 2

Я думаю, что вы не можете получить левый баланс. Потому что, если вы построили левый баланс, вы можете сначала получить левый-левый или левый-правый, тогда дерево будет вращаться и сохранять равновесие.