Java Reference
In-Depth Information
could run in
O
(
1
) steps instead of
O
(
n
) steps. It might seem like the
intersection
method will now run in
O
(
n
) steps, but by switching to a hash table, it becomes more
difficult to iterate through the set of items. Instead of traversing a single linked list to
retrieve every item in the set, the hash table version must now iterate through the hash
table array and then for each index in the array iterate through the linked list at that
index. If the array is size
N
and the number of items in the hash table is
n
, then the
iteration time becomes
O
(
N
+
n
). In practice, we would expect
N
to be larger than
n
.
So although we have decreased the number of steps it takes to look up an item, we have
increased the number of steps it takes to iterate over every item. If this is troublesome,
you could overcome this problem with an implementation of
Set<T>
that uses both
a linked list (to facilitate iteration) and a hash table (for fast lookup). However, the
complexity of the code is significantly increased using such an approach. You are asked
to explore the hash table implementation in Programming Project 15.10.
Self-Test Exercises
23. Write a method named
difference
that returns the difference between two
sets. The method should return a new set that has items from the fi rst set that
are not in the second set. For example, if
setA
contains {1, 2, 3, 4} and
setB
contains {2, 4, 5}, then
setA.difference(setB)
should return the set {1, 3}.
24. What is the run time of the
difference
method for the previous question?
Give your answer using big-
O
notation.
15.7
Trees
I think that I shall never see a data structure as useful as a tree.
ANONYMOUS
The tree data structure is an example of a more complicated data structure made with
links. Moreover, trees are a very important and widely used data structure. So, we will
briefly outline the general techniques used to construct and manipulate trees. This
section is only a very brief introduction to trees to give you the flavor of the subject.
This section uses recursion, which is covered in Chapter 11 .
Tree Properties
A tree is a data structure that is structured as shown in Display 15.39. In particular,
in a tree you can reach any node from the top (root) node by some path that follows
the links. Note that there are no cycles in a tree. If you follow the links, you eventually
get to an “end.” A definition for a tree class for this sort of tree of
int
s is outlined
in Display 15.39. Note that each node has two references to other nodes (two links)
coming from it. This sort of tree is called a
binary tree
, because each node has exactly
binary tree
