按树高度合并 高度高的树的根结点作根 3 5 (-0 0 0)(-0 0 0 0 2 0 Union(2,0)2 2 3 5 3 2 0 2 2 5 3 3 3 263 0 16
16 ◼ 按树高度合并 ➢ 高度高的树的根结点作根 -0 -0 -0 -0 -0 0 1 2 3 4 -0 -0 0 -2 2 5 6 -2 -1 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 6 5 2 1 3 4 Union(2, 0)
Union操作的折叠规则 为进一步改进树的性能,可以使用如下折叠 规则来“压缩路径”。即:如果j是从i到 根root的路径上的一个结点,且S > parenti!= root[jl,则把S-> parentI置 为 roti 6 8哪(⑦⑨((8 3 从i=5压缩路径 3)(5 17
17 Union操作的折叠规则 ◼ 为进一步改进树的性能，可以使用如下折叠 规则来“压缩路径” 。即： 如果 j 是从 i 到 根 root 的 路 径 上 的 一 个 结 点 ， 且 S- >parent[j] != root[j]， 则把 S->parent[j] 置 为 root[i]。 0 0 6 7 8 6 7 8 1 9 1 9 3 5 3 5 从 i = 5 压缩路径
int Collapsing Find (UFSets *S, int i)i 使用折叠规则的搜索算法 nt J while(s->parent[]>=0) j=S-> parental; ∥}j循双亲指针走到根 while(i!=j){/换 parent到j int temp=S->parent[i; v S->parenti=j; i=temp; return ];
18 int CollapsingFind (UFSets *S, int i ) { //使用折叠规则的搜索算法 int j = i; while ( S->parent[j] >= 0 ) j = S->parent[j]; //让 j 循双亲指针走到根 while ( i != j ) { //换 parent[i] 到 j int temp = S->parent[i]; S->parent[i] = j; i = temp; } return j; }
静态搜索表 搜索( Search)的概念 所谓搜索,就是在数据集合中寻找满足某 种条件的数据对象。 搜索的结果通常有两种可能 ◆搜索成功,即找到满足条件的数据对象 这时作为结果,可报告该对象在结构中 的位置,还可给出该对象中的具体信息。 ◆搜索不成功,或搜索失败。作为结果 应报告一些信息,如失败标志、位置等
19 搜索(Search)的概念 静态搜索表 ◼ 所谓搜索，就是在数据集合中寻找满足某 ◼ 种条件的数据对象。 ◼ 搜索的结果通常有两种可能： ◆ 搜索成功，即找到满足条件的数据对象 这时,作为结果, 可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。 ◆ 搜索不成功，或搜索失败。作为结果, 应报告一些信息, 如失败标志、位置等
通常称用于搜索的数据集合为搜索结构 它是由同一数据类型的对象(或记录)组成。 在每个对象中有若干属性,其中有一个属 性,其值可唯一地标识这个对象。称为关 键码。使用基于关键码的搜索,搜索结果 应是唯一的。但在实际应用时,搜索条件 是多方面的,可以使用基于属性的搜索方 法,但搜索结果可能不唯 20
20 ◼ 通常称用于搜索的数据集合为搜索结构， 它是由同一数据类型的对象(或记录)组成。 ◼ 在每个对象中有若干属性，其中有一个属 性，其值可唯一地标识这个对象。称为关 键码。使用基于关键码的搜索，搜索结果 应是唯一的。但在实际应用时，搜索条件 是多方面的，可以使用基于属性的搜索方 法，但搜索结果可能不唯一