CHAPTER 8
The Disjoint Set Class
8.1 We assume that unions operated on the roots of the trees containing the arguments. Also, in case of ties, the
second tree is made a child of the first. Arbitrary union and union by height give the same answer (shown as
the first tree) for this problem. Union by size gives the second tree.
8.3 Below are some typical results with sets of size 500 and 300 unions :
Method Average Max Heights
No Compress Random Union 17.931
#include <vector>
#include <iostream>
#include <cmath>
#include <ctime>
class DisjSets
{
private:
vector<int> set;
public:
DisjSets(int size) : set(size, –1)
if ( set[x] < 0)
return x;
else
return set[x] = findCompress(set[x]);
}
void unionSets(int root1, int root2)
{
set[root2] = root1;
}
else
{
set[root2] += set[root1];
set[root1] = root2;
}
}
max = height(i);
return max;
}
int height(int x)
{
if (set[x] < 0)
return 0;
};
int main()
{
int heightNoRand=0;
int heightNoSize=0;
int heightNoRank=0;
int heightCompRand=0;
int heightCompSize=0;
int heightCompRank=0;
int x, y, one, two;
//srand(time(NULL));
for (int i = 0; i < NUM_ITERS; i++)
{
x = rand()%MAXSET;
y = rand()%MAXSET;
one = noCompressRandUnion.find(x);
two = noCompressRandUnion.find(y);
if (one != two)
{
noCompressRandUnion.unionSets(one, two);
one = noCompressUnionSize.find(x);
one = compressRandUnion.findCompress(x);
two = compressRandUnion.findCompress(y);
compressRandUnion.unionSets(one,two);
}// for
heightNoRand += noCompressRandUnion.maxHeight();
heightNoSize += noCompressUnionSize.maxHeight();
cout<<“No Compress Union by Size \t”<<heightNoSize/(float)NUM_ITERS<<endl;
8.4 Claim: A tree of height h has at least 2h nodes. The proof is by induction. A tree of height 0 clearly has at
least 1 node, and a tree of height 1 clearly has at least 2. Let T be the tree of height h with fewest nodes. Thus
8.5 We are given T(n) = n/f(n) * T(f(n)) + n
First, we expand T(f(n)) using the definition of T(n) itself:
T(f(n)) = f(n)/f(f(n)) * T(f(f(n))) + n
and then substitute this expression for T(f(f(n))) into the most recent formula we have for T(n).
T(n) = n/f(f(n)) * [ f(f(n))/f(f(f(n))) * T(f(f(f(n)))) + n ] + n2/f(n) + n
and let’s substitute into the most recent formula for T.
T(n) = n/f(f(f(n))) * [ f(f(f(n)))/f(f(f(f(n)))) * T(f(f(f(f(n))))) + n] + n2/f(f(n)) + n2/f(n) + n
8.9 Run the normal algorithm; never remove the prespecified wall. Let s1 and s2 be squares on the opposite side
8.10 (a) When we perform a union we push onto a stack the two roots and the old values of their parents. To
8.11 We assume that the tree is implemented with links instead of a simple array. Thus find will return a reference
instead of an actual set name. We will keep an array to map set numbers to their tree nodes. union and find
8.12 Suppose there are u union and f find operations. Each union costs constant time, for a total of u. A find costs
one unit per vertex visited. We charge, as in the text, under the following slightly modified rules:
8.14 For each vertex v, let the pseudorank Rv be defined as
log v
S
, where Sv is the number of descendents
(including itself) of v in the final tree, after all union operations are performed, ignoring path compression.
Although the pseudorank is not maintained by the algorithm, it is not hard to show that the pseudorank
8.15
/*
Builds a maze
The maze is a 2 dimensional array of rooms
_ _ _ _ _ _ _ _ _ _ _ _ _ _
| | | | | | |
_ _ _ _ _
| | | | | | | | |
*/
#include <iostream>
#include <vector>
#include <time.h>// initialize the random number generator
struct Room
{
bool top; // if true top is present
bool left;// if true left side is present
};
class Maze
{
private:
public:
Maze(int rows= 0, int cols=0) : numRows(rows), numCols(cols)
{ Room room;
room.top = true;
room.left = true;
rooms.resize(numRows+1);
for (int i = 0; i < numRows+1; i++)
rooms[i].resize(numCols+1, room);
connect.initialize(numRows*numCols);
bool removeWall(int row, int col, bool wall) // 0 for top, 1 for side
// returns true if all rooms are connected
rooms[row][col].top = false;
connect.unionSetsSize(room1Root, room2Root);
}
}// end remove a top
if (wall && (!rooms[row][col].left || col== 0))
// try to romove top (already removed)
return false;
else if (wall && col!=0 && rooms[row][col].left )
{
}
}// end remove a left wall
return connect.allDone();
}
void printMaze()
{
for (int i = 0; i < numRows+1; i++)
{
for (int j = 0; j < numCols+1; j++)
if (rooms[i][j].top)
cin>>numRows>>numCols;
Maze maze(numRows,numCols);
}
8.16 This is most conveniently implemented without recursion and is faster because, even if full path
compression is implemented nonrecursively, it requires two passes up the tree. This requires only one. We leave the