Double Rotation: Exercise VII

  • Trace Double Left-Right Rotation.

Consider the following BST:

Exercise Remove the value $13$ 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 removal:

Notice the violation of balance property occurs in the parent of the node which was removed. From the perspective of the parent node, the problem is caused in left child's right subtree. (the highlighted nodes) This is the pattern which requires (double) left-right rotation to rebalance.

So we perform a left rotation to bring $10$ above $9$ (to bring the median value on a level between the low and high values):

And then a right rotation to bring $10$ above $12$ (to bring the median value on a level above the low and high values):