Java Reference
In-Depth Information
18.
Why might a binary search tree work poorly as an implementation of a priority queue?
19.
Consider a method for a binary search tree that decides whether the tree is height balanced, as Segment 25.41
describes. The header of the method could be as follows:
public boolean
isBalanced()
Write this method for the class
BinarySearchTree
. It should call a private recursive method of the same name.
20.
Write a static method that accepts as its argument a
BinaryTree
object and returns true if the argument tree is a
binary search tree. Examine each node in the given tree only once.
21.
Implement the method
toString
for the class
BinarySearchTree
. The method should return a string that, when
displayed, shows the shape of the tree in two dimensions. Ignore the data in each node. For example a tree might
appear as follows:
o
/\
oo
/\
oo
22.
Consider two empty binary search trees that allow duplicate entries with the same search key. To one of the trees,
add
m
unique entries, each with a different search key. To the other, add each of these
m
entries
k
times for a total
of
m
k
entries. Assuming that each entry is stored in a single node, compare the heights of the two trees. Discuss
how the order in which entries are added to the second tree affects its height. Give the addition orders that lead to
the tallest tree and the shortest tree.
×
23.
Segment 25.4 describes a binary search tree that allows duplicates. You place the duplicate of an entry in the
entry's right subtree.
a.
What is an advantage and a disadvantage of this scheme?
b.
Suppose that we change the definition of a binary search tree so that the duplicate of an entry can be in
either the entry's right subtree or its left subtree. If we choose the subtree randomly, what is an advantage
and a disadvantage of this scheme?
P
ROJECTS
1.
Specify and implement a class of binary search trees in which duplicate entries are allowed. Place the duplicate of
an entry in the entry's right subtree, as suggested in Segment 25.4. Provide a method that searches the tree for a
given entry and returns the first one it finds. Also, provide a similar method that returns a list of all entries that
match the given one.
2.
Repeat the previous project, but instead randomly place the duplicate of an entry in the entry's left or right subtree.
Thus, we modify the definition of a binary search tree as follows.
For each node in a binary search tree,
•
The data in a node is greater than
or equal to
the data in the node's left subtree
•
The data in a node is less than
or equal to
the data in the node's right subtree
Searching for a duplicate must allow a search of both subtrees.
3.
Implement the ADT sorted list by using a binary search tree.
