Huffman树、二叉排序树

1、Huffman树、二叉排序树树、二叉排序树 胡俊峰 2016/04/8 2今天的内容今天的内容 Huffman树 二叉排序树简介3建立建立n个元素的堆？个元素的堆？ 从0开始，不断插入堆：O(nlogn) 4有没有更好（高效率）的方法？有没有更好（高效率）的方法？012345678910115哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树 哈夫曼算法 哈夫曼编码6Huffman树与最优编码树与最优编码 信息与编码 扩充二叉树与最优编码 Huffman树7扩充二叉树的概念扩充二叉树的概念把原二叉树的结点都变为度数为2的分支结点如果原结点的度数为2，则不变度数为1，则增加一个分支，度数为0（树叶），则

2、增加两个分支。空二叉树的扩充二叉树规定为只有一个外部结点组成的二叉树。德智5体77018内部节点YNYYNN1008概率加权、前缀编码、加权平衡二叉树概率加权、前缀编码、加权平衡二叉树 wi是第i个外部结点的权值 li为从根到第i个外部结点的路径长度 m为外部结点的个数。 WPL = 1 x 5 + 2 x 70 + 3 x 18 + 3 x 7 = 5 + 140 + 54 + 21 = 220 德智5体77018内部节点YNYYNN100miiilwWPL1外部路径外部路径1000119外部路径与加权外部路径外部路径与加权外部路径“外部路径长度” E:在扩充的二叉树里从根到每个外部结点的路

3、径长度之和。其中，li为从根到第i个外部结点的路径长度，m为外部结点的个数。设扩充二叉树具有m个带权值的外部结点，那么从根结点到各个外部结点的路径长度与相应结点权值的乘积的和，叫做扩充二叉树的带权的外部路径长度。其中，wi是第i个外部结点的权值，li为从根到第i个外部结点的路径长度，m为外部结点的个数。miilE1miiilwWPL110哈夫曼树：哈夫曼树：对于一组非负实数w1 , w2 , w3 , wm，存在一棵以wi（i = 1,2,，m）为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度WPL最小。这棵二叉树就称为哈夫哈夫曼树曼树或最优二叉树最优二叉树。WPL = 1 x 70

4、+ 2 x 18 + 3 x 5 + 3 x 7 = 70 + 36 + 15 +21 = 142智体70德7185内部节点YNYYNN10011哈夫曼树（构建算法）哈夫曼树（构建算法）给定m个权值 w1 , w2 , wm （叶子）构造由m棵二叉树组成的树林F = T1,T2,Tm，其中每棵树Ti 只有一个根结点，且根结点的权值为wi；在树林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。将新的二叉树加入到树林F中，去除原两棵权值最小的树；重复2、3步骤，直至F中只剩一棵树为止。12给定权值给定权值 7，5，2，4，构造哈夫曼树

5、，构造哈夫曼树abcd7524(a)675cd(b)11b57cd(c)6a 711cdb5624(d)1813信息量：信息量： 14哈夫曼编码：哈夫曼编码：在概率意义上平均码长最短在概率意义上平均码长最短 互不为子串1452208010050655001101 (hot,50), (warm,65),(mild,120), (cold,80), (very cold,50)120103650hot111warm01mild10cold00very cold11015哈夫曼树的存储实现哈夫曼树的存储实现 存储结构可以有多种，如二叉链表、三叉链表等。下面给出一种顺序结构(一维数组），结点结构：

6、ww: 以该结点为根的子树中所有外部结点的加权和。 parent: 父结点在数组中的存储位置（下标），根无父，设为-1。 llink: 左孩子存储位置，对于外部结点，无孩子，设为-1。 rlink: 右孩子存储位置，对于外部结点，无孩子，设为-1。wwparentllinkrlink16在线性结构上实现哈夫曼树在线性结构上实现哈夫曼树struct HtNode /* 哈夫曼树结点的结构 int ww; int parent, llink, rlink;哈夫曼树可定义为： struct HtTree struct HtNode htMAXNODE; int root；/* 树根在数组中的下标*/

7、;typedef struct HtTree *PHtTree;17哈夫曼算法（初始化）哈夫曼算法（初始化）18哈夫曼算法（构造树）哈夫曼算法（构造树）思考：如果用堆结构实现huffman算法有没有问题？19使用优先队列20二叉排序树（又称二叉搜索树）二叉排序树（又称二叉搜索树） 以关键码值关键码值为结点的二叉树 如果任一结点的左子树非空，则左子树中的所有结点的关键码都小于根结点的关键码； 如果任一结点的右子树非空，则右子树中的所有结点的关键码都大于根结点的关键码。 10152040 6 2 815302521最佳二叉排序树（续）最佳二叉排序树（续） 在扩充二叉排序树里，检索一个关键码的平均比

8、平均比较次数较次数为： 检索中平均比较次数最小，即E(n)最小的二叉排序树称作最佳二叉排序树最佳二叉排序树。niniiiiilqlpwnE10) 1(1)(22最佳二叉排序树的构造最佳二叉排序树的构造 对于K=27,73,10,5,18,41,99,51,25，构造最佳二叉排序树的过程如下：首先将它们排序为：5，10，18，25，27，41，51，73，99，然后从空二叉树出发，在排序的关键码序列中用二分法检索5，检索中遇到的结点为27,10,5，将这三个结点插入二叉排序树。再检索第二个结点10，遇到的结点为27,10，二叉排序树中已经有这两个结点。再检索第三个结点18，。得到的插入次序为27

9、，10，5，18，25，51，41，73，99。2324平衡二叉排序树平衡二叉排序树 以上的“最佳”二叉排序树，不仅构造的时间代价很大，而且很难动态的保持。通常用于表示一旦构造后就不改动的静态字典静态字典； 对于动态字典动态字典，为了能够在进行元素的插入和删除操作时，较快地对二叉排序树进行调整，通常不要求二叉排序树总是保持“最佳的”检索效率，而是希望达到一种比较容易调整的“较佳”的状态。25平衡二叉排序树，平衡二叉排序树， 又称AVL树，树，要求从整体上看，在动态插入或删除后，每个结点的左右子树能够基本保持平衡。不会出现过分倾斜的现象，从而使得平均检索长度保持比较短。 结点右子树高度与左子树高度之差称为该结点的平衡因子平衡因子，平衡二叉排序树中每个结点的平衡因子只能是1、0或1。 2627插入的影响插入的影响 在平衡二叉排序树中插入新结点时，如果新结点插入后不影响其父结点为根的子树高度，则不会破坏整个二叉排序树的平衡；反之，若父结点为根的子树高度增加了，则可能引起一连串的反映。 其结果又有两种可能，一种是在其祖先的某一层上不再影响子二叉排序树的高度，则整个二叉排序树仍然是平衡的；另一种是在其祖先的某一层上破坏了平衡的要求，使整个二叉排序树不再是AVL树。 28最小不平衡子树最小不平衡子树 处理失去平衡的方法为首先找出最小不平衡子树最小不平衡子