Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 23
This key sequence represents the worst case for the unbalanced binary search
trees of Chapter 14 because this sequence results
in trees whose height equals the number of elements.
Let's see how red-black trees handle this insert sequence.
We use the node format [color, key],
where color is the node color.
The first two inserts result in the following
balanced trees.
[b, 15] [b, 15]
/
[r, 14]
Immediately after the insertion of 13, we
have the unbalanced tree
[b, 15] gu
/
[r, 14] pu
/
[r, 13] u
The imbalance is an LLb imbalance because both u and
pu are left children and the other child of
gu is an external node.
The tree following an LLb rotation is shown below.
[b, 14]
/ \
[r, 13] [r, 15]
When 12 is inserted we get the following unbalanced tree:
gu [b, 14]
/ \
pu [r, 13] [r, 15]
/
u [r, 12]
The imbalance is an LLr imbalance because both u and
pu are left children and the other child of
gu is a red node.
The tree following an LLr color flip is shown below (note that the
color of the root remains black).
gu [b, 14]
/ \
pu [b, 13] [b, 15]
/
u [r, 12]
The insertion of 11 gives us the unbalanced tree
[b, 14]
/ \
gu [b, 13] [b, 15]
/
pu [r, 12]
/
u [r, 11]
The imbalance type is LLb, and following an LLb rotation we get the balanced tree
[b, 14]
/ \
[b, 12] [b, 15]
/ \
[r, 11] [r, 13]
Following the insertion of 10 we have the unbalanced tree
[b, 14]
/ \
gu [b, 12] [b, 15]
/ \
pu [r, 11] [r, 13]
/
u [r, 10]
The imbalance type is LLr, and following an LLr color flip we get the balanced tree
[b, 14]
/ \
gu [r, 12] [b, 15]
/ \
pu [b, 11] [b, 13]
/
u [r, 10]
When 9 is inserted we get the unbalanced tree
[b, 14]
/ \
[r, 12] [b, 15]
/ \
gu [b, 11] [b, 13]
/
pu [r, 10]
/
u [r, 9]
The imbalance type is LLb, and following an LLb rotation we get the balanced tree
[b, 14]
/ \
[r, 12] [b, 15]
/ \
[b, 10] [b, 13]
/ \
[r, 9] [r, 11]
The insertion of 8 gives us the unbalanced tree
[b, 14]
/ \
[r, 12] [b, 15]
/ \
gu [b, 10] [b, 13]
/ \
pu [r, 9] [r, 11]
/
u [r, 8]
The imbalance type is LLr, and following an LLr color flip we get the tree
gu [b, 14]
/ \
pu [r, 12] [b, 15]
/ \
u [r, 10] [b, 13]
/ \
[b, 9] [b, 11]
/
[r, 8]
An imbalance of type LLb remains and an LLb rotation is done to get
the balanced tree shown below. Once again, the color of the root is not
chnaged to red (as dictated by Figure 15.11(b)) because the
color of the root is always black.
[b, 12]
/ \
/ \
/ \
[r, 10] [r, 14]
/ \ / \
[b, 9] [b, 11] [b, 13] [b, 15]
/
[r, 8]
The insertion of 7 gives us the unbalanced tree
[b, 12]
/ \
/ \
/ \
[r, 10] [r, 14]
/ \ / \
gu [b, 9] [b, 11] [b, 13] [b, 15]
/
pu [r, 8]
/
u [r, 7]
The imbalance type is LLb, and following an LLb rotation we get
the balanced tree
[b, 12]
/ \
/ \
/ \
[r, 10] [r, 14]
/ \ / \
[b, 8] [b, 11] [b, 13] [b, 15]
/ \
[r, 7] [r, 9]
The insertion of 6 gives us the unbalanced tree
[b, 12]
/ \
/ \
/ \
[r, 10] [r, 14]
/ \ / \
gu [b, 8] [b, 11] [b, 13] [b, 15]
/ \
pu [r, 7] [r, 9]
/
u [r, 6]
The imbalance type is LLr, and following an LLr color flip we get
gu [b, 12]
/ \
/ \
/ \
pu [r, 10] [r, 14]
/ \ / \
u [r, 8] [b, 11] [b, 13] [b, 15]
/ \
[b, 7] [b, 9]
/
[r, 6]
The imbalance type is again LLr and another color flip yields the
balanced tree
[b, 12]
/ \
/ \
/ \
[b, 10] [b, 14]
/ \ / \
[r, 8] [b, 11] [b, 13] [b, 15]
/ \
[b, 7] [b, 9]
/
[r, 6]
The insertion of 5 gives us the unbalanced tree
[b, 12]
/ \
/ \
/ \
[b, 10] [b, 14]
/ \ / \
[r, 8] [b, 11] [b, 13] [b, 15]
/ \
gu [b, 7] [b, 9]
/
pu [r, 6]
/
u [r, 5]
The imbalance type is LLb, and following an LLb rotation we get
the balanced tree
[b, 12]
/ \
/ \
/ \
[b, 10] [b, 14]
/ \ / \
[r, 8] [b, 11] [b, 13] [b, 15]
/ \
[b, 6] [b, 9]
/ \
[r, 5] [r, 7]
The insertion of 4 gives us the unbalanced tree
[b, 12]
/ \
/ \
/ \
[b, 10] [b, 14]
/ \ / \
[r, 8] [b, 11] [b, 13] [b, 15]
/ \
gu [b, 6] [b, 9]
/ \
pu [r, 5] [r, 7]
/
u [r, 4]
The imbalance type is LLr, and following an LLr color flip we get
[b, 12]
/ \
/ \
/ \
gu [b, 10] [b, 14]
/ \ / \
pu [r, 8] [b, 11] [b, 13] [b, 15]
/ \
u [r, 6] [b, 9]
/ \
[b, 5] [b, 7]
/
[r, 4]
An imbalance of type LLb remains, and an LLb rotation is done to
get the balanced tree
[b, 12]
/ \
/ \
/ \
[b, 8] [b, 14]
/ \ / \
[r, 6] [r, 10] [b, 13] [b, 15]
/ \ / \
[b, 5] [b, 7] [b, 9] [b, 11]
/
[r, 4]
When 3 is inserted we get the
following unbalanced tree.
[b, 12]
/ \
/ \
/ \
[b, 8] [b, 14]
/ \ / \
[r, 6] [r, 10] [b, 13] [b, 15]
/ \ / \
gu [b, 5] [b, 7] [b, 9] [b, 11]
/
pu [r, 4]
/
u [r, 3]
The imbalance type is LLb, and following an LLb rotation we get
[b, 12]
/ \
/ \
/ \
[b, 8] [b, 14]
/ \ / \
[r, 6] [r, 10] [b, 13] [b, 15]
/ \ / \
[b, 4] [b, 7] [b, 9] [b, 11]
/ \
[r, 3] [r, 5]
The insertion of 2 gives us the unbalanced tree
[b, 12]
/ \
/ \
/ \
[b, 8] [b, 14]
/ \ / \
[r, 6] [r, 10] [b, 13] [b, 15]
/ \ / \
gu [b, 4] [b, 7] [b, 9] [b, 11]
/ \
pu [r, 3] [r, 5]
/
u [r, 2]
The imbalance type is LLr, and following an LLr color flip we get
[b, 12]
/ \
/ \
/ \
gu [b, 8] [b, 14]
/ \ / \
pu [r, 6] [r, 10] [b, 13] [b, 15]
/ \ / \
u [r, 4] [b, 7] [b, 9] [b, 11]
/ \
[b, 3] [b, 5]
/
[r, 2]
An LLr imbalance remains and another color flip is done to get the
tree.
pu [b, 12]
/ \
/ \
/ \
u [r, 8] [b, 14]
/ \ / \
[b, 6] [b, 10] [b, 13] [b, 15]
/ \ / \
[r, 4] [b, 7] [b, 9] [b, 11]
/ \
[b, 3] [b, 5]
/
[r, 2]
The tree is now balanced and we proceed to insert
1. This gives us the unbalanced tree
[b, 12]
/ \
/ \
/ \
[r, 8] [b, 14]
/ \ / \
[b, 6] [b, 10] [b, 13] [b, 15]
/ \ / \
[r, 4] [b, 7] [b, 9] [b, 11]
/ \
gu [b, 3] [b, 5]
/
pu [r, 2]
/
u [r, 1]
The imbalance type is LLb, and following an LLb rotation we get
[b, 12]
/ \
/ \
/ \
[r, 8] [b, 14]
/ \ / \
[b, 6] [b, 10] [b, 13] [b, 15]
/ \ / \
[r, 4] [b, 7] [b, 9] [b, 11]
/ \
[b, 2] [b, 5]
/ \
[r, 1] [r, 3]