9.1: Overview

In the previous chapter, techniques were presented for ordering and storing data so that it could be efficiently searched and traversed when desired. Those methods work well as long as the collection of data is essentially static?/FONT>meaning that relatively few insertions and deletions are required. This is a general characteristic of arrays, which were the basis for the faster binary search: they support efficient search but not efficient insertion and deletion. Lists can be used for more efficient insertion and deletion, but then a binary search is not possible.

In this chapter the focus is on achieving efficient search and efficient insertions and deletion. Sometimes traversals through the data in sorted order by key value are also desirable. Four data structures that are appropriate for dealing with dynamic data are presented. First, priority queues are discussed. They provide the means to deal with a special case of insertion and deletion, as well as serving as an application of heaps. Next, hash tables are considered. Hash tables are important data structures that have excellent average search, insertion, and deletion times. Finally, binary search trees and AVL trees are introduced. These data structures support all the operations?/FONT>search, insertion, deletion, and traversal?/FONT>quite well.