TAOCP 6.2.3 Exercise 1
In Case 2 the symmetric order of the keys is determined by the in-order sequence of the subtrees: all keys in the left subtree of $A$ precede $\text{KEY}(A)$, all keys in the left subtree of $B$ that...
Exercise 1. [01] [01] In Case 2 of (1), why isn’t it a good idea to restore the balance by simply interchanging the left subtrees of A and B?
Verified: yes
Solve time: 49s
In Case 2 the symmetric order of the keys is determined by the in-order sequence of the subtrees: all keys in the left subtree of $A$ precede $\text{KEY}(A)$, all keys in the left subtree of $B$ that are not in $A$’s right subtree lie between $\text{KEY}(A)$ and $\text{KEY}(B)$, and all keys in the right subtree of $B$ follow $\text{KEY}(B)$.
If one interchanges only the left subtrees of $A$ and $B$, then the subtree that originally belonged between $\text{KEY}(A)$ and $\text{KEY}(B)$ is placed entirely to the left of $A$, so elements that should lie in the middle interval are moved into the region of keys $< \text{KEY}(A)$. This violates the symmetric-order property required of a search tree, since the in-order traversal no longer yields the keys in increasing order.
The double rotation in Case 2 is designed so that the subtree rooted at $X$ becomes the new root of the local structure, with the other subtrees redistributed so that each remains within its correct key interval. A simple interchange of left subtrees cannot achieve this redistribution while preserving both the ordering constraints and the height relationships that determine balance. This completes the solution. ∎