4
$\begingroup$

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:

enter image description here

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:

enter image description here

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Wow, that's a complicated and yet misleading presentation... have you checked out other sources? $\endgroup$
    – Raphael
    Commented Apr 9, 2016 at 9:57

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ok so the Schaum's Outline is wrong in this case and they have unnecessarily done that rotateRight()...Thanks for confirming, feels bad when books misdirects us... $\endgroup$
    – Mahesha999
    Commented Apr 9, 2016 at 12:00
2
$\begingroup$

Looking at small examples can be misleading.

For a general explanation (which can be found in many textbooks), add the subtrees of P, U and W as well as the missing one of Z. Assign fitting heights symbolically, i.e. $h \pm \{0,1,2\}$. Observe how your proposed rotation fails.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.