一 基本运算：
按秩合并：
? ? ? ? 初始每个结点秩为0
路径压缩：
????????
????????在进行路径压缩时，不会改变节点的秩，但会改变节点的高度（高度减小），故秩为结点高度的一个上界。
?
二 一些题目
1.给出一个有n个合并和寻找运算（仅按秩合并）的序列，使得{1,2,...n}构成一个高度为的树。
? ? ? ? ?一开始我想通过按秩合并构成一棵完全二叉树，但这完全不可行。实际上不需要如此也可以让树高为。用归纳的思想：
? ? ? ? 若两棵树均由按秩合并获得且完全相同，高度为h，节点数量为n，。将这两棵树合并，则新树满足
，仍满足题意。而开始时，所有树只有一个节点，显然满足要求。故秩序保证，每次进行按秩合并的两棵树相同即可。流程如下：
? ? ? ? 1：UNION(2*i,2*i-1)? ? i=1,2,3....n/2
? ? ? ? 2：按根节点重新设置序号
? ? ? ? 3：n = n/2
? ? ? ? 4：若n大于1则返回1，否则结束。
? ? ? ? 实际上就是按以下规则合并:
? ? ? ? 第一轮：UNION(2*i,2*i-1)
? ? ? ? 第二轮：UNION(4*i,4*i-2)
? ? ? ? 第三轮：UNION(8*i,8*i-4)
? ? ? ? ··········
? ? ? ? 共有轮
2.T为用按秩合并和路径压缩的合并和寻找运算序列得到的树，x是T中的一结点，证明rank(x)为x高度的上界。
?
?
?