[balance factor, key].
The first two inserts result in the following
balanced trees.
[0, 15] [1, 15]
/
[0, 14]
Immediately after the insertion of 13, we
have the unbalanced tree
[2, 15] A node
/
[1, 14] B
/
[0, 13] C
The nearest ancestor of the newly inserted node whose balance factor
is +2 or -2 is
[2, 15]. So this node is the A
node.
The imbalance is an LL imbalance because the new node was inserted into
the left subtree of the left subtree of A.
The tree following an LL rotation is shown below.
[0, 14]
/ \
[0, 13] [0, 15]
When 12 is inserted we get the following balanced tree:
[1, 14]
/ \
[1, 13] [0, 15]
/
[0, 12]
The insertion of 11 gives us the unbalanced tree
[2, 14]
/ \
A [2, 13] [0, 15]
/
B [1, 12]
/
C [0, 11]
The imbalance type is LL, and following an LL rotation we get the balanced tree
[1, 14]
/ \
[0, 12] [0, 15]
/ \
[0, 11] [0, 13]
Following the insertion of 10 we have the unbalanced tree
[2, 14] A node
/ \
B [1, 12] [0, 15]
/ \
C [1, 11] [0, 13]
/
[0, 10]
The imbalance type is LL, and following an LL rotation we get the balanced tree
[0, 12]
/ \
[1, 11] [0, 14]
/ / \
[0, 10] [0, 13] [0, 15]
When 9 is inserted we get the unbalanced tree
[1, 12]
/ \
A [2, 11] [0, 14]
/ / \
B [1, 10] [0, 13] [0, 15]
/
C [0, 9]
The imbalance type is LL, and following an LL rotation we get the balanced tree
[0, 12]
/ \
/ \
/ \
[0, 10] [0, 14]
/ \ / \
[0, 9] [0, 11] [0, 13] [0, 15]
The insertion of 8 gives us the balanced tree
[1, 12]
/ \
/ \
/ \
[1, 10] [0, 14]
/ \ / \
[1, 9] [0, 11] [0, 13] [0, 15]
/
[0, 8]
The insertion of 7 gives us the unbalanced tree
[2, 12]
/ \
/ \
/ \
[2, 10] [0, 14]
/ \ / \
A [2, 9] [0, 11] [0, 13] [0, 15]
/
B [0, 8]
/
C [0, 7]
The imbalance type is LL, and following an LL rotation we get
[1, 12]
/ \
/ \
/ \
[1, 10] [0, 14]
/ \ / \
[0, 8] [0, 11] [0, 13] [0, 15]
/ \
[0, 7] [0, 9]
The insertion of 6 gives us the unbalanced tree
[2, 12]
/ \
/ \
/ \
A [2, 10] [0, 14]
/ \ / \
B [1, 8] [0, 11] [0, 13] [0, 15]
/ \
C [1, 7] [0, 9]
/
[0, 6]
The imbalance type is LL, and following an LL rotation we get
[1, 12]
/ \
/ \
/ \
[0, 8] [0, 14]
/ \ / \
[1, 7] [0, 10] [0, 13] [0, 15]
/ / \
[0, 6] [0, 9] [0, 11]
The insertion of 5 gives us the unbalanced tree
[2, 12]
/ \
/ \
/ \
[1, 8] [0, 14]
/ \ / \
A [2, 7] [0, 10] [0, 13] [0, 15]
/ / \
B [1, 6] [0, 9] [0, 11]
/
C [0,5]
The imbalance type is LL, and following an LL rotation we get
[1, 12]
/ \
/ \
/ \
[0, 8] [0, 14]
/ \ / \
[0, 6] [0, 10] [0, 13] [0, 15]
/ \ / \
[0, 5] [0, 7] [0, 9] [0, 11]
The insertion of 4 gives us the unbalanced tree
A [2, 12]
/ \
/ \
/ \
B [1, 8] [0, 14]
/ \ / \
C [1, 6] [0, 10] [0, 13] [0, 15]
/ \ / \
[1, 5] [0, 7] [0, 9] [0, 11]
/
[0, 4]
The imbalance type is LL, and following an LL rotation we get
[0, 8]
/ \
/ \
[1, 6] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[1, 5] [0, 7] [0, 10] [0, 14]
/ / \ / \
[0, 4] [0, 9] [0, 11] [0, 13] [0, 15]
The insertion of 3 gives us the unbalanced tree
[1, 8]
/ \
/ \
[2, 6] [0, 12]
/ \ / \
/ \ / \
/ \ / \
A [2, 5] [0, 7] [0, 10] [0, 14]
/ / \ / \
B [1, 4] [0, 9] [0, 11] [0, 13] [0, 15]
/
C [0, 3]
The imbalance type is LL, and following an LL rotation we get
[0, 8]
/ \
/ \
[1, 6] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[0, 4] [0, 7] [0, 10] [0, 14]
/ \ / \ / \
[0, 3] [0, 5] [0, 9] [0, 11] [0, 13] [0, 15]
The insertion of 2 gives us the unbalanced tree
[1, 8]
/ \
/ \
A [2, 6] [0, 12]
/ \ / \
/ \ / \
/ \ / \
B [1, 4] [0, 7] [0, 10] [0, 14]
/ \ / \ / \
C [1, 3] [0, 5] [0, 9] [0, 11] [0, 13] [0, 15]
/
[0, 2]
The imbalance type is LL, and following an LL rotation we get
[0, 8]
/ \
/ \
[0, 4] [0, 12]
/ \ / \
/ \ / \
/ \ / \
[1, 3] [0, 6] [0, 10] [0, 14]
/ / \ / \ / \
[0, 2] [0, 5] [0, 7] [0, 9] [0, 11] [0, 13] [0, 15]
The insertion of 1 gives us the unbalanced tree
[1, 8]
/ \
/ \
[1, 4] [0, 12]
/ \ / \
/ \ / \
/ \ / \
A [2, 3] [0, 6] [0, 10] [0, 14]
/ / \ / \ / \
B [1, 2] [0, 5] [0, 7] [0, 9] [0, 11] [0, 13] [0, 15]
/
C [0, 1]
The imbalance type is LL, and following an LL rotation we get
[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]
As you can see, we get minimum height binary trees!