Java Reference
In-Depth Information
3.
Node
N
contains 60, and node
C
contains 80.
T
3
is the one-node subtree containing 90.
T
1
and
T
2
are empty.
4.
Part
a
of the following figure shows an imbalance at node
N
after 10 was added to the tree. A left rotation restores
the tree's balance, as Part
b
illustrates.
(b)
(a)
C
N
5
7
N
T
3
T
1
C
3
7
5
9
T
2
6
9
T
3
T
1
3
6
T
2
10
5.
Node
N
contains 50, node
C
contains 80, and node G contains 60.
T
1
,
T
3
, and
T
4
are one-node subtrees:
T
1
contains 20,
T
3
contains 70, and
T
4
contains 90.
T
2
is empty. In Parts
a
and
b
,
T
2
is the left subtree of 60. In Part
c
,
it is the right subtree of 50.
6.
Node
N
contains 50, node
C
contains 20, and node G contains 40.
T
1
,
T
2
, and
T
4
are one-node subtrees:
T
1
contains 10,
T
2
contains 35, and
T
4
contains 55.
T
3
is empty. In Parts
a
,
b
and
c
,
T
3
is the right subtree of 40. In
Part
d
, it is the left subtree of 50.
7.
70
40
80
20
50
90
60
10
30
8.
The following binary search tree is taller than the previous AVL tree, and it is not balanced:
70
20
80
10
50
90
60
40
30
9.
Since we had a binary search tree before the rotation, the value in node
N
is less than the values in nodes
C
and
G
and all the values in
T
2
and
T
3
. The value in node
C
is greater than the value in node
G
, and each of these two
values is greater than all values in
T
2
. Moreover, all values in
T
3
are less than the value in node
C
but greater than
the value in node
G
. These relationships are maintained after the rotation: Node
G
has node
N
as its left child and
node
C
as its right child;
T
2
is a right subtree of node
N
, and
T
3
is a left subtree of node
C
. The subtrees
T
1
and
T
4
have their original parents in the new tree. Thus, the resulting tree is a binary search tree.
