[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 15 gives us the unbalanced tree
[b, 8]
/ \
/ \
[b, 4] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [b, 1b] [b, 14] py
/ \ / \ / \ / \
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11] v[b, 13] y
The y node is an external node.
Since the y node is a right 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 Rb0. The following tree results when an Rb0 color change is done.
[b, 8]
/ \
/ \
[b, 4] [b, 12] py
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [b, 10] v [b, 14] y
/ \ / \ / \ /
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11] [r, 13]
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
[b, 8] py
/ \
/ \
[b, 4] v [b, 12] y
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [r, 10] [b, 14]
/ \ / \ / \ /
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11] [r, 13]
The y node is now one level higher in the tree.
The imbalance is once again classified as an Rb0 imbalance and another color
change is done. The new tree is
[b, 8] y
/ \
/ \
[r, 4] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [r, 10] [b, 14]
/ \ / \ / \ /
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11] [r, 13]
Since the y node is the root, we are done.
14 is removed, we get the tree
[b, 8]
/ \
/ \
[r, 4] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [r, 10] [r, 13] y
/ \ / \ / \
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11]
Since y is red node,
the tree is balanced by changing the color of y
to black. The balanced tree is
[b, 8]
/ \
/ \
[r, 4] [b, 12]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [r, 10] [b, 13]
/ \ / \ / \
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11]
Next
when 13 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
[r, 4] [b, 12] py
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [r, 10] v y
/ \ / \ / \
[b, 1] [b, 3] [b, 5] [b, 7] [b, 9] [b, 11]
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]
/ \
/ \
[r, 4] [b, 10]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [b, 9] [b, 12]
/ \ / \ /
[b, 1] [b, 3] [b, 5] [b, 7] [r, 11]
When 12 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
[r, 4] [b, 10]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [b, 9] [r, 11] y
/ \ / \
[b, 1] [b, 3] [b, 5] [b, 7]
Since y is a red node, we change its color to
red to get the balanced tree shown below.
[b, 8]
/ \
/ \
[r, 4] [b, 10]
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [b, 9] [b, 11]
/ \ / \
[b, 1] [b, 3] [b, 5] [b, 7]
When 11 is removed, we get the unbalanced tree
[b, 8]
/ \
/ \
[r, 4] [b, 10] py
/ \ / \
/ \ / \
/ \ / \
[b, 2] [b, 6] [b, 9] v y
/ \ / \
[b, 1] [b, 3] [b, 5] [b, 7]
An Rb0 color change is done to get
py [b, 8]
/ \
/ \
[r, 4] v [b, 10] y
/ \ /
/ \ /
/ \ /
[b, 2] [b, 6] [r, 9]
/ \ / \
[b, 1] [b, 3] [b, 5] [b, 7]
The Rr0 imbalance is handled by performing an Rr0 rotation. The resulting
balanced tree is shown below.
[b, 4]
/ \
/ \
[b, 2] [b, 8]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [r, 6] [b, 10]
/ \ /
[b, 5] [b, 7] [r, 9]
When 10 is removed, we get the unbalanced tree
[b, 4]
/ \
/ \
[b, 2] [b, 8]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [r, 6] [r, 9] y
/ \
[b, 5] [b, 7]
Since y is a red node, we rebalance the
tree by chaing the color of y to black.
The result is
[b, 4]
/ \
/ \
[b, 2] [b, 8]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [r, 6] [b, 9]
/ \
[b, 5] [b, 7]
When 9 is removed, we get the unbalanced tree
[b, 4]
/ \
/ \
[b, 2] [b, 8] py
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [r, 6] v y
/ \
[b, 5] [b, 7]
The imbalance type is Rr0 and an Rr0 rotation (equivalent to an LL rotation)
is performed to rebalance the tree. The result is
[b, 4]
/ \
/ \
[b, 2] [b, 6]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [b, 5] [b, 8]
/
[r, 7]
The removal of 8 leaves behind the unbalanced tree
[b, 4]
/ \
/ \
[b, 2] [b, 6]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [b, 5] [r, 7] y
Since y is a red node, we rebalance the tree
by making y a black node. The result is
[b, 4]
/ \
/ \
[b, 2] [b, 6]
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [b, 5] [b, 7]
The removal of 7 leaves behind the unbalanced tree
[b, 4]
/ \
/ \
[b, 2] [b, 6] py
/ \ / \
/ \ / \
/ \ / \
[b, 1] [b, 3] [b, 5] v y
The imbalance type is Rb0. The ensuing Rb0 color change gives use the
tree
[b, 4] py
/ \
/ \
[b, 2] v [b, 6] y
/ \ /
[b, 1] [b, 3] [r, 5]
The imbalance type is again Rb0 and an Rb0 color change is done.
The resulting tree is
[b, 4] y
/ \
/ \
[r, 2] [b, 6]
/ \ /
[b, 1] [b, 3] [r, 5]
Since y is the root, we are done.
6 leaves behind the unbalanced tree
[b, 4]
/ \
/ \
[r, 2] [r, 5] y
/ \
[b, 1] [b, 3]
Since y is a red node, we balance the
tree by making y a black node as is
done below.
[b, 4]
/ \
/ \
[r, 2] [b, 5]
/ \
[b, 1] [b, 3]
The removal of 5 gives us the unbalanced tree
[b, 4] py
/ \
/ \
[r, 2] v y
/ \
[b, 1] [b, 3]
The imbalance type is Rr0 and an Rr0 rotation
is performed to rebalance the tree. The result is
[b, 2]
/ \
/ \
[b, 1] [b, 4]
/
[r, 3]
The removal of 4 gives us the unbalanced tree
[b, 2]
/ \
[b, 1] [r, 3] y
Since y is red, we balance the tree
by making y black. The balanced tree
is shown below.
[b, 2]
/ \
[b, 1] [b, 3]
The removal of 3 gives us the unbalanced tree
[b, 2] py
/ \
[b, 1] v y
The imbalance type is Rb0 and a color change is done to get the
tree
[b, 2] y
/
[r, 1]
Since y is the root, we are done.
2 gives us the unbalanced tree
[r, 1] y
Since y is red, we make it black. The balanced tree
is
[b, 1]
The removal of 1 leaves behind an empty tree.