一 基本运算：
数据结构：将一个集合划分为两个子集，这两个子集没有相同元素则可称之为不相交集。每个集合选出一个代表元素来表示这个集合。可以用树结构表示，根节点为该集合的代表元素。
当数据为由1....n的连续数字时，这棵树可以用一个长度为n的数组存储，用数组索引表示数据，用数组内容表示父节点，比如A[1]=3表示1的根节点为3。
按秩合并：
初始每个结点秩为0,用rank(x)表示根节点x的秩，使用UNION(x,y)
rank(x)<rank(y):将节点x附到节点y上(将x的父节点改为y，改一下数组的指向即可)。
rank(x)>rank(y):同上。
rank(x)=rank(y):将结点x附到结点y上，并将rank(y)增加1。
路径压缩：
在进行路径压缩时，不会改变节点的秩，但会改变节点的高度（高度减小），故秩为结点高度的一个上界。
二 一些题目
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高度的上界。
