PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

沾悍其
5 years ago
Views:

1 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五国家级规划教材 )

2 A 第 6 章树 B C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用 D I E J F G H 树的顺序存储结构 K 叉树 2

3 父指针表示法只需要知道父结点的应用只需要保存一个指向其父结点的指针域, 称为父指针 (parent pointer) 表示法用数组存储树结点, 同时在每个结点中附设一个指针指示其父结点的位置 A B C D E F G H I J K L 结点索引值父结点索引 A B C D E F G H I J K L

4 父指针表示法 : 算法查询结点的根从一个结点出发找出一条向上延伸到达根的祖先路径 O(k),k 为树高判断两个结点是否在同一棵树两个结点根结点相同, 它们一定在同一棵树中如果其根结点不同, 那么两个结点就不在同一棵树中 4

5 并查集并查集是一种特殊的集合, 由一些不相交子集构成, 合并查集的基本操作是 : Find: 查询结点所在集合 Union: 归并两个集合并查集是重要的抽象数据类型应用于求解等价类等等问题 5

6 等价关系一个具有 n 个元素的集合 S, 另有一个定义在集合 S 上的 r 个关系的关系集合 R x,y,z 表示集合中的元素若关系 R 是一个等价关系, 当且仅当如下条件为真时成立 : (a) 对于所有的 x, 有 (x,x) R( 即关系是自反的 ) (b) 当且仅当 (x,y) R 时 (y,x) R( 即关系是对称的 ) (c) 若 (x,y) R 且 (y,z) R, 则有 (x,z) R( 即关系是传递的 ) 如果 (x,y) R, 则元素 x 和 y 是等价的 6

7 等价类 (equivalence classes) 等价类是指相互等价的元素所组成的最大集合所谓最大, 就是指不存在类以外的元素, 与类内部的元素等价由 x S 生成的一个 R 等价类 [x] R = {y y S xry} R 将 S 划分成为 r 个不相交的划分 S 1,S 2, S r, 这些集合的并为 S 7

8 用树来表示等价类的并查用一棵树代表一个集合集合用父结点代替 S 1 S 2 S (a) (b) (c) 8 8 若两个结点在同一棵树中, 则它们处于同一个集合树的实现存储在静态指针数组中结点中仅需保存父指针信息 8

9 UNION/FIND 算法示例 (1) 对这 5 个等价对进行处理 (A,B) (C,K) (J,F) (H,E) (D,G) A B C K D E (A,B)(C,K)(J,F)(E,H)(D,G) F G H J A C F E D 6 B K J H G 9

10 UNION/FIND 算法示例 (1) 然后对两个等价对 (K,A) 和 (E,G) 进行处理 A B C K D E K 所在树的根为 C,A 自己是根结点,A!=C, 所以两棵树要合并 F G H J (K,A) A B (E,G) D C F G E K J H 10

11 树的父指针表示与 Union/Find 算法实现 template<class T> class ParTreeNode { private: Tvalue; ParTreeNode<T>* parent; int ncount; public: ParTreeNode(); virtual ~ParTreeNode(){}; TgetValue(); void setvalue(const T& val); ParTreeNode<T>* getparent(); void setparent(partreenode<t>* par); int getcount(); void setcount(const int count); }; 11 // 树结点定义 // 结点的值 // 父结点指针 // 集合中总结点个数 // 构造函数 // 析构函数 // 返回结点的值 // 设置结点的值 // 返回父结点指针 // 设置父指针 // 返回结点数目 // 设置结点数目

12 树的父指针表示与 Union/Find 算法实现 template<class T> class ParTree { public: ParTreeNode<T>* array; }; int Size; ParTreeNode<T>* Find(ParTreeNode<T>* node) const; ParTree(const int size); virtual ~ParTree(); void Union(int i,int j); bool Different(int i,int j); // 树定义 // 存储树结点的数组 // 数组大小 // 查找 node 结点的根结点 // 构造函数 // 析构函数 // 把下标为 i,j 的结点合并成一棵子树 // 判定下标为 i,j 的结点是否在一棵树中 12

13 树的父指针表示与 Union/Find 算法实现 template <class T> ParTreeNode<T>* ParTree<T>::Find(ParTreeNode<T>* node) const { ParTreeNode<T>* pointer=node; while ( pointer->getparent()!= NULL ) pointer=pointer->getparent(); return pointer; } 13

14 树的父指针表示与 Union/Find 算法实现 template<class T> void ParTree<T>::Union(int i,int j) { ParTreeNode<T>* pointeri = Find(&array[i]); ParTreeNode<T>* pointerj = Find(&array[j]); if (pointeri!= pointerj) { if(pointeri->getcount() >= pointerj->getcount()) { pointerj->setparent(pointeri); pointeri->setcount(pointeri->getcount() + pointerj->getcount()); } else { pointeri->setparent(pointerj); pointerj->setcount(pointeri->getcount() + pointerj->getcount()); } } } // 找到结点 i 的根 // 找到结点 j 的根 14

15 UNION/FIND 算法示例 (2) 最后使用加权合并规则处理等价对 (H,J) H 所在树的根为 E, 而 J 的根结点依据加权合并规则为 F,E!=F,, 以所以两颗树要合并 F 为根的树结点个数少, 故将 F 指向 D (H,J) A D A B C K D E F G H J B C F G E K J H 15

16 查找 X 设 X 最终到达根 R 路径压缩顺着由 X 到 R 的路径把每个结点的父指针域均设置为直接指向 R A D B C F G K J E H 产生极浅树 16

17 UNION/FIND 算法示例 (3) 使用路径压缩规则处理 Find(H) A D A B C K D E F G H J B C F G E K J H 17

18 A D template <class T> 路径压缩 B C F G E H ParTreeNode<T>* ParTree<T>::FindPC(ParTreeNode<T>* node) const K J { if (node->getparent() == NULL) return node; node->setparent(findpc(node->getparent())); return node->getparent(); } 18

19 路径压缩使 Find 开销接近于常数权重 + 路径压缩对 n 个结点进行 n 次 Find 操作的开销为 O(nα(n)), 约为 Θ(nlog * n) α(n) 是单变量 Ackermann 函数的逆, 它是一个增长速度比 logn 慢得多但又不是常数的函数 log * n 是在 n = logn 1 之前要进行的对 n 取对数操作的次数 log * = 4(4 次 log 操作 ) Find 至多需要一系列 n 个 Find 操作的开销非常接近于 Θ(n) 在实际应用中,α(n) 往往小于 4 19

20 思考可否使用动态指针方式实现父指针表示法? 查阅各种并查集权重和路径压缩优化方法, 并讨论各种方法的异同和优劣 20

21 数据结构与算法谢谢聆听国家精品课数据结构与算法张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五国家级规划教材

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用