Java Reference
In-Depth Information
chapter
19
F
or large amounts of input, the linear access time of linked lists is prohib-
itive. In this chapter we look at an alternative to the linked list: the
binary
search tree,
a simple data structure that can be viewed as extending the binary
search algorithm to allow insertions and deletions. The running time for most
operations is
O
(log
N
) on average. Unfortunately, the worst-case time is
O
(
N
)
per operation.
In this chapter, we show
The basic binary search tree
n
A method for adding order statistics (i.e., the
findKth
operation)
n
Three different ways to eliminate the
O
(
N
) worst case (namely, the
AVL tree, red-black tree,
and
AA-tree
)
n
Implementation of the Collections API
TreeSet
and
TreeMap
n
Use of the
B-tree
to search a large database quickly
n
basic ideas
19.1
In the general case, we search for an item (or element) by using its
key
. For
instance, a student transcript could be searched on the basis of a student ID
number. In this case, the ID number is referred to as the item's key.
Search WWH ::
Custom Search