Data structure augmentation

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.

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.

Widely used data structures

*Linked List
*Hash Table
*Binary Tree
*AVL Tree
*Red Black Tree
*Binary heap
*Binomial heap

References

*

External links

* [http://www.cs.rochester.edu/~gildea/csc282/slides/C14-augmenting.pdf Augmenting a Red Black Tree]