Home » Data Structure

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:

1. Address of parent node
2. Address of left child
3. Address of right child
4. Color
5. Key value
6. 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.

1. Firstly choose a data structure which has to be augmented.
2. Then find out the additional information which is needed to be added and which also support the algorithm.
3. Then it is verified whether the operation of Red Black tree will work with this additional information or not.
4. The information which is required by Red Black tree is chosen for developing new operations.
5. 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.