Double Rotation: Exercise VI
Consider the following BST:
Exercise Insert the value $23$ 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 newly inserted node. From the perspective of the grandparent node, the problem is caused in right child's left subtree (the highlighted nodes). This is the pattern which requires (double) right-left rotation to rebalance.
So we perform a right rotation to bring $22$ above $25$ (to bring the median value on a level between the low and high values):
And then a left rotation to bring $22$ above $20$ (to bring the median value on a level above the low and high values):