Page 143 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes /

b
Our initial reaction here is to do a single left rotation. Let’s try that.
c
/
a
\

b
Our left rotation has completed, and we’re stuck in the same situation. If we were to do a single
right rotation in this situation, we would be right back where we started. What’s causing this?
The answer is that this is a result of the right subtree having a negative balance. In other words,
because the right subtree was left heavy, our rotation was not sufficient. What can we do? The

answer is to perform a right rotation on the right subtree. Read that again. We will perform a
right rotation on the right subtree. We are not rotating on our current root. We are rotating on
our right child. Think of our right subtree, isolated from our main tree, and perform a right
rotation on it:
Before:

c
/
b
After:
b

\
c
After performing a rotation on our right subtree, we have prepared our root to be rotated left.
Here is our tree now:

a
\
b
\

c
Looks like we’re ready for a left rotation. Let’s do that:
b
/ \
a c

Voila. Problem solved.

138 LOVELY PROFESSIONAL UNIVERSITY