[balance factor, key].
The initial tree is
[0, 8]
/ \
/ \
[0, 4] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 2] [0, 6] [0, 10] [0, 14]
/ \ / \ / \ / \
[0, 1] [0, 3] [0, 5] [0, 7] [0, 9] [0, 11] [0, 13] [0, 15]
Removal of 15 gives us the balanced tree
[0, 8]
/ \
/ \
[0, 4] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 2] [0, 6] [0, 10] [1, 14] q
/ \ / \ / \ /
[0, 1] [0, 3] [0, 5] [0, 7] [0, 9] [0, 11] [0, 13]
The q node is [1, 14],
and since its balance factor is +1 no
further work is to be done.
14 is removed, we get the tree
[0, 8]
/ \
/ \
[0, 4] [1, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 2] [0, 6] [0, 10] [0, 13] q
/ \ / \ / \
[0, 1] [0, 3] [0, 5] [0, 7] [0, 9] [0, 11]
When 13 is removed, we get the unbalanced tree
[0, 8]
/ \
/ \
[0, 4] [2, 12] q, A
/ \ /
/ \ /
/ \ /
[0, 2] [0, 6] [0, 10] B
/ \ / \ / \
[0, 1] [0, 3] [0, 5] [0, 7] [0, 9] [0, 11]
The type of the imbalance is R0 because the deletion was from the
right subtree of the A node and because
bf(B) = 0. Performing an R0 rotation
balances the tree. The result is
[0, 8]
/ \
/ \
[0, 4] [-1, 10]
/ \ / \
/ \ / \
/ \ / \
[0, 2] [0, 6] [0, 9] [1, 12]
/ \ / \ /
[0, 1] [0, 3] [0, 5] [0, 7] [0, 11]
When 12 is removed, we get the balanced tree
[1, 8]
/ \
/ \
[0, 4] [0, 10]
/ \ / \
/ \ / \
/ \ / \
[0, 2] [0, 6] [0, 9] [0, 11]
/ \ / \
[0, 1] [0, 3] [0, 5] [0, 7]
When 11 is removed, we get the balanced tree
[1, 8]
/ \
/ \
[0, 4] [1, 10]
/ \ /
/ \ /
/ \ /
[0, 2] [0, 6] [0, 9]
/ \ / \
[0, 1] [0, 3] [0, 5] [0, 7]
When 10 is removed, we get the unbalanced tree
[2, 8] A
/ \
/ \
[0, 4] B [0, 9] q
/ \
/ \
/ \
[0, 2] [0, 6]
/ \ / \
[0, 1] [0, 3] [0, 5] [0, 7]
The imbalance type is R0 and an R0 rotation (equivalent to an LL rotation)
is performed to rebalance the tree. The result is
[-1, 4]
/ \
/ \
[0, 2] [1, 8]
/ \ / \
[0, 1] [0, 3] [0, 6] [0, 9]
/ \
[0, 5] [0, 7]
When 9 is removed, we get the unbalanced tree
[-1, 4]
/ \
/ \
[0, 2] [2, 8] q, A
/ \ /
[0, 1] [0, 3] [0, 6] B
/ \
[0, 5] [0, 7]
The imbalance type is R0 and an R0 rotation
is performed to rebalance the tree. The result is
[-1, 4]
/ \
/ \
[0, 2] [-1, 6]
/ \ / \
[0, 1] [0, 3] [0, 5] [1, 8]
/
[0, 7]
The removal of 8 leaves behind the balanced tree
[0, 4]
/ \
/ \
[0, 2] [0, 6]
/ \ / \
[0, 1] [0, 3] [0, 5] [0, 7] q
The removal of 7 leaves behind the balanced tree
[0, 4]
/ \
/ \
[0, 2] [1, 6] q
/ \ /
[0, 1] [0, 3] [0, 5]
The removal of 6 leaves behind the balanced tree
[1, 4]
/ \
/ \
[0, 2] [0, 5] q
/ \
[0, 1] [0, 3]
The removal of 5 gives us the unbalanced tree
[2, 4] q, A
/
/
[0, 2] B
/ \
[0, 1] [0, 3]
The imbalance type is R0 and an R0 rotation
is performed to rebalance the tree. The result is
[-1, 2]
/ \
[0, 1] [1, 4]
/
[0, 3]
The removal of 4 gives us the balanced tree
[0, 2]
/ \
[0, 1] [0, 3] q
The removal of 3 gives us the balanced tree
[1, 2] q
/
[0, 1]
The removal of 2 gives us the balanced tree
[0, 1]
The removal of 1 leaves behind an empty tree.