数据结构与算法分析树资料.ppt

三、其他树(15.3) B-树的ADT p760 B-树 ADT 数据元素集合： 满足以下性质的树： 1）每个节点最多放m-1个数据项； 2）每个非叶节点（根除外）是k度点，其中(m+1)/2≤k＜m； 3）所有叶子同一层 基本操作： 构造、判空、查找 添加：添加一项，并保持B-树 删除：删除一项，并保持B-树 用作外部查找的数据类型 p760;2-3-4树为4阶B树 What’s next? Let’s go… Thanks for your patience. * Chapter 1 Introduction * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? * 1: What is Data Structure ? 数据结构与算法分析-C++语言描述 （第二版） 2010.08 一、哈夫曼树(15.1)二、AVL树(15.2)三、其他树(2-3-4树、红-黑树、B-树和其他) (15.3) Start to Solve them! 第15章 树(第12章 继续) 哈夫曼树(huffman tree)/霍夫曼树: 也称最优树。保证构造的字符编码在进行通信时传输的信息量最小。--长度最短。 1952 D.A. Huffman 一、哈夫曼树(15.1) 哈夫曼树的构造方法: (示范) 假设通信所用的字符集合为: a, b, c, d, e, f, g, h 各自使用的频率为: 17, 2, 7, 5, 25, 11, 19,14 17 a 2 b 7 c 5 d 25 e 11 f 19 g 14 h V V 一、哈夫曼树(15.1) 哈夫曼树的构造方法: (示范) 假设通信所用的字符集合为: a, b, c, d, e, f, g, h 各自使用的频率为: 17, 2, 7, 5, 25, 11, 19,14 17 a 2 b 7 c 5 d 25 e 11 f 19 g 14 h 2 b 5 d 7 V V 17 a 25 e 11 f 19 g 14 h 7 c 2 b 5 d 7 14 V V 一、哈夫曼树(15.1) 哈夫曼树的构造方法: (示范) 17 a 25 e 19 g 7 c 2 b 5 d 7 14 11 f 14 h 25 7 c 2 b 5 d 7 14 17 a 31 25 e 19 g 11 f 14 h 25 V V V V 一、哈夫曼树(15.1) 哈夫曼树的构造方法: (示范) 7 c 2 b 5 d 7 14 17 a 31 11 f 14 h 25 25 e 19 g 44 一、哈夫曼树(15.1) 哈夫曼树的构造方法: (示范) 25 e 19 g 44 7 c 2 b 5 d 7 14 17 a 31 11 f 14 h 25 56 一、哈夫曼树(15.1) 哈夫曼树的构造方法: (示范) 编码规则:左枝为0,右枝为1 编码结果: a:111 b:11010 c:1100 d:11011 e:01 f:100 g:00 h:101 25 e 19 g 44 7 c 2 b 5 d 7 14 17 a 31 11 f 14 h 25 56 100 一、哈夫曼树(15.1) 哈夫曼树的构造方法: (示范) 编码结果: a:111 b:11010 c:1100 d:11011 e:01 f:100 g:00 h:101 假设通信所用的字符集合为: a, b, c, d, e, f, g, h 各自使用的频率为: 17, 2, 7, 5, 25, 11, 19,14 (保证构造的字符编码在进行通信时传输的信息量最小。) 结论: 非前缀码(简单的证明：从根到叶子的路径唯一),立刻可解码性,解码算法P734 可以保证码传输长度最小 构造过程中使用优先队列 平衡的二叉排序树AVL(P) 二、AVL树