第八章集合与搜索 并查集 静态搜索表 二叉搜索树 AVL树
1 ◼ 并查集 ◼ 静态搜索表 ◼ 二叉搜索树 ◼ AVL树
并查集( Union- Find sets 并查集支持以下三种操作: ◆ Union(Root1,Root2)/合并操作 ◆Find(x) 搜索操作 ◆ InituFSets(s)/初始化操作 对于并查集来说,每个集合用一棵树表示。 为此,采用树的双亲表示作为集合存储表示。 集合元素的编号从0到n-1。其中n是最大 元素个数
2 并查集 (Union-Find Sets) ◼ 并查集支持以下三种操作： ◆ Union (Root1, Root2) //合并操作 ◆ Find (x) //搜索操作 ◆ InitUFSets (s ) //初始化操作 ◼ 对于并查集来说，每个集合用一棵树表示。 ◼ 为此，采用树的双亲表示作为集合存储表示。 集合元素的编号从0到n-1。其中 n 是最大 元素个数
在双亲表示中,第i个数组元素代表包含 集合元素i的树结点。初始时,根结点的 双亲为-1,表示集合中的元素个数。 在同一棵树上所有结点所代表的集合元素 在同一个子集合中。 n为此,需要有两个映射: ◆集合元素到存放该元素名的树结点间的 对应; ◆集合名到表示该集合的树的根结点间的 对应
3 ◼ 在双亲表示中，第 i 个数组元素代表包含 集合元素 i 的树结点。初始时, 根结点的 双亲为-1，表示集合中的元素个数。 ◼ 在同一棵树上所有结点所代表的集合元素 在同一个子集合中。 ◼ 为此，需要有两个映射： ◆ 集合元素到存放该元素名的树结点间的 对应； ◆ 集合名到表示该集合的树的根结点间的 对应
设S1={0,6,7,8},S2={1,4,9},S3={2,3, 5} 集合名指针 0|S 123 2 S ⑥⑦③①⑨③⑤ 为简化讨论,忽略实际的集合名,仅用表 示集合的树的根来标识集合
4 ◼ 设 S1= {0, 6, 7, 8 }, S2= { 1, 4, 9 }, S3= { 2, 3, 5 } 集合名 指针 0 S1 1 S2 2 S3 0 4 2 6 7 8 1 9 3 5 ◼ 为简化讨论，忽略实际的集合名，仅用表 示集合的树的根来标识集合
初始时, InitUFSets(S)构造一个森林,每棵 树只有一个结点,表示集合中各元素自成 个子集合S[i=-1,i=0,1,…,n-1。 用Find(S,i)寻找集合元素i的根。 a如果有两个集合元素i和j Find(s, i)==Find(s,D 表明这两个元素在同一个集合中 a如果两个集合元素i和j不在同一个集合 中可用Unon(S,i,j将它们合并到一个集 合中
5 ◼ 初始时, InitUFSets(S) 构造一个森林, 每棵 树只有一个结点, 表示集合中各元素自成一 个子集合 S[i] = -1, i = 0, 1, …, n-1。 ◼ 用 Find(S, i) 寻找集合元素 i 的根。 ◼ 如果有两个集合元素 i 和 j: Find(S, i) == Find(S, j) 表明这两个元素在同一个集合中， ◼ 如果两个集合元素 i 和 j 不在同一个集合 中,可用 Union(S, i, j) 将它们合并到一个集 合中
下标0123456789 parent-44-32-320004 集合S1,S2和S3的双亲表示 ② 6⑦8①⑨③⑤
6 S1 下标 parent 集合 S1 , S2 和 S3 的双亲表示 -4 4 -3 2 -3 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 6 7 8 4 1 9 2 3 5 S2 S3
下标0123456789 parent-74|-32020004 合S1∪S,和S3的双亲表示 6⑦⑧④ S1∪S2的可能的表示方法
7 S1 S2的可能的表示方法 下标 parent 集合 S1 S2和 S3的双亲表示 -7 4 -3 2 0 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 6 7 8 4 1 9 4 0 1 9 6 7 8
并查集的结构定义 const int setsize=50;并查集元素个数 typedef struct i )并查集结构定义 int parent[ Setsize;/合元素数组 3 UFSets; void InitufSets( UFSets*S){∥集合初始化 for( int i=0; iparent[1=-1 //每一个自成一个单元素集合
8 并查集的结构定义 const int SetSize = 50; //并查集元素个数 typedef struct { //并查集结构定义 int parent[SetSize]; //集合元素数组 } UFSets; void InitUFSets (UFSets *S) { //集合初始化 for ( int i = 0; i parent[i] = -1; } //每一个自成一个单元素集合
A并查集操作的算法 查找 5 0 ((23 Find(s, 4) Find (s, 3)=3 Find(s, 2)=2 Find(s,1)=1 Find(s, 0)=0 5<0结束
9 并查集操作的算法 ◼ 查找 -5 0 1 2 3 0 1 2 3 4 Find (S,4) Find (S,3) = 3 Find (S,2) =2 Find (S,1) = 1 Find (S,0) = 0 = -5 < 0 结束
0 2 3 parent 50123 Parent!0l Parent] 5 Parent[1] Parent(3=3 =0 Parent2=2 int Find(UFSets *S, int x)& if(s->parent [x]parent [x]);
10 int Find (UFSets * S, int x ) { if ( S->parent [x] parent [x] ); } parent -5 0 1 2 3 Parent[4] Parent[3] =3 Parent[2] =2 =1 Parent[1] =0 Parent[0] =-5 0 1 2 3 4