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?