Double Rotation: Exercise VII

  • Trace Double Left-Right Rotation.

Consider the following BST:

Exercise Remove the value 1313 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 1010 above 99 (to bring the median value on a level between the low and high values):

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