资源描述：
《3-union-find树结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Union-Find的树结构前一个算法执行O(n)条Union和Find指令需要O(n*Logn)时间，是因为在合并的时候，小集合中每个元素i的所属集合名R[i]要改名。R[i]可使Find指令在O(1)时间里完成（优点），但使得Union指令所需工作量增大（主要用于R[i]的改名）。因此，要降低Union的工作量，就必须大幅度减少改名的次数。其中的一种方法，是用树结构来表示集合：仅在树根处记录集合的名字。初始时每个结点是一棵单节点树,作集合合并时,让结点少的树A的根指向结点多的树B的根,(结点数相同时可选其中任一个根作为新的根)，这样就完
2、成了集合的合并。故合并可以在O(1)时间里面完成。NameCountFather每个结点i的形式为Name[i]:以结点i为根的子树原有的名称。但只有含结点i的树的根结点处的Name才是当前正确的集合名。Count[i]:以结点i为根的子树中元素的个数。但只有含结点i的树的根结点处的Count才是当前集合正确的元素个数。Father[i]:结点i的父结点的编号。结点i是根结点时，则该域为0。例如n=8，初始时为:11102210……8810另外，还有一个数组Root记录每个集合的根节点编号，初始时为112233445566778891011
3、即Root[k]:集合名为k的树的根结点编号。e.g.当执行Union(1,2,9)指令时，集合1和2合并,重新命名为集合9，使2成为1的父结点，则Name[2]、Count[2]、Father[1]和Root[9]均要修改如下：29201112Root1122334455667788921011此时，如再执行Union(9,3,10)指令，则根据Root[9]查到集合9的根结点编号为2，于是Name[2]改为10，Count[2]改为3（=2+1）,Father[3]改为2（新的父结点编号），Root[10]中记入2。这样的处理，使得Un
4、ion可以在O(1)时间里面完成，但Find时间增多，在最坏情况下，执行1条Find指令需要O(Logn)。于是执行O(n)条Union-Find指令仍需要O(n*Logn)。Find的时间能否改进？注意到：执行Find[i]指令时,必然会形成一条从结点i到根的路径P,如果我们让该路径P上的所有非根节点均指向根（路径压缩），这样下一次对该路径上的结点，再执行Find指令时，查找时间就会变短（因各结点已直接指向根节点）。采用一个功能与Aho书P132基本相同的算法（形式上要略简单）：假定集合名在1..n之间，且用树的高度代替树中的元素个数；用
5、原先深度大的集合的名字作为合并后的新集合的名字（即不指定外部名），让树高值小的树的根，指向树高值大的树的根。这样，Union不做各元素的所属集合改名，Find只与树的高度有关。该算法只用2个数组：P[i]：若i为根结点,则P[i]=i。若i不是根结点,则P[i]是i的父结点的编号。rank[i](秩)：在指令序列中删去Find指令,得到只含Union指令的新序列,rank[i]是执行（即未经压缩）时，以结点i为根的子树的树高。（若在执行中有Find指令，则会对树进行压缩，所以rank[i]结点i实际的深度。）带路径压缩的递归程序Find(i
6、)：（注意：应尽可能避免使用全局变量，ifip[i]/*i不是根*/虽然此处为突出重点p不是入口参数）thenp[i]Find(p[i]);returnp[i];注意：Find操作既不改变树的大小（仅仅是将指针改一下），也不改变rank的值。但很有可能会改变树高。Union(i,j)/*i,j可以是任意结点，不一定是根结点*/aFind(i)/*a是含结点i的树的根结点编号*/bFind(j)/*b是含结点j的树的根结点编号*/ifa=breturna;/*i,j在同一个集合中，无需进行Union*/ifrank[a]>rank[b]the
7、n{p[b]a;returna;}/*根结点为a的树‘深’，b指向a*/else{p[a]b;/*根结点为b的树‘深’或相等，a指向b*/ifrank[a]=rank[b]thenrank[b]增1;returnb;}/*注意，rank的改动只在：两rank相等时，新根结点rank才被增1*/结论1：rank[i]是不会减少的，当某次合并后i不再为根，则从此rank[i]就不再改变。(若以指令序号{1,2,…m}作为x轴，则每个结点i的rank[i]函数图像是单调不减的阶梯函数)结论2：对所有不为根的结点的i（满足p[i]i），都有rank
8、[p[i]]>rank[i]（因合并时总是rank大的作根）。结论3：以i为根的集合中的元素个数2rank[i]（可以针对上述所给Union算法，用归纳法证明）结论4：a)至多有
