Java Reference
In-Depth Information
a node
v
is one more than the sum of the sizes of its two children. Figure 26.12
shows an AVL tree and the
size
value for each node in the tree.
size: 6
25
size: 2
size: 3
20
34
size: 1
size: 1
size: 1
5
30
50
F
IGURE
26.12
The
size
data field in
AVLTreeNode
stores the number of nodes in the sub-
tree rooted at the node.
In the
AVLTree
class, add the following method to return the
k
th smallest ele-
ment in the tree.
public
E find(
int
k)
The method returns
null
if
k<1
or
k > the size of the tree
. This method
can be implemented using the recursive method
find(k, root)
, which returns
the
k
th smallest element in the tree with the specified root. Let
A
and
B
be the left
and right children of the root, respectively. Assuming that the tree is not empty
and
k
…
root
.
size
,
find(k, root)
can be recursively defined as follows:
E
root
.
element
,
if A is null and k is
1;
B
.
element
,
if A is null and k is
2;
find
(
k
,
A
),
if k
find
(
k
,
root
)
=
6 =
A
.
size
;
root
.
element
,
if k
=
A
.
size
+
1;
find
(
k
-
A
.
size
-
1,
B
),
if k
7
A
.
size
+
1;
Modify the
insert
and
delete
methods in
AVLTree
to set the correct value
for the
size
property in each node. The
insert
and
delete
methods will still
be in
O
(log
n
) time. The
find(k)
method can be implemented in
O
(log
n
) time.
Therefore, you can find the
k
th smallest element in an AVL tree in
O
(log
n
) time.
Use the following main method to test your program:
import
java.util.Scanner;
public class
Exercise26_05 {
public static void
main(String[] args) {
AVLTree<Double> tree =
new
AVLTree<>();
Scanner input =
new
Scanner(System.in);
System.out.print(
"Enter 15 numbers: "
);
for
(
int
i =
0
; i <
15
; i++) {
tree.insert(input.nextDouble());
}
System.out.print(
"Enter k: "
);
System.out.println(
"The "
+ k +
"th smallest number is "
+
tree.find(k));
}
}
**26.6
(
Test
AVLTree
) Design and write a complete test program to test if the
AVLTree
class in Listing 26.4 meets all requirements.
Search WWH ::
Custom Search