Java Reference
In-Depth Information
10.
Since we had a binary search tree before the rotation, the value in node
N
is greater than the values in nodes
C
and
G
and all the values in
T
2
and
T
3
. The value in node
C
is less than the value in node
G
, and each of these two
values is less than all values in
T
3
. Moreover, all values in
T
2
are less than the value in node
G
but greater than the
value in node
C
. These relationships are maintained after the rotation: Node
G
has node
C
as its left child and
node
N
as its right child;
T
2
is a right subtree of node
C
, and
T
3
is a left subtree of node
N
. The subtrees
T
1
and
T
4
have their original parents in the new tree. Thus, the resulting tree is a binary search tree.
11.
private
BinaryNodeInterface<T> rotateLeft(BinaryNodeInterface<T> nodeN)
{
BinaryNodeInterface<T> nodeC = nodeN.getRightChild();
nodeN.setRightChild(nodeC.getLeftChild());
nodeC.setLeftChild(nodeN);
return
nodeC;
}
// end rotateLeft
12.
60, 20, 10.
60, 20, 50, 55.
60, 20, 50, 35, 40.
60, 20, 50, 35.
13.
35 60
20
50
80
10
30
40
55
70
90
14.
60
20 40
80
10
70
90
30
50
15.
The 2-3 tree is shorter than the AVL tree and is balanced.
16.
a.
20, 10.
b.
20, 50, 80, 55, 60.
c.
20, 50, 35, 40.
d.
20, 50, 35.
17.
50
20
80
90
10
35 40
55 60 70
