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.
 
Search WWH ::




Custom Search