Examples of Augmenting a Data Structure
There are many examples of augmenting data structures, and augmenting is simply changing the existing data structure to solve our problem.
- Augmented Queue for Maximum Element: In an augmented queue, each element not only stores its value but also maintains information about the maximum element in the current queue up to that point.
- Augmented Trie for Prefix Sums: Consider a trie (prefix tree) data structure where each node stores the sum of values of all elements with the same prefix up to that node.
- Augmented AVL Tree for Rank Queries: In an AVL tree (a self-balancing binary search tree), each node can store the rank of that node in the tree, i.e., the number of nodes in its left subtree plus one.
- Augmented Disjoint Set (Union-Find) for Set Size: In a disjoint set data structure, each set representative (root) could store the size of its corresponding set.
Introduction to Augmented Data Structure
Data Structures play a significant role in building software and applications but many a times all our requirements are not satisfied using an existing data structure. This is when we modify an existing data structure according to our needs. This article will provide a brief introduction about when and how to Augment a Data Structure.
Table of Content
- What is an Augmented Data Structure?
- Examples of Augmenting a Data Structure
- Considerations before Augmenting a Data Structure
- How to Augment a Data Structure?
- A Problem using Augmentation of Data Structure