Java Reference
In-Depth Information
implementing the collections
api
TreeSet
and
TreeMap
classes
19.7
In this section we provide a reasonably efficient implementation of the
Collections API
TreeSet
and
TreeMap
classes. The code is a blend of the
Collections API linked list implementation presented in Section 17.5 and
the AA-tree implementation in Section 19.6. Some AA-tree details are not
reproduced here because the core private routines, such as the tree rota-
tions, are essentially unchanged. Those routines are contained in the
online code. Other routines, such as the private
insert
and
remove
, are only
slightly different than those in Section 19.6, but we rewrite them to show
the similarity and for completeness.
The basic implementation resembles that of the standard
LinkedList
class
with its node, set, and iterator classes. However, there are two main differ-
ences between the classes.
1.
The
TreeSet
class can be constructed with a
Comparator
, and the
Comparator
is saved as a data member.
2.
The
TreeSet
iteration routines are more complex than those of the
LinkedList
class.
Iteration is the trickiest part. We must decide how to perform the traversal.
Several alternatives are available:
1.
Use parent links
2.
Have the iterator maintain a stack that represents the nodes on the
path to the current position
3.
Have each node maintain a link to its inorder successor, a technique
known as a
threaded tree
To make the code look as much as possible like the AA-tree code in
Section 19.6, we use the option of having the iterator maintain a stack. We
leave using parent links for you to do as Exercise 19.32.
Figure 19.68 shows the
TreeSet
class skeleton. The node declaration is
shown at lines 12 and 13; the body of the declaration is identical to the
AANode
in Section 19.6. At line 18 is the data member that stores the comparison
function object. The routines and fields in lines 54-55, 57-58, 62-63, and
70-77 are essentially identical to their AA-tree counterparts. For instance,
the differences between the
insert
method at lines 54-55 and the one in the
AATree
class is that the
AAtree
version throws an exception if a duplicate is
Search WWH ::
Custom Search