Java Reference
In-Depth Information
strategy gives the best balance? Which takes the least CPU time to
process an entire sequence of operations?
a.
Replace with the value in the largest node, X, in T L and recur-
sively remove X .
b.
Alternatively replace with the value in the largest node in T L or
the value in the smallest node in T R and recursively remove the
appropriate node.
c.
Replace with the value in the largest node in T L or the value in the
smallest node in T R (recursively remove the appropriate node),
making the choice randomly.
19.26
Implement a binary search tree to allow duplicates. Have each node
store a linked list of items that are considered duplicates (using the
first item in the linked list) to control branching.
Implement a toString method for class BinarySearchTree . Make sure
your method runs in linear time. Hint: Use a private recursive method
that has a Node and a StringBuilder as its parameters.
19.27
Write the remove method for red-black trees.
19.28
Implement the search tree operations with order statistics for the bal-
anced search tree of your choice.
19.29
Implement TreeSet method lower , which returns the greatest element in
the set strictly less than the given element. Then implement method
floor , which returns the greatest element in the set less than or equal to
the given element. Both routines return null if there is no such element.
19.30
Implement TreeSet method higher , which returns the least element in the
set strictly greater than the given element. Then implement method
ceiling , which returns the least element in the set greater than or equal
to the given element. Both routines return null if there is no such element.
19.31
Reimplement the TreeSet class by using parent links.
19.32
Reimplement the TreeSet class by adding to each node two links: next and
previous , representing the previous and next item that would be obtained
in an inorder tree traversal. Also add header and tail nodes to avoid spe-
cial cases for the minimum and maximum item. This simplifies the itera-
tor implementation considerably, but requires revisions to the mutators.
19.33
Modify the TreeSet and TreeMap classes so that their iterators are
bidirectional.
19.34
Implement TreeSet method descendingSet which return a view of the
set, whose iterator and toString methods view items in decreasing
sorted order. Changes to the underlying set should reflect automati-
cally in the view, and vice-versa.
19.35
Search WWH ::




Custom Search