A tree rotation can be an imtimidating concept at first. You end up in a situation where you’re juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast. I find it helps to block out what’s going on with any of the subtrees which are attached to the nodes you’re fumbling with, but that can be hard.
Left Rotation (LL) or Single Left rotation
Imagine we have this situation:
a
\\
b
\\
c
```To fix this, we must perform a left rotation, rooted at A. This is done in the following steps:
b becomes the new root.
a takes ownership of b's left child as its right child, or in this case, null.
b takes ownership of a as its left child.
temp = p->right;
p->right = temp->left;
temp->left = p;
p = temp;
The tree now looks like this:
Figure 1-2
b
/ \
a c
A right rotation is a mirror of the left rotation operation described above. Imagine we have this situation:
Figure 1-3
c
/
b
/
a
b becomes the new root.
c takes ownership of b's right child, as its left child. In this case, that value is null.
b takes ownership of c, as it's right child.
temp = p->left;
p->left = temp->right;
temp->right = p;
p = temp;
The resulting tree:
Figure 1-4
b
/ \
a c
Sometimes a single left rotation is not sufficient to balance an unbalanced tree. Take this situation:
Figure 1-5
a
\
c
Figure 1-6
a
\
c
/
b
Our initial reaction here is to do a single left rotation. Let's try that.
Figure 1-7
c
/
a
\
b
Before:
Figure 1-8
c
/
b
Figure 1-9
b
\
c
Figure 1-10
a
\
b
\
c
Figure 1-11
b
/ \
a c
**
Right-Left Rotiation (RL) or "Double right"**
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.
Figure 1-12
c
/
a
\
b
Figure 1-13
a
\
c
/
b
Figure 1-14
c
/
a
\
b
Figure 1-15
c
/
b
/
a
Figure 1-16
b
/ \
a c