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