AVL Деревья, похоже, имеют четыре вида преобразований: левые, левые, правые и правые. Однако, похоже, могут быть и другие обстоятельства. Я представляю это как левой Balanced:Дополнительные случаи в деревьях AVL
Ни влево, ни вправо вращения может сбалансировать это дерево. Какой алгоритм можно использовать для балансировки?
Оба 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.
Думаю, вы не можете получить шкалу слева. Потому что если вы построили левый баланс, вы можете сначала получить левое или левое право, затем дерево будет вращаться и сохранять равновесие.
Вы получаете каждый из изображенных случаев, удаляющих один узел из правого поддерева действительного дерева AVL. – greybeard
AV & L не выполнил процедуру балансировки _any_ упорядоченного двоичного дерева в дерево AVL с «не более чем одним двойным вращением». Они представили, как перебалансировать двоичное дерево после вставки одного узла, но одно из трех состояний/два дополнительных бита на узел. Это было расширено для других операций. Ни одно из трех «левых» деревьев, показанных выше, не может быть результатом добавления единственного узла к действительному дереву AVL, каждый из которых может привести к удалению одного узла, заслуживающего метку больше 50. Тем не менее, что (с точки зрения высоты) _is_ разные в узлах с метками 40 и 45 между «последними двумя левыми деревьями»? – greybeard