# Augmenting Data Structure

In this article, we will learn **what Augmenting Data Structure is and how to represent an augmented data structure?** Augmentation strategies and algorithm for determining the rank of a particular node in a order static tree also prescribed in this article.

Submitted by Abhishek Kataria, on June 17, 2018

## Augmenting Data Structure

**Augmenting data structure means adding some extra information to the existing data structure so that the data structure can be implemented efficiently**. Typically any node of a tree contains some useful information such as a left pointer, right pointer, data, parent node, the color of the node. This information is useful for accessing particular node more efficiently from the given tree. For each node k, add a new field size(k) now with this size information there can be fast computing access of dynamic order statics and rank of a particular node will be determined. In this position of a node is in linear order. Let us see know how this augmentation helps us to use the Red Black Tree.

### Dynamic order statics

For **augmenting the data structure** we will simply store, extra information of size. The augmented tree is also called as order static tree. Hence every node of order static tree has following features which are as follows:

- Address of parent node
- Address of left child
- Address of right child
- Color
- Key value
- Size of a particular node

**Representation of order static tree**

In the above-given tree, the Red Black Tree is augmented because in this we have computed the size of each node and storing the information about size in each node.

Consider that if we need to compute the size of node k then:

size[k] = size[left node[k]] +size[right node[k]]+1

Consider the leaf node 22 which has no left child and right child hence:

size[22] =size[left[22]]+size[right[22]]+1 size[22] =0+0+1=1

### Augmentation strategy

Following are the steps which are needs to be followed when we want to augment a data structure.

- Firstly choose a data structure which has to be augmented.
- Then find out the additional information which is needed to be added and which also support the algorithm.
- Then it is verified whether the operation of Red Black tree will work with this additional information or not.
- The information which is required by Red Black tree is chosen for developing new operations.
- Size and rank are the two types of additional information which are required to enhance the performance of a basic data structure.

### Determining, Rank of the node

Rank of the particular node in the order static tree indicates the position of that node in the inorder sequence. For determining the position of a particular node the following algorithm is prescribed below:

Algorithm Determining the rank(root, k){ //input: root denotes the root node of the tree and k //denotes the node whose rank is to be determined. //output: rank of k node. rank ← size [left[k]] +1 temp ← k While (temp! =root) { If (temp=right[parent[temp]])then rank ← rank +size [left[parent[temp]]]+1 temp ← k[temp] } return rank }

By this algorithm, we can derive a rank for a particular node for a given order static tree.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.