AVL 树四轮旋转不起作用

Question

我们知道要保持二叉树平衡，我们可以使用 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）中的任何一个来使树再次平衡。谁能告诉我为什么？

Answer 1

树是左重的，但是树的左子树不是左重的，只需要右旋一次就可以了。向右旋转后，树将如下所示：

                 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
 } 
}

AVL 树四轮旋转不起作用

The AVL tree four rotate is not works

tree

avl-tree