[Solved]: Why do we need double-rotations to rebalance AVL trees?

Problem Detail: 

I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree:

• Left High (LH) tree is a tree tree with the height of the left subtree more than that of right subtree.
• Right High (RH) tree is a tree with the height of the right subtree more than that of left subtree.

Then the book says:

Insertion of a node may make an AVL tree height unbalanced. All height unbalanced trees fall in one of these four cases:

• LH of LH — A subtree of a tree that is left high has also become left high.
• RH of RH — A subtree of a tree that is right high has also become right high.
• RH of LH — A subtree of a tree that is left high has become right high.
• LH of RH — A subtree of a tree that is right high has become left high.

I went through the example of balancing RH of RH tree as below. As can be seen below it involves left rotating root of RH tree (not subtree) to replace left node of the root of RH subtree:

Now I am looking at the example in Schaum's, which inserts W in the AVL tree already containing M,E,D,G,T,P,V,U,Z as follows:

I dont understand if the rotateRight() in above is necessary. I guess above is also an example of RH of RH tree, if you apply Forouzan's analogy. In this case nodes T and V are Right High. So as per explanation in Forouzan's book, we can apply single left rotation to node T to make it left child of V and balance this AVL tree as follows:

                 M                /   \               /     \              E       V              / \     /  \            D   G   T    Z                   / \  /                   P   U W 

I dont find the need of first rightRotate() to make W right child of Z. Is it necessary? Or Schaum's example is wrong?

Asked By : Mahesha999

Answered By : Hendrik Jan

I think you are right for this example. But the title of your question is misleading. Let me explain.

After insertion the tree can be rebalanced with one (single or double) rotation at the lowest node $x$ where unbalance occurs. There are four cases, as you mention. If the key has been inserted in a left-left or a right-right subtree we do a single rotation to the right or to the left, and if it was the left-right or right-left subtree we do a double rotation at $x$ (in suitable direction). In general a single rotation will not work.

Back to the example you show us. The lowest point of unbalance is $T$. From $T$ the new key $W$ was added right-right. That means a single rotation left at $T$. As far as I see the result of this is exactly what you have drawn in your diagram.

To close, your title is misleading, as we do not need double rotation here, but we need one in other situations.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55717

3.2K people like this

 Download Related Notes/Documents