Data structure augmentation


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]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Structure du tableau périodique — Tableau périodique des éléments Pour les articles homonymes, voir Tableau. Le tableau périodique des éléments, également appelé table de Mendeleïev, classification périodique des éléments (CPE) ou simplement tableau périodique, représente tous… …   Wikipédia en Français

  • Augmentation du niveau de la mer — Élévation du niveau de la mer Les mesures du niveau de la mer à partir de 23 enregistrements de marégraphes dans des environnements géologiquement stables montrent une élévation d environ 2 mm par an …   Wikipédia en Français

  • Augmentation du niveau des mers — Élévation du niveau de la mer Les mesures du niveau de la mer à partir de 23 enregistrements de marégraphes dans des environnements géologiquement stables montrent une élévation d environ 2 mm par an …   Wikipédia en Français

  • Enhanced Data Rates For GSM Evolution — Générations et normes de téléphonie mobile 0G PTT MTS IMTS AMTS 0,5G Autotel/PALM ARP 1G NMT AMPS Hicap CDPD Mobitex DataTac TACS RC2000 C NETZ Comvik NTT …   Wikipédia en Français

  • Enhanced Data Rates for Global Evolution — Enhanced Data Rates for GSM Evolution Générations et normes de téléphonie mobile 0G PTT MTS IMTS AMTS 0,5G Autotel/PALM ARP 1G NMT AMPS Hicap CDPD Mobitex DataTac TACS RC2000 C NETZ Comvik NTT …   Wikipédia en Français

  • XML — Infobox file format name = Extensible Markup Language icon = logo = extension = .xml mime = application/xml, text/xml (deprecated) type code = uniform type = public.xml magic = owner = World Wide Web Consortium genre = Markup language container… …   Wikipedia

  • Relational model — The relational model for database management is a database model based on first order predicate logic, first formulated and proposed in 1969 by Edgar Codd. [ Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks , E.F …   Wikipedia

  • Skip list — Invented in 1990 by William Pugh, a skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).Underlying the… …   Wikipedia

  • Charles Sanders Peirce bibliography — C. S. Peirce articles  General:    Charles Sanders Peirce Charles Sanders Peirce bibliography Philosophical:    Categories (Peirce) Semiotic elements and   classes of signs (Peirce) Pragmatic maxim • Pragmaticism… …   Wikipedia

  • Pseudoforest — A 1 forest (a maximal pseudoforest), formed by three 1 trees In graph theory, a pseudoforest is an undirected graph[1] in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of ve …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.