Java Reference
In-Depth Information
12.
Segment 25.17 gave an iterative algorithm for the method
addEntry
. Implement the following alternate algorithm
for this method:
Algorithm
addEntry(binarySearchTree, newEntry)
result =
null
currentNode =
root node of
binarySearchTree
parentNode =
null
while
(newEntry
is not found and
currentNode
is not
null
)
{
if
(newEntry
matches entry in
currentNode)
{
result =
entry in
currentNode
Replace entry in
currentNode
with
newEntry
}
else if
(newEntry <
entry in
currentNode)
{
parentNode = currentNode
currentNode =
the left child of
currentNode
}
else
// newEntry >
entry in
currentNode
{
parentNode = currentNode
currentNode =
the right child of
currentNode
}
}
if
(newEntry
is not found in the tree
)
{
Create a new node and place
newEntry
into it
if
(newEntry <
entry in
parentNode)
Make the new node the left child of
parentNode
else
Make the new node the right child of
parentNode
}
return
result
13.
The methods
remove
and the recursive
removeEntry
, as described in Segments 25.28 through 25.30, use the inner
class
ReturnObject
. In this way,
removeEntry
can convey to
remove
both the root of the revised tree and the entry
it removed. Revise these methods to instead use a class
Pair<T1, T2>
, like the one given in Segment B.40 of
Appendix B.
Pair
will need accessor methods for its fields. The method
removeEntry
can then return the root and
the removed entry as a
Pair
object.
14.
Segment 25.43 builds a balanced binary search tree from one particular group of search keys. Generalize this
approach, and write a recursive algorithm that creates a balanced binary search tree from a sorted collection
of
n
items.
15.
Write an algorithm that returns the smallest search key in a binary search tree.
16.
Beginning with Segment 25.23, you saw how to find the inorder predecessor or the inorder successor of a node
with two children. Unfortunately, this approach will not work for a leaf node. For a node with one child, the
technique will find either the predecessor or the successor, but not both. Discuss how the structure of a node might
be modified so that the inorder predecessor or the inorder successor can be found for any node.
17.
Write an algorithm that returns the second largest value in a binary search tree containing at least two nodes.