More than one rotation needed to balance an AVL Tr

问题:

My best guess is that one rotation is always enough to balance an AVL tree when you insert or delete ONE element from an already balanced AVL tree.

Is one rotation always enough? An example will help where more than one rotations are needed.

PS: I count RL/LR rotations as one rotation only.

回答1:

For insert 1 rotation is at most.
For delete the number of rotation is bounded by O(log(n)). Log(n) is the height of the tree.
More explanation on AVL deletion. When you delete a node from AVL you might cause the tree unbalanced, which you have to trace back to the point where it is unbalanced. If the unbalanced point is the root. You have to rebalance the tree from top to bottom.

回答2:

For insertion I believe one is enough.

but for deletion: consider this tree:

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

delete 15 , first the 25's balance factor is destructed, one rotation:

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

but still, we have to check, now the tree's root's balance factor is destructed, have to be rotated again:

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