[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 6 gives us the balanced tree
[0, 8]
/ \
/ \
[0, 4] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 2] q [-1, 5] [0, 10] [0, 14]
/ \ \ / \ / \
[0, 1] [0, 3] [0, 7] [0, 9] [0, 11] [0, 13] [0, 15]
The q node is [-1, 15],
and since its balance factor is -1 no
further work is to be done.
7 is removed, we get the tree
[0, 8]
/ \
/ \
[1, 4] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 2] q [0, 5] [0, 10] [0, 14]
/ \ / \ / \
[0, 1] [0, 3] [0, 9] [0, 11] [0, 13] [0, 15]
When 5 is removed, we get the unbalanced tree
[0, 8]
/ \
/ \
q, A [2, 4] [0, 12]
/ / \
/ / \
/ / \
B [0, 2] [0, 10] [0, 14]
/ \ / \ / \
[0, 1] [0, 3] [0, 9] [0, 11] [0, 13] [0, 15]
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 (equivalent
to an LL rotation)
balances the tree. The result is
[0, 8]
/ \
/ \
[-1, 2] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 1] [1, 4] [0, 10] [0, 14]
/ / \ / \
[0, 3] [0, 9] [0, 11] [0, 13] [0, 15]
When 10 is removed, we get the balanced tree
[0, 8]
/ \
/ \
[-1, 2] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 1] [1, 4] [1, 11] q [0, 14]
/ / / \
[0, 3] [0, 9] [0, 13] [0, 15]
When 9 is removed, we get the balanced tree
[0, 8]
/ \
/ \
[-1, 2] [-1, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 1] [1, 4] [0, 11] q [0, 14]
/ / \
[0, 3] [0, 13] [0, 15]
When 11 is removed, we get the unbalanced tree
[0, 8]
/ \
/ \
[-1, 2] [-2, 12] q, A
/ \ \
/ \ \
/ \ \
[0, 1] [1, 4] [0, 14] B
/ / \
[0, 3] [0, 13] [0, 15]
The imbalance type is L0 and an L0 rotation
is performed to rebalance the tree. The result is
[0, 8]
/ \
/ \
[-1, 2] [1, 14]
/ \ / \
/ \ / \
/ \ / \
[0, 1] [1, 4] [-1, 12] [0, 15]
/ \
[0, 3] [0, 13]
When 15 is removed, we get the unbalanced tree
[0, 8]
/ \
/ \
[-1, 2] [2, 14] q, A
/ \ /
/ \ /
/ \ /
[0, 1] [1, 4] [-1, 12] B
/ \
[0, 3] [0, 13] C
The imbalance type is R-1 and an R-1 rotation (equivalent to an LR rotation)
is performed. Following the rotation, we move up the
tree and adjust the balance factor of [0, 8].
The result is
[1, 8]
/ \
/ \
[-1, 2] [0, 13]
/ \ / \
/ \ / \
/ \ / \
[0, 1] [1, 4] [0, 12] [0, 14]
/
[0, 3]
The removal of 12 leaves behind the balanced tree
[1, 8]
/ \
/ \
[-1, 2] [-1, 13] q
/ \ \
/ \ \
/ \ \
[0, 1] [1, 4] [0, 14]
/
[0, 3]
The removal of 13 leaves behind the unbalanced tree
[2, 8] A
/ \
/ \
[-1, 2] B [0, 14] q
/ \
/ \
/ \
[0, 1] [1, 4] C
/
[0, 3]
The imbalance type is R-1. The tree after the R-1 rotation is performed is
[0, 4]
/ \
/ \
[0, 2] [-1, 8]
/ \ \
[0, 1] [0, 3] [0, 14]
The removal of 1 gives us the balanced tree
[0, 4]
/ \
/ \
q [-1, 2] [-1, 8]
\ \
[0, 3] [0, 14]
The removal of 2 gives us the balanced tree
[-1, 4]
/ \
/ \
q [0, 3] [-1, 8]
\
[0, 14]
The removal of 3 gives us the unbalanced tree
[-2, 4] q, A
\
\
[-1, 8] B
\
[0, 14]
The imbalance type is L-1 and an L-1 rotation (equivalent to an RR rotation)
is performed. The result is the balanced tree
[0, 8]
/ \
[0, 4] [0, 14]