Java Reference
In-Depth Information
FIGURE 27-2
(a) Adding 80 to the tree in Figure 27-1d does not change the
balance of the tree; (b) a subsequent addition of 90 makes the
tree unbalanced ; (c) a left rotation restores its balance
(a)
(b)
(c)
50
50
50
20
60
20
60
20
80
80
80
60
90
90
Balanced
Unbalanced
Balanced
N
is the first node that is unbalanced along the path between the inserted leaf and
N
. A right rotation
about node
C
restores the balance of the tree, as Figure 27-3c shows. After the rotation,
C
is above
N
, and the tree has the same height as it did before the addition of a node.
Since we had a binary search tree before the rotation (Figure 27-3b), the value in node
N
is
greater than the value in node
C
and all the values in
T
2
. Moreover, all values in
T
2
are greater
than the value in node
C
. These relationships are maintained after the rotation (Figure 27-3c),
since node
N
is a right child of node
C
, and
T
2
is a left subtree of node
N
. Finally, the subtrees
T
1
and
T
3
have their original parents in the new tree. Thus, the resulting tree is still a binary
search tree.
Figure 27-4 provides a specific instance of the right rotation depicted in Figure 27-3. Part
a
of the figure shows an imbalance at node
N
after 4 was added to the tree. A right rotation restores
the tree's balance, as Part
b
illustrates. To simplify the figure, we have labeled only the roots of
the subtrees
T
1
,
T
2
, and
T
3
. Here, node
N
was the root of the AVL tree, and node
C
became the
root. However if node
N
had a parent before the rotation, we would make node
C
a child of that
parent after the rotation.
FIGURE 27-3
Before and after an addition to an AVL subtree that requires
a right rotation to maintain its balance
(a) Before addition
(b) After addition
(c) After right rotation
N
C
N
N
C
C
h
h
h
+ 1
T
3
T
3
T
1
T
2
T
1
T
2
T
2
T
3
T
1