Question 12.2.4: A leaf is added to or deleted from a balanced tree. Prove th......

We prove the more general statement:
Lemma. If a subtree Y of a balanced tree X is replaced by a balanced tree Z, and the heights of Y and Z differ by 1, then the resulting tree can be made balanced by several rotations. The number of rotations does not exceed the height where the change occurs (that is, where the root of Y and Z is located).
The addition/deletion of a leaf is a special case of the transformation mentioned in the lemma, therefore it is enough to prove this lemma.
Proof of the lemma. We use induction over the height where the change is made. If the change is made at the root, the entire tree is replaced; in this case, the lemma is evident because the tree Z is balanced. Assume that the replaced tree Y is, say, the left subtree of some vertex x. Two cases are possible:

1. After replacement, the balance condition at the vertex x is still valid. (How-ever, the balance condition at the ancestors of x may be violated because the height of the subtree rooted at x may change.) In this case, we apply the induction hypothesis assuming that the replacement was done at the lower level and the whole tree rooted at x was replaced.

2. The balance condition at x is no longer valid. In this case, the height difference is 2 (it cannot be larger because the heights of Y and Z differ by at most 1). Here two subcases are possible:

(a) The right subtree ofx (the one that was not replaced) is higher. Assume that the height of the left subtree of x (i.e., Z) is k; then the height of the right subtree is k + 2. The height of the old left subtree of X (i.e., Y) was k + 1. The subtree of the initial tree rooted at x has height k + 3 and its height does not change after replacement.
By the preceding problem, a rotation can transform the subtree rooted at x into a balanced subtree of height k + 2 or k + 3. While doing this, the height of the subtree rooted at x (compared with its height before the transformation) did not change or was decreased by 1. Therefore, we apply the induction assumption.
(b) The left subtree of x is higher. Let the height of the left subtree (i.e., Z) be k + 2; the right subtree has height k. The old left subtree of x (i.e., Y) was of height k + 1. The subtree rooted at x (in the initial tree) has height k + 2; after the replacement it has height k + 3. After a suitable rotation (see the preceding problem), the subtree rooted at x becomes balanced and its height is k + 2 or k + 3; therefore, the change in height (compared with the height of the subtree of X rooted at x) does not exceed 1 and the induction assumption applies.