Page 144 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

Right-Left Rotiation (RL) or “Double right” Notes

A double right rotation, or right-left rotation, or simply RL, is a rotation that must be performed
when attempting to balance a tree which has a left subtree, that is right heavy. This is a mirror
operation of what was illustrated in the section on Left-Right Rotations, or double left rotations.
Let’s look at an example of a situation where we need to perform a Right-Left rotation.
c
/
a

\
b
In this situation, we have a tree that is unbalanced. The left subtree has a height of 2, and the right
subtree has a height of 0. This makes the balance factor of our root node, c, equal to -2. What do
we do? Some kind of right rotation is clearly necessary, but a single right rotation will not solve
our problem. Let’s try it:

a
\
c
/
b

Looks like that didn’t work. Now we have a tree that has a balance of 2. It would appear that we
did not accomplish much. That is true. What do we do? Well, let’s go back to the original tree,
before we did our pointless right rotation:
c

/
a
\
b
The reason our right rotation did not work, is because the left subtree, or ‘a’, has a positive
balance factor, and is thus right heavy. Performing a right rotation on a tree that has a left subtree
that is right heavy will result in the problem we just witnessed. What do we do? The answer is to
make our left subtree left-heavy. We do this by performing a left rotation our left subtree. Doing
so leaves us with this situation:
c
/
b
/
a

LOVELY PROFESSIONAL UNIVERSITY 139