《数据结构与算法树》由会员分享，可在线阅读，更多相关《数据结构与算法树（33页珍藏版）》请在金锄头文库上搜索。
1、一、哈夫曼树(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,一、哈夫曼树(15.1),哈夫曼树的构造方
2、法: (示范),假设通信所用的字符集合为: a, b, c, d, e, f, g, h 各自使用的频率为: 17, 2, 7, 5, 25, 11, 19,14,一、哈夫曼树(15.1),哈夫曼树的构造方法: (示范),一、哈夫曼树(15.1),哈夫曼树的构造方法: (示范),一、哈夫曼树(15.1),哈夫曼树的构造方法: (示范),一、哈夫曼树(15.1),哈夫曼树的构造方法: (示范),编码规则:左枝为0,右枝为1,编码结果: a:111 b:11010 c:1100 d:11011 e:01 f:100 g:00 h:101,一、哈夫曼树(15.1),哈夫曼树的构造方法: (示范),编
3、码结果: 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树(15.2) 续12章,定义: 每个结点的左右子树的层高差1(平衡),且满足二叉排序树的特征。 两个科学家的纪
4、念 前苏联 G.M.AdelSon-VelSkii & E.M.Landis (1962年) 平衡因子: 左右子树的层树差值。 =左子树层数 - 右子树层数,AVL树上的操作,二、AVL树(15.2),依次插入: (1)1,2,3,4,5 (2)20,10,30,80,40,60,50,70,AVL的ADT描述,二、AVL树(15.2),AVL的节点实现：,二、AVL树(15.2) 插入 (1 of 16),Case 1:,Case 2:,二、AVL树(15.2) 插入 (2 of 16),Case 3:,不平衡，需要调整,二、AVL树(15.2) R 旋转/右单旋 (3 of 16),-左子
5、树重: 插入到左子树外侧 /case 3,P-left =LC-right ;,LC-right= P ;,/ LC 成为根 ;,二、AVL树(15.2)R 旋转/右单旋 示范 (4 of 16),-左子树重:插入到左子树外侧 /case 3,插入 3,2,1,3,0,插入 5 (DIY),二、AVL树(15.2) L 旋转/左单旋 (5 of 16),P-right =LC-left ;,LC-left =P ;,/ LC 成为根 ;,-右子树重:插入到右子树外侧 /case 3,二、AVL树(15.2) L 旋转/左单旋 示范 (6 of 16),-右子树重:插入到右子树外侧 /case
6、3,插入 91,二、AVL树(15.2) R 双旋/右双旋(7 of 16),-左子树重:插入到左子树内侧/case 3,L 旋转(LC) R 旋转(P),右双旋,二、AVL树(15.2) L双旋/左双旋 (8 of 16),-右子树重:插入到右子树内侧 /case 3,R 旋转(LC) L 旋转(P),L 双旋,二、AVL树(15.2) R 双旋/右双旋L 旋转 (9 of 16),P,2,LC,-1,C,二、AVL树(15.2) R 双旋/右双旋R 旋转(11 of 16),二、AVL树(15.2) R 双旋/右双旋L 旋转(10 of 16),二、AVL树(15.2) R 双旋/右双旋R
7、 旋转(12 of 16),二、AVL树(15.2) L双旋/左双旋R 旋转(13 of 16),二、AVL树(15.2) L双旋/左双旋L 旋转(15 of 16),二、AVL树(15.2) L双旋/左双旋R 旋转(14 of 16),二、AVL树(15.2) L双旋/左双旋L 旋转 (16 of 16),三、其他树(15.3),2-3-4树：查找树，非叶子节点有2个、3个或者4个孩子。 2-3-4树的ADT p750,三、其他树(15.3),2-3-4树的查找 p751,2-3-4树的添加分裂 p752,三、其他树(15.3),红黑树的ADT p756,三、其他树(15.3),2-3-4树转换为红-黑树表示 P756,红-黑树的添加 P759,三、其他树(15.3),B-树的ADT p760,用作外部查找的数据类型 p760;2-3-4树为4阶B树,Whats next? Lets go,Thanks for your patience.,
