Right Rotation: Exercise III
- Trace Single Right Rotation.
Consider the following BST:
Exercise Insert the value $3$ and apply a structural rotation to balance the BST if needed.
Solution
Let's observe the original BST is balanced:
Here is the BST after insertion:
Notice the violation of balance property occurs in the great-grandparent of the inserted node. From the perspective of the great-grandparent node, the problem is caused in left child's left subtree. This is the pattern that requires a (single) right rotation. However, this case is a bit tricky:
When you bring $7$ to be the parent of $14$, the latter needs to go to the right of $7$. However, $11$ is already to the right of $7$. So we need to attach $11$ to the left of $14$ (where $7$ used to be).