Четыре поворота дерева AVL не работают

Мы знаем, что для поддержания баланса бинарного дерева мы можем использовать RR LL RL LR четыре поворота, чтобы сбалансировать дерево дисбаланса. Но если у нас есть дерево баланса в виде потоков:

        885
        / \
       /   \
     659   912
     / \     \
    /   \    934
  212   759
  / \
 /   \
11   344

если мы добавим к этому дереву узел (168) и дерево вот так:

        885
        / \
       /   \
     659   912
     / \     \
    /   \    934
  212   759
  / \
 /   \
11   344
 \
 168

дерево не сбалансировано, но я не могу использовать ни один из четырех поворотов (RR, LL, RL, LR), чтобы снова сбалансировать дерево. кто-нибудь СКАЖЕТ почему?


tree avl-tree
person sundq    schedule 20.11.2016    source источник
comment
ты видел ответ?   -  person guymaor86    schedule 29.11.2016
comment
да, ты очень хорошо отвечаешь   -  person sundq    schedule 06.12.2016

Ответы (1)


arrow_upward
1
arrow_downward

Дерево оставлено тяжелым, но левое поддерево дерева не оставлено тяжелым, вам нужно только сделать поворот вправо. После поворота вправо дерево будет выглядеть следующим образом:

                 659
                /   \
               /     \
             212      885
             / \      /  \
            /   \    /    \
           11   344  759   912
             \               \
              \               \
               168             934

Попробуйте использовать следующий алгоритм для выбора метода:

IF tree is right heavy {
 IF tree's right subtree is left heavy {
   Perform Double Left rotation
 }
 ELSE{
   Perform Single Left rotation
 }
}
ELSE IF tree is left heavy {
 IF tree's left subtree is right heavy {
   Perform Double Right rotation
 }
 ELSE {
   Perform Single Right rotation
 } 
}
person guymaor86    schedule 20.11.2016