Question 12.2.3: Suppose a tree is balanced everywhere except at the root whe......
Suppose a tree is balanced everywhere except at the root where the difference of heights between the left and right subtrees equals 2 (that is, the left and right subtrees are balanced and their heights differs by 2). Prove that this tree may be transformed into a balanced tree using one of the four transformations mentioned above and that the height remains the same or decreases by 1 after the transformation.
Assume, for example, that the left subtree has smaller height, which we denote by k. Then the height of the right subtree is k + 2. Denote the root of the tree by a. Let b be its right son (it does exist). Consider the left and right subtrees of the vertex b. One of them has height k + 1, the other has height k or k +1. (Its height cannot be smaller than k because the right subtree of the root is balanced.) If the height of the left subtree of b is k +1, and the height of the right subtree of b is k, a big right rotation is needed; in all other cases, a small right rotation suffices. Here are the three possible cases:
