平衡AVL树需要多次旋转？

Question

我最好的猜测是,当您从已经平衡的AVL树插入或删除一个元素时,一次旋转总是足以平衡AVL树.

一次轮换总是足够吗？一个例子将有助于需要多次轮换.

PS:我将RL/LR旋转计为仅一次旋转.

Answer 1

对于插入物1,旋转最多.
对于删除,旋转次数由O(log(n))限定.Log(n)是树的高度.
关于AVL删除的更多解释.从AVL删除节点时,可能会导致树不平衡,您必须追溯到不平衡点.如果不平衡点是根.您必须从上到下重新平衡树.

Answer 2

对于插入，我相信一个就足够了。

但要删除：请考虑以下树：

                 50
              /      \
            25       75
           /   \    /   \
          15   40  60    80
               /  /  \    \
              35 55  65   90
                     /
                    62

删除15，首先破坏25的平衡因子，旋转一圈：

                 50
              /      \
            35       75
           /   \    /   \
          25  40  60    80
                  /  \    \
                 55  65   90
                     /
                    62

但是仍然，我们必须检查一下，现在树的根的平衡因子已被破坏，必须再次旋转：

                 60
              /      \
            50       75
           /   \     /  \
          35   55   65   80
         /  \       /     \
        25  40     62     90