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