Java Reference
In-Depth Information
Question 2
Why is the tree in Figure 27-5c a binary search tree?
Question 3
Using the notation of Figure 27-5, label nodes
N
and
C
, and subtrees
T
1
,
T
2
,
and
T
3
,
in Parts
b
and
c
of Figure 27-2.
Question 4
Just as Figure 27-4 gave an example of a right rotation, provide a specific
example of the left rotation illustrated in Figure 27-5.
Note:
An imbalance at node
N
of an AVL tree due to an addition to the tree can be cor-
rected by a single rotation if
•
The addition occurred in the left subtree of
N
's left child
C
(right rotation), or
•
The addition occurred in the right subtree of
N
's right child
C
(left rotation)
In both cases, we can imagine node
C
rotating above node
N
.
27.4
Right-left double rotations.
Now we add 70 to the AVL tree in Figure 27-2c. An imbalance occurs at
the tree's root, as Figure 27-6a shows. A right rotation about the node containing 60 results in the tree
in Figure 27-6b. The mechanics of this rotation are the same as the one in Figure 27-3, where the rota-
tion is about node
C
. The subtree heights differ in these two figures, however.
Unfortunately, this rotation does not balance the tree. A subsequent left rotation about the node
containing 60—corresponding to node
C
in Figure 27-5b—is necessary to restore the balance
(Figure 27-6c). Together, these two rotations are called a
right-left double rotation
. First, 60
rotates above 80 and then it rotates above 50. Again, notice that after each rotation, the tree is still a
binary search tree.
FIGURE 27-6
(a) Adding 70 to the tree in Figure 27-2c destroys its balance; to
restore the balance, perform both (b) a right rotation and (c) a
left rotation
(a) After adding 70
(b) After right rotation
(c) After left rotation
50
50
60
20
80
20
60
50
80
60
90
80
70
90
20
70
90
70
Let's look at the general case. Figure 27-7a shows a subtree of an AVL tree that is height bal-
anced. Node
N
has a child
C
and a grandchild
G
. An addition that occurs in the right subtree
T
3
of
node
G
adds a leaf to
T
3
. When such an addition increases the height of
T
3
, as Figure 27-7b shows,
the subtree rooted at
N
becomes unbalanced. Notice that nodes
N
,
C
, and
G
correspond to the nodes
in Figure 27-6a that contain 50, 80, and 60, respectively.
Node
N
is the first node that is unbalanced along the path between the inserted leaf and
N
.
After a right rotation about node
G
, the subtree rooted at
G
is unbalanced, as Figure 27-7c shows.
