 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Augmenting Data Structures
Chapter Overview - Chapter 14| There are some engineering situations that require no more than a “textbook” data structure—such as a doubly linked list, a hash table, or a binary search—tree but many others require a dash of creativity. Only in rare situations will you need to create an entirely new type of data structure, though. More often, it will suffice to augment a textbook data structure by storing additional information in it. You can then program new operations for the data structure to support the desired application. Augmenting a data structure is not always straightforward, however, since the added information must be updated and maintained by the ordinary operations on the data structure.
This chapter discusses two data structures that are constructed by augmenting red-black trees. Section 14.1 describes a data structure that supports general order-statistic operations on a dynamic set. We can then quickly find the ith smallest number in a set or the rank of a given element in the total ordering of the set. Section 14.2 abstracts the process of augmenting a data structure and provides a theorem that can simplify the augmentation of red-black trees. Section 14.3 uses this theorem to help design a data structure for maintaining a dynamic set of intervals, such as time intervals. Given a query interval, we can then quickly find an interval in the set that overlaps it. |
|
2002 McGraw-Hill Higher Education