# 编写一个程序来确定路径压缩法和各种求并方法的效果。你的程序应该使用六种可能的方法处理一系列等价操作。

题意是叫你实现 2 种 find 操作和 3 种 union 操作，常规任意并查集初始化为 0，但灵巧求并算法的初始化为 - 1。测试数据可以用书上习题 8.1 的，还挺有用的。

void DisjSet_Init_0(DisjSet S)

{

    for(int i = NumSets; i > 0; i--)

      S[i] = 0;

}

// it apply in DisjSet_Union_Size() and DisjSet_Union_Height()

void DisjSet_Init_1(DisjSet S)

{

    for(int i = NumSets; i > 0;i--)

      S[i] = -1;

}

// Assume that Root1 and Root2 are roots

// union is a C keyword, so this routine

// is name DisjSet_Union

void DisjSet_Union(DisjSet S,SetType Root1,SetType Root2)

{

    S[Root2] = Root1;

}

// Assume that Root1 and Root2 are roots

// big size root will be attached to small size root  

void DisjSet_Union_Size(DisjSet S,SetType Root1,SetType Root2)

{

    if(S[Root1]<S[Root2])

    {

        S[Root1] += S[Root2];

        S[Root2] = Root1;

    }

    else

    {

        S[Root2] += S[Root1];

        S[Root1] = Root2;

    }

}

// Assume that Root1 and Root2 are roots

// low height Root will be attached to high height Root

// if Root1's height and Root2's height are same, Root1 will be attached to Root2

void DisjSet_Union_Height(DisjSet S,SetType Root1,SetType Root2)

{

    if(S[Root2]<S[Root1])//Root2 is deeper Set

      S[Root1] = Root2; //Make Root2 new root 

    else

    {

        if(S[Root1]==S[Root2]) //Same height

           S[Root1]--; //Update Height

        S[Root2] = Root1;

    }

}

// just find the root node of x, do nothing

SetType DisjSet_Find(DisjSet_ElementType X,DisjSet S)

{

    if(S[X]<=0) return X;

    else return DisjSet_Find(S[X],S);

}

// find the root of x and 

// The parent node of each node passed from x becomes the root node

SetType DisjSet_Find_Path(DisjSet_ElementType X,DisjSet S)

{

    if(S[X]<=0) return X;

    else return S[X]=DisjSet_Find_Path(S[X],S);

}

# 证明，如果 Union 按照高度进行，那么任意一棵树的深度则为$O(\log{}{N})$

假设高度为 H 并查集节点数为$2^H$。
由归纳假设得高度为 0，节点数为 1；高度为 1，节点数为 4
那么假设高度为 H，最少节点数为 T，若最后一轮合并时，则$T=2^{H-1}$。
若小于$T=2^{H-1}$，假设不成立，所以 N 个节点的树高度为$\log{}{N}$，且$N=2^H$。

# 习题 8.5

1. 证明如果$M=N^2$，那么 M 次 Union/Find 操作的运行时间是 O (M)。
2. 证明如果$M=N\log{}{N}$，那么 M 次 Union/Find 操作的运行时间是 O (M)。
3. 设$M=\Theta(N\log{}{\log{}{N}})$，则 M 次 Union/Find 操作的运行时间是多少？
4. 设$M=\Theta(N\log{}{*N})$，则 M 次 Union/Find 操作的运行时间是多少？

全是 O (M), 由定理 8.3:M 次 Union/Find 操作的运行时间是$O(M\log{}{*N})$ 可得$\log{}{*N}$ 远远小于 1，所以运行时间为 O (M)。

# 假设我们想要添加一个附加的操作 Deunion，它废除尚未被废除的最后的 Union 操作。

1. 证明：如果我们按高度求并以及不用路径压缩进行 Find，那么 Deunion 操作容易进行并且连续 M 次 Union，Find 和 Deuion 操作花费$O(M\log{}{N})$ 时间
2. 为什么路径压缩使得 Deunion 很难进行？

假设由节点 N 组成的并查集，Union 运行时间为 O (M)，Find 在并查集运行时间和二叉树查找一眼为$O(\log{}{N})$，而 Deuion 操作只运行常数时间即 O (1),
所以总的运行时间为$M*(\log{}{N}+1)$, 即$O(M\log{}{N})$。若使用路径压缩，则破坏了树原来的结构，难以分析和实现。

# 假设我们想要添加一种额外的操作 Remove（X），该操作把 X 从当前的集合中除去并把它放到它自己的集合中。指出如何修改 Union/Find 算法使得连续 M 次 Union，Find，和 Remove 操作的运行时间为$O(M\alpha(M,N))$.

同样假设由 N 个节点，Union 运行时间为$O(M)$，Remove 和 Find 的运行时间是一样的$O(log{}{N})$，但使用 M 次 Remove 操作后会造成失衡，需要额外做一次 Find 操作，又需要$O(M)$ 次操作，则 Remove 和 Find 的总运行时间为$O(\alpha(M,N))$，那么总共需要$O(M\alpha(M,N))$。

# 证明，如臬所有的 Union 都在 Find 之前，那么使用路径压缩的不相交集算法需要线性时间，即使 Union 是任意进行的也是如此。

假设由$u$ 次 Union 和$f$ 次 Find，$u$ 次 Union (不论那种类型) 会使根节点和非根节点增加$u$ 个，对于 Find，则在原先的基础上加$u$，即$f+u$，因为总共需要执行两次 Find，所以总运行时间为$O(2f+2u)$。

# 证明，如果 Union 按大小进行且执行路径压缩，那么最坏情形运行时间为$O(M\log{}{*N})$。

对于每个点 v, 让秩$R_v=\log{}{S_v}$, 其中$S_v$ 是最终合并树的节点数。
由引理 8.1：当执行一系列 Union 指令时，一个秩为$r$ 的节点必然至少$2^r$ 个后裔 (包括它自己) 可知秩为$R_v$ 的树节点数至少为$2^{R_v}$。
又由引理 8.2: 秩为$r$ 的节点的个数最多是$N/2^r$ 可得$R=N/2^R$。
又由于会计诀窍和定理 8.3:M 次 Union/Find 操作的运行时间是$O(M\log{}{*N})$ 可知无论何种 Find 和 Union，其最坏情形都是$O(M\log{}{*N})$，证毕。

# 设我们通过使在从 i 到根的路径上的每一个节点指向它的祖父 (当有意义时) 以实现对 Find (i) 的偏路径压缩 (partial path compression). 这叫做路径评分 (path halving)。

1. 编写一个过程完成上述工作
2. 证明，如果对诸 Find 操作进行路径平分，则不论使用按高度求并还是按大小求并，其最坏情形运行时间皆为$O(M\log{}{*N})$。

// find the root of x and 

// Every node from x to the root points to its grandparent

// note: I haven't actually tested this function

SetType DisjSet_Find_Path_Halving(DisjSet_ElementType X,DisjSet S)

{

    while(S[X]>0&&S[S[X]]>0)

    {

        S[X] = S[S[X]];

        X = S[X];

    }

    if(S[X]>0) //if S[X] is the child of the root

      X = S[X];

    return X;

}

第二题的证明同上一题证明一致。