Java Reference
In-Depth Information
4.
Devise an algorithm that uses a binary search tree to sort an array of objects. Such a sort is called
treesort
.
Implement and test your algorithm. Discuss the time efficiency of your treesort in both the average and worst cases.
5.
Implement a binary search tree that includes the following methods based on Exercises 15 and 16:
/** @return the entry with the smallest search key */
public
T getMin();
/** @return the entry with the largest search key */
public
T getMax();
/** @return either the inorder predecessor of entry, or
entry if it's the smallest element in the tree, or
null if entry is not in the tree */
public
T getPredecessor(T entry);
/** @return either the inorder successor of entry, or
entry if it's the largest element in the tree, or
null if entry is not in the tree */
public
T getSuccessor(T entry);
6.
Implement the class
ArrayBinarySearchTree
that extends
ArrayBinaryTree
, described in Project 7 of Chapter 24.
7.
Write Java code that creates a binary search tree from
n
random integer values and returns the height of the search
tree. Run the code for
n
=
2
h
-
1, where
h
ranges from 4 to 12. Compare the height of the randomly built search tree
with
h
, the height of the shortest binary search tree.
8.
Chapter 1 defined a set as a bag that does not permit duplicate entries. Define a class of sets that uses a binary
search tree to store a set's entries.
9.
Repeat Project 3 of Chapter 19, but use binary search trees to implement the two dictionaries. Write Java code that
will create within the first dictionary a balanced binary search tree of the reserved words in the Java language.
Why is it important that the search tree containing Java reserved words be balanced? Can you guarantee that the
search tree of user-defined identifiers is also balanced?
10.
Compare the performance of two binary search trees as more objects are added to them. Initially, one tree is
balanced and the other is not.
First modify
BinarySearchTreeInterface
and
BinarySearchTree
so that the
add
method returns the number
of comparisons used. Then write a program that uses the new version of
BinarySearchTree
, as follows. Create two
empty binary search trees. Associate two variables with each tree. One variable sums the number of comparisons
used in adding values to a tree, and the other sums the heights of a tree at certain times following the insertion of
several values. Name these variables
comparisonSum1
,
comparisonSum2
,
heightSum1
, and
heightSum2
.
In a loop that executes 100 times, do the following:
•
Add the values 1000, 2000, 3000, 4000, 5000, 6000, and 7000 to both trees. In the first tree, add
them in increasing order. In the second, add them in an order that forms a complete tree. Your first
tree will be unbalanced, while the second tree will be balanced.
•
Generate 10 random values between 0 and 8000. Add these values to each tree in the same order.
After each of these additions, update each tree's
comparisonSum
variable by the number of compar-
isons performed for the insertion.
•
Add each tree's height to its
heightSum
variable.
•
Clear the two trees.
