Augmenting Data Structures
From Wikipedia, the free encyclopedia
In computer science augmenting a data structure means modifying it in some way to create a new one by storing new information in it. Augmenting data structures is quite common in software developing. This is mainly due to specific requirements of the application in development.
Contents |
[edit] An Augmentation Strategy
In order to augment a data structure consider these guidelines:
- Choose an underlying data structure.
- Determine additional information to be maintained in underlying data structure.
- Verify that the additional information can be maintained for the basic modifying operations on the underlying data structure.
- Develop new operations.
These guidelines are not steps of an augmentation algorithm. They are not meant to be followed in precise order in which they are listed either. This four step method should help you in your efforts in augmenting a data structure, and organization of documentation of an augmented data structure.
Ideally, a product of augmentation should maintain the new information efficiently by most of the built-in procedures. If this goal is not reached, choice of a different data structure (step 1) or newly stored information (step 2) might improve the efficiency.
[edit] References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 14.2: How to Augment a Data Structure, pp.302–309.
