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
Search WWH ::




Custom Search