3-Union-Find的树结构.doc

Union-Find的树结构前一个算法执行O(n)条Union和Find指令需要O(n*Logn)时间，是因为在合并的时候，小集合中每个元素i的所属集合名Ri要改名。Ri可使Find指令在O(1)时间里完成（优点），但使得Union指令所需工作量增大（主要用于Ri的改名）。因此，要降低Union的工作量，就必须大幅度减少改名的次数。其中的一种方法，是用树结构来表示集合：仅在树根处记录集合的名字。初始时每个结点是一棵单节点树, 作集合合并时, 让结点少的树A的根指向结点多的树B的根,(结点数相同时可选其中任一个根作为新的根)，这样就完成了集合的合并。故合并可以在O(1)时间里面完成。NameCountFather每个结点i的形式为Namei: 以结点i为根的子树原有的名称。但只有含结点i的树的根结点处的Name才是当前正确的集合名。Counti: 以结点i为根的子树中元素的个数。但只有含结点i的树的根结点处的Count才是当前集合正确的元素个数。Fatheri: 结点i的父结点的编号。结点i是根结点时，则该域为0。例如n=8，初始时为:111022108810另外，还有一个数组Root记录每个集合的根节点编号，初始时为112233445566778891011即Rootk: 集合名为k的树的根结点编号。e.g. 当执行Union(1,2,9)指令时，集合1和2合并, 重新命名为集合9，使2成为1 的父结点，则Name2、Count2、Father1和Root9均要修改如下：29201112Root1122334455667788921011此时，如再执行Union(9,3,10)指令，则根据Root9查到集合9的根结点编号为2，于是Name2改为10，Count2改为3（=2+1）, Father3 改为2（新的父结点编号），Root10中记入2。这样的处理，使得Union可以在O(1)时间里面完成，但Find时间增多，在最坏情况下，执行1条Find指令需要O(Logn)。于是执行O(n)条Union-Find指令仍需要O(n*Logn)。Find的时间能否改进？注意到：执行Findi指令时, 必然会形成一条从结点i到根的路径P, 如果我们让该路径P上的所有非根节点均指向根（路径压缩），这样下一次对该路径上的结点，再执行Find指令时，查找时间就会变短（因各结点已直接指向根节点）。采用一个功能与Aho书P132基本相同的算法（形式上要略简单）：假定集合名在1.n之间，且用树的高度代替树中的元素个数； 用原先深度大的集合的名字作为合并后的新集合的名字 （即不指定外部名），让树高值小的树的根，指向树高值大的树的根。 这样，Union不做各元素的所属集合改名，Find只与树的高度有关。该算法只用2个数组：Pi：若i为根结点,则Pi=i。若i不是根结点,则Pi是i的父结点的编号。ranki(秩)：在指令序列中删去Find指令, 得到只含Union指令的新序列,ranki是执行（即未经压缩）时，以结点i为根的子树的树高。（若在执行中有Find指令，则会对树进行压缩，所以ranki 结点i实际的深度。）带路径压缩的递归程序Find(i)：（注意：应尽可能避免使用全局变量，if ipi /*i不是根*/虽然此处为突出重点p不是入口参数）thenpiFind(pi);return pi;注意：Find操作既不改变树的大小（仅仅是将指针改一下），也不改变rank的值。但很有可能会改变树高。Union(i,j) /*i,j可以是任意结点，不一定是根结点*/aFind(i) /*a是含结点i的树的根结点编号*/bFind(j) /*b是含结点j的树的根结点编号*/if a=b return a; /*i,j在同一个集合中，无需进行Union */if rankarankb then pba; return a; /*根结点为a的树深，b指向a*/ else pab; /*根结点为b的树深或相等，a指向b*/if ranka=rankb then rankb增1; return b;/*注意，rank的改动只在：两rank相等时，新根结点rank才被增1*/结论1：ranki是不会减少的，当某次合并后i不再为根，则从此ranki就不再改变。(若以指令序号1,2,m作为x轴，则每个结点i的ranki函数图像是单调不减的阶梯函数)结论2：对所有不为根的结点的i（满足pii），都有rankpiranki（因合并时总是rank大的作根）。结论3：以i为根的集合中的元素个数2ranki （可以针对上述所给Union算法，用归纳法证明）结论4：a)至多有n/个秩（rank）为r的结点。b)没有一个结点的秩大于Log2n。（见Aho书上的引理4.2及其推论。）在Union算法中，除了2个Find以外，其余的工作量是O(1)。所以主要的工作量是花在Find指令的执行上。所以，根据平摊分析的聚集方法，O(n)条Unoin-Find指令的时间复杂度，主要取决于O(n)条Find指令（其余工作的总和只有O(n)）。其时间复杂度的分析与Ackerman函数有关。Ackerman函数（增长极快的函数）:F(i)=, F(0)=1, F(1)=2, F(2)=4, F(3)=16, F(4)=65536, F(5)=其广义逆函数G(r)= G(r)是增长极慢的函数。把秩r按照G(r)分组，秩r属于第G(r)组。（e.g: 秩为5则属于第3组）由结论4的b)，r Log2n。所以最大组号不超过G() G(n)-1，即最多有G(n)个组。定义N(g):其秩在组号为g的组中结点的个数。注意:组号为g的组中的秩是从F(g-1)+1到F(g)。由结论4 a) 秩为r的结点至多有n/个，故有N(g) =这样，执行一条Find(i0)指令，若pi0=i1，pi1=i2， ，pim-1=im， 而是im根，则执行路径压缩后，有pik=im (0km-1)。另外，由结论2（父结点的秩大于子结点的秩）有：ranki0 ranki1 ranki2ranki m-1 rankim用平摊分析的聚集方法，把O(n)条Find指令的耗费分为三类：1） O(n)条Find指令的根费用，2） O(n)条Find指令的组费用，3） O(n)条Find指令的路径费用。根费用：执行一条Find指令时，处理根及其儿子所需的费用。一条Find指令只会碰到一个根（及其儿子），故O(n)条Find指令的根费用为O(n)，这样，根及其儿子的费用已全部计算在内。非根（及其儿子）的结点只有两种可能性：1、该结点的秩与其父结点的秩不在同一个秩组中；2、该结点的秩与其父结点的秩在同一个秩组中。前者的费用计为组费用，后者的费用计为路径费用。组费用：若结点ik (0km-2)与其父结点ik+1的秩不在同一个秩组中， 则对ik收取一个组费用。因最多有G(n)个组，故一条Find指令最多只会碰到G(n)个结点、其秩与其父结点的秩不在同一个秩组中，每个点处理为常数时间，故O(n)条Find指令的组费用最多为O(n*G(n)。路径费用：若结点ik (0km-2)与其父结点ik+1的秩在同一个秩组中， 则对ik收取一个路径费用。O(n)条Find指令的路径费用不是按一条条的Find指令来计算的，而是按在执行O(n)条Find指令中，结点ik总共被收取了多少路径费用来计算的。在O(n)条Find指令（其间可能夹有Union指令）的执行中，考虑任一个被收取路径费用的结点，（此时该结点的秩与其父结点的秩必定在同一个秩组中，且该结点不是根结点的儿子，否则应收取根费用而不是路径费用，）每收取一次路径费用，Find指令将其变为根结点的儿子（路径压缩），从而其新父结点（根）的秩比其原父结点的秩至少高1。当某条Union指令将其新父结点作成其它某根结点的儿子，则对该结点又可以收取路径费用（只要该结点的秩与其当前父结点的秩仍在同一个秩组中，且下面的某条Find指令执行时经过该结点）。该结点（设该结点的秩在组g中）可以收取路径费用的次数最多为F(g)-(F(g-1)+1)。（因为每次收取路径费用时必然执行路径压缩，使得该结点的秩与其新父结点的秩差至少增1。）故路径费用最多收取F(g)-(F(g-1)+1) 次之后，其父结点的秩与该