Application of Trees: Set Representation and Union, Find Operations

Application of Trees: Set Representation and Union, Find Operations

Trees represent the hierachical structure hence associated with this structure there are many applications of trees which are listed below.

1. The trees are used in data compression techniques for encoding the compressed data.

2. The expression trees are special type of trees in which the root/parent node is for operator and child nodes hold the values of operands.

For example : The expression a + (b*c) can be represented with the help of trees as.

Here from this expression tree we can generate infix, prefix, postfix expressions by traversing the tree in inorder, preorder and postorder manner respectively.

infix expression a+(b*c)

prefix expression +a*bc

postfix expression abc*+

3. The tree is a useful data structure used by the complier in the parsing phase. The parse tree for the tokens is generated for particular programming statement and then complier checks for the syntax errors.

4. Trees are also used in game playing such as Tic Tac Toe. The trees built in the game playing are called decision trees.

5. As data is arranged systematically in binary search trees, the binary search trees are used in sorting and searching of records.

1. Set Representation

A set data structure is a data structure that contains the partitioned sets. These partitioned sets are separate non overlapping sets.

For example consider a set S = {S₁, S₂, ... S_k} in which each member S_i represents the distinct set. These sets are dynamic sets.

Representing set using linked list is the most convenient method. The representation for sets (10, 20, 30} and {5, 8} can be ‒

For each set a linked list is created. The head node is the starting node of each set and tail node points to the last node of the set.

2. Union and Find Operations

• There are two tasks that are performed on set data structure

■ Union : This operation is for combining two sets into a single set.

■ Find : This operation is for finding the particular element from the disjoint sets.

• To support these tasks following are the operations that are used:

1. MakeSet(x) : This function is for creating a new set.

2. Union(x,y) : This function is for uniting two sets. Hence resulting set is S_x U S_y.

• FindSet(x): This function returns the pointer to the set containing x.

• The union operation performs the union of two elements X₁ and X₂ at a time from each set.

• Fig. 6.8.2 represents that after performing union operation on two sets, the tree structure is Fig. 6.8.2 (a) and (b) represents two disjoint sets represented as trees and (c) represents the result of union operation.

Algorithms for Makeset, Find and Union

Algorithm Makeset (x)

{

     // Problem Description : This algorithm creates

     // the set with x element

     x.parent <‒x //Here x. parent means parent of x

}

Algorithm Find (x)

{

     // Problem Description: This algorithm is

     // for returning the desired element

     if (x.parent = x) then

          return x

     else

          return Find (x.parent)

}

Algorithm Union (x1, x2)

{

     // Problem Description: For uniting two elements

     // x1 and x2 this algorithm is used

     x1Root <‒ Find (x1)

     x2Root <‒ Find (x2)

     x1Root.parent <‒ x2Root

}

Review Questions

1. Write C++ code for the implementation of different types of tree traversals. State few tree applications.

2. How can you construct an expression tree? Describe your answer with an example.

3. Discuss how sets are represented ?

4. Explain union find operations?

5. Explain the algorithm for union and find operations in disjoint sets.