PROBLEM: IMPLEMENTATION OF A SET USING A BINARY TREE

Implement union() and find() operations on sets represented as trees.

Program

#include <stdio.h> #define N 100 // max no of elements together in all sets. typedef int type; typedef struct node node; struct node { type val; // this is value of member. int parent; // this is index of parent in the array. }; node sets[N]; // all sets are contained in it. int setsindex = 0; // total no of elements in sets. int insertRoot( type val ) { /* * insert val in sets as a root of a new tree. */ sets[setsindex].val = val; sets[setsindex].parent = -1; setsindex++; return setsindex-1; } void insertElement( int rootindex, type val ) { /* * insert element val in set whose root is indexed at rootindex. */ sets[setsindex].val = val; sets[setsindex].parent = rootindex; setsindex++; } int buildSet( type a[], int n ) { /* * repeated calls to this fun with diff arrays will insert diff set in sets. * forms a tree representation of elements in a. * n is number of elements in the set. * empty set(n==0) cannot be represented here. * returns index of root. */ int i, rootindex; if( n <= 0 ) { fprintf( stderr, "n should be > 0.\n" ); return -1; } // check whether there is enough space for n elements. if( setsindex+n > N ) { fprintf( stderr, "ERROR: set overflow.\n" ); return -1; } // a[0] becomes the root. rootindex = insertRoot( a[0] ); for( i=1; i<n; ++i ) insertElement( rootindex, a[i] ); return rootindex; } void printSets() { int i; printf( "\n" ); for( i=0; i<setsindex; ++i ) printf( "%d %d.\n", sets[i].val, sets[i].parent ); printf( "\n" ); } int unionSets( int rindex1, int rindex2 ) { /* * makes a union of sets whose root indices are rindex1 and rindex2. */ sets[rindex2].parent = rindex1; // or the reverse. return rindex1; // root of the union. } int findSet( int valindex ) { /* * given a val at index valindex in the array, finds index of its root. */ for( ; sets[valindex].parent!=-1; valindex=sets[valindex].parent ) ; return valindex; } int getIndex( type val ) { /* *

dummy

procedure to return index in array of val. */ int i; for( i=0; i<setsindex; ++i ) if( sets[i].val == val ) return i; return -1; } int main() { type s1[] = {1,7,8,9}; type s2[] = {5,2,10}; type s3[] = {3,4,6}; int i1 = buildSet( s1, 4 ); int i2 = buildSet( s2, 3 ); int i3 = buildSet( s3, 3 ); //printSets(); i1 = unionSets( i1, i2 ); printf( "%d %d.\n", 3, sets[findSet( getIndex(3) )].val ); printf( "%d %d.\n", 5, sets[findSet( getIndex(5) )].val ); printf( "%d %d.\n", 2, sets[findSet( getIndex(2) )].val ); i3 = unionSets( i3, i1 ); printf( "%d %d.\n", 3, sets[findSet( getIndex(3) )].val ); printf( "%d %d.\n", 5, sets[findSet( getIndex(5) )].val ); printf( "%d %d.\n", 7, sets[findSet( getIndex(2) )].val ); printSets(); return 0; }

Explanation

1. We represent sets as trees in which different elements are stored as nodes in a tree. Since the order of elements is immaterial in sets, the order of nodes also does not matter in the tree. However, the links of the tree are reversed , that is, the child nodes have links to the parent instead of the parent pointing to its children. The reason for this representation is discussed next .
   Example:

   

2. Union of two disjointed sets S1 and S2 ( unionSets() ) under the tree representation can be carried out simply by making any node of S1 the parent node of the root node of S2, or vice-versa. This operation can be carried out in a constant amount of time.
   Example:

   

3. The find operation ( findSet() ) searches for the root of an element in the tree. It travels from that element upwards in the hierarchy until it reaches a node that has no parent. Thus, its root is determined. The complexity of the find() operation is O( h ) where h is the height of the tree. If the height remains below O(log n ), the operation is faster. However, the worst-case time is linear. This O( n ) time appears when each node (except the root) has only one predecessor.
   Example: ple: The root of vertex 8 in S1 in the last example is 1. However, the root of 8 in (S1 U S2) is 1 or 5 depending on how the union is done.

4. The program stores all the sets in a global array of nodes. Each node contains the value of the element and the index of its parent element. To make find() efficient, each node is connected directly to the root node. The function unionSets(i1, i2) take indices of root elements and makes i1 the parent of the root node pointed to by i2 . The function findSets(index) travels backwards from the node pointed to by the index until it reaches any of the root nodes. The root node has a parent index equal to –1.

Points to Remember

1. The function union() does not work if the sets are not disjointed.

2. Operations union() and find() were devised from specific applications that use symbol tables. This asks for a specific representation of data in the form of a tree with reversed links. This shows how closely algorithms and data structures are related .

3. union() has a complexily of O(1), while find() has the worst-case complexity of O( h ), where h is the height of the element in the tree.