[color, key],
where color is the node color.
The initial tree is
[b, 8]
/ \
/ \
[b, 4] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [b, 10] [b, 14]
/ \ / \ / \ / \
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11] [b, 13] [b, 15]
Removal of 6 gives us the unbalanced tree
[b, 8]
/ \
/ \
[b, 4] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 2] py [b, 5] [b, 10] [b, 14]
/ \ / \ / \ / \
[b, 1] [b, 3] y v[b, 7] [b, 9] [b, 11] [b, 13] [b, 15]
The y node is an external node.
Since the y node is a left child
whose sibling v is a black node that has no
red children (both children of v are
external nodes, and external nodes are black), the imbalance type
is Lb0. The following tree results when an Lb0 color change is done.
[b, 8]
/ \
/ \
py [b, 4] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 2] v y [b, 5] [b, 10] [b, 14]
/ \ \ / \ / \
[b, 1] [b, 3] [r, 7] [b, 9] [b, 11] [b, 13] [b, 15]
The y node is now one level higher in the tree.
The imbalance is again classified as an Rb0 imbalance and another color
change is done. The new tree is
py [b, 8]
/ \
/ \
y [b, 4] v [b, 12]
/ \ / \
/ \ / \
/ \ / \
[r, 2] [b, 5] [b, 10] [b, 14]
/ \ \ / \ / \
[b, 1] [b, 3] [r, 7] [b, 9] [b, 11] [b, 13] [b, 15]
The y node is now one level higher in the tree.
The imbalance is classified as an Lb0 imbalance and another color
change is done. The new tree is
y [b, 8]
/ \
/ \
[b, 4] [r, 12]
/ \ / \
/ \ / \
/ \ / \
[r, 2] [b, 5] [b, 10] [b, 14]
/ \ \ / \ / \
[b, 1] [b, 3] [r, 7] [b, 9] [b, 11] [b, 13] [b, 15]
Since the y node is the root, we are done.
7 is removed, we get the tree
y [b, 8]
/ \
/ \
[b, 4] [r, 12]
/ \ / \
/ \ / \
/ \ / \
[r, 2] [b, 5] [b, 10] [b, 14]
/ \ / \ / \
[b, 1] [b, 3] [b, 9] [b, 11] [b, 13] [b, 15]
Since the deleted node node was red, the tree is balanced. Next
when 5 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
py [b, 4] [r, 12]
/ \ / \
/ \ / \
/ \ / \
[r, 2] v y [b, 10] [b, 14]
/ \ / \ / \
[b, 1] [b, 3] [b, 9] [b, 11] [b, 13] [b, 15]
The type of the imbalance is Rr0 because the deletion was from the
right subtree of py and the sibling
v is a red node that has no red
children. Performing an Rr0 rotation
balances the tree. The result is
[b, 8]
/ \
/ \
[b, 2] [r, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] [b, 10] [b, 14]
/ / \ / \
[r, 3] [b, 9] [b, 11] [b, 13] [b, 15]
When 10 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
[b, 2] [r, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] py [b, 9] [b, 14]
/ / \ / \
[r, 3] y v[b, 11] [b, 13] [b, 15]
The imbalance type is Lb0. After an Lb0 color change we get the tree
[b, 8]
/ \
/ \
[b, 2] py [r, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] y [b, 9] v [b, 14]
/ \ / \
[r, 3] [r, 11] [b, 13] [b, 15]
The imbalance type is again Lb0. Following an Lb0 color change we get the
tree
[b, 8]
/ \
/ \
[b, 2] y [r, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] [b, 9] [r, 14]
/ \ / \
[r, 3] [r, 11] [b, 13] [b, 15]
Since y is a red node, its color is changed
to black and the tree is balanced.
The balanced tree is
[b, 8]
/ \
/ \
[b, 2] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] [b, 9] [r, 14]
/ \ / \
[r, 3] [r, 11] [b, 13] [b, 15]
When 9 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
[b, 2] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] y [r, 11] [r, 14]
/ / \
[r, 3] [b, 13] [b, 15]
The tree is balanced by making y a black node.
The balanced tree is shown below.
[b, 8]
/ \
/ \
[b, 2] py [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] y v [r, 14]
/ / \
[r, 3] [b, 13] [b, 15]
An Lr0 rotation is done to get the balanced tree shown below.
[b, 8]
/ \
/ \
[b, 2] [b, 14]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] [b, 12] [b, 15]
/ \
[r, 3] [r, 13]
When 15 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
[b, 2] [b, 14] py
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] [b, 12] v y
/ \
[r, 3] [r, 13] w
The imbalance type is Rb1(ii). The balanced tree following an Rb1(ii) rotation
rotation is shown below.
[b, 8]
/ \
/ \
[b, 2] [b, 13]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] [b, 12] [b, 14]
/
[r, 3]
When 12 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
[b, 2] [b, 13] py
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 4] y v [b, 14]
/
[r, 3]
The imbalance type is Lb0 and an Lb0 color change
is performed to get the tree.
[b, 8] py
/ \
/ \
[b, 2] v [b, 13] y
/ \ \
/ \ \
/ \ \
[b, 1] [b, 4] [r, 14]
/
[r, 3]
The imbalance type is now Rb0 and another clor change is done to get the tree
[b, 8] y
/ \
/ \
[r, 2] [b, 13]
/ \ \
/ \ \
/ \ \
[b, 1] [b, 4] [r, 14]
/
[r, 3]
Since y is the root, the tree is balanced.
13 leaves behind the unbalanced tree
[b, 8]
/ \
/ \
[r, 2] [r, 14] y
/ \
/ \
/ \
[b, 1] [b, 4]
/
[r, 3]
Since y is a red node, we rebalance the tree
by making y a black node. The result is
[b, 8]
/ \
/ \
[r, 2] [b, 14]
/ \
/ \
/ \
[b, 1] [b, 4]
/
[r, 3]
The removal of 2 leaves behind the unbalanced tree
[b, 8]
/ \
/ \
py [r, 1] [b, 14]
/ \
/ \
/ \
y v [b, 4]
/
w [r, 3]
The imbalance type is Lb1(ii). The ensuing Lb1(ii) rotation gives use the
balanced tree
[b, 8]
/ \
/ \
[r, 3] [b, 14]
/ \
/ \
/ \
[b, 1] [b, 4]