Double Rotation: Exercise VI

  • Trace Double Right-Left Rotation.

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):