Java Reference
In-Depth Information
public boolean
hasNext()
{
return
localIterator.hasNext();
}
// end hasNext
public
K next()
{
Entry<K, V> nextEntry = localIterator.next();
return
nextEntry.getKey();
}
// end next
public void
remove()
{
throw new
UnsupportedOperationException();
}
// end remove
}
// end KeyIterator
You implement
getValueIterator
in a similar manner.
25.48
Comments.
This implementation of the ADT dictionary is as time efficient as the underlying
search tree. When the binary search tree is balanced, the operations are O(log
n
). But a binary
search tree can lose its balance, and so the efficiency of the dictionary operations can degrade to
O(
n
) as entries are added or removed. A search tree that stays balanced, such as those you will see
in Chapter 27, would provide a better implementation of the dictionary than the one shown here.
Also, notice that a binary search tree maintains the dictionary entries in sorted order by their
search keys. As a result,
getKeyIterator
enables us to traverse the search keys in sorted order. In
contrast, other dictionary implementations—hashing, for example—traverse the search keys in
unsorted order.
C
HAPTER
S
UMMARY
•
A binary search tree is a binary tree whose nodes contain
Comparable
objects. For each node in the tree,
The data in a node is greater than the data in the node's left subtree
■
The data in a node is less than (or equal to) the data in the node's right subtree
■
•
A search tree has the operations
contains
,
getEntry
,
add
,
remove
, and
getInorderIterator
, in addition to
the operations common to all trees.
•
The class
BinarySearchTree
can be a subclass of
BinaryTree
, but it must disallow
setTree
. A client must
create a binary search tree by using only the
add
method, to avoid changing the order of the nodes in the tree.
•
The search algorithm to locate an entry in a binary search tree forms the basis of the methods
getEntry
,
add
,
and
remove
. These methods each have reasonable iterative and recursive implementations.
•
Each addition of an entry to a binary search tree adds a leaf to the tree. The new entry is placed where the
search algorithm will find it.
•
Removing an entry from a binary search tree depends on the number of children that belong to the node con-
taining the entry. When the node is a leaf or has one child, you remove the node itself. The node's parent can
adopt a solitary child when it exists. However, when the node
N
has two children, you replace the node's
entry with another one
r
whose node is easy to remove. To maintain the order of the binary search tree, this
entry
r
can be either the largest entry in
N
's left subtree or the smallest entry in
N
's right subtree. It follows
that
r
's node is either a leaf or a node with one child.
