Huffman樹、二叉排序樹

1、Huffman樹、二叉排序樹樹、二叉排序樹 胡俊峰 2016/04/8 2今天的內(nèi)容今天的內(nèi)容 Huffman樹 二叉排序樹簡介3建立建立n個元素的堆？個元素的堆？ 從0開始，不斷插入堆：O(nlogn) 4有沒有更好（高效率）的方法？有沒有更好（高效率）的方法？012345678910115哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 哈夫曼樹 哈夫曼算法 哈夫曼編碼6Huffman樹與最優(yōu)編碼樹與最優(yōu)編碼 信息與編碼 擴充二叉樹與最優(yōu)編碼 Huffman樹7擴充二叉樹的概念擴充二叉樹的概念把原二叉樹的結(jié)點都變?yōu)槎葦?shù)為2的分支結(jié)點如果原結(jié)點的度數(shù)為2，則不變度數(shù)為1，則增加一個分支，度數(shù)為0（樹葉），則

2、增加兩個分支?？斩鏄涞臄U充二叉樹規(guī)定為只有一個外部結(jié)點組成的二叉樹。德智5體77018內(nèi)部節(jié)點YNYYNN1008概率加權(quán)、前綴編碼、加權(quán)平衡二叉樹概率加權(quán)、前綴編碼、加權(quán)平衡二叉樹 wi是第i個外部結(jié)點的權(quán)值 li為從根到第i個外部結(jié)點的路徑長度 m為外部結(jié)點的個數(shù)。 WPL = 1 x 5 + 2 x 70 + 3 x 18 + 3 x 7 = 5 + 140 + 54 + 21 = 220 德智5體77018內(nèi)部節(jié)點YNYYNN100miiilwWPL1外部路徑外部路徑1000119外部路徑與加權(quán)外部路徑外部路徑與加權(quán)外部路徑“外部路徑長度” E:在擴充的二叉樹里從根到每個外部結(jié)點的路

3、徑長度之和。其中，li為從根到第i個外部結(jié)點的路徑長度，m為外部結(jié)點的個數(shù)。設(shè)擴充二叉樹具有m個帶權(quán)值的外部結(jié)點，那么從根結(jié)點到各個外部結(jié)點的路徑長度與相應(yīng)結(jié)點權(quán)值的乘積的和，叫做擴充二叉樹的帶權(quán)的外部路徑長度。其中，wi是第i個外部結(jié)點的權(quán)值，li為從根到第i個外部結(jié)點的路徑長度，m為外部結(jié)點的個數(shù)。miilE1miiilwWPL110哈夫曼樹：哈夫曼樹：對于一組非負(fù)實數(shù)w1 , w2 , w3 , wm，存在一棵以wi（i = 1,2,，m）為權(quán)的m個外部結(jié)點的擴充的二叉樹，使得帶權(quán)的外部路徑長度WPL最小。這棵二叉樹就稱為哈夫哈夫曼樹曼樹或最優(yōu)二叉樹最優(yōu)二叉樹。WPL = 1 x 70

4、+ 2 x 18 + 3 x 5 + 3 x 7 = 70 + 36 + 15 +21 = 142智體70德7185內(nèi)部節(jié)點YNYYNN10011哈夫曼樹（構(gòu)建算法）哈夫曼樹（構(gòu)建算法）給定m個權(quán)值 w1 , w2 , wm （葉子）構(gòu)造由m棵二叉樹組成的樹林F = T1,T2,Tm，其中每棵樹Ti 只有一個根結(jié)點，且根結(jié)點的權(quán)值為wi；在樹林中選取兩棵根結(jié)點權(quán)值最小的和次小的二叉樹作為左右子樹構(gòu)造一棵新的二叉樹，其根結(jié)點的權(quán)值為左右子樹根結(jié)點權(quán)值之和。將新的二叉樹加入到樹林F中，去除原兩棵權(quán)值最小的樹；重復(fù)2、3步驟，直至F中只剩一棵樹為止。12給定權(quán)值給定權(quán)值 7，5，2，4，構(gòu)造哈夫曼樹

5、，構(gòu)造哈夫曼樹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哈夫曼樹的存儲實現(xiàn)哈夫曼樹的存儲實現(xiàn) 存儲結(jié)構(gòu)可以有多種，如二叉鏈表、三叉鏈表等。下面給出一種順序結(jié)構(gòu)(一維數(shù)組），結(jié)點結(jié)構(gòu)：

6、ww: 以該結(jié)點為根的子樹中所有外部結(jié)點的加權(quán)和。 parent: 父結(jié)點在數(shù)組中的存儲位置（下標(biāo)），根無父，設(shè)為-1。 llink: 左孩子存儲位置，對于外部結(jié)點，無孩子，設(shè)為-1。 rlink: 右孩子存儲位置，對于外部結(jié)點，無孩子，設(shè)為-1。wwparentllinkrlink16在線性結(jié)構(gòu)上實現(xiàn)哈夫曼樹在線性結(jié)構(gòu)上實現(xiàn)哈夫曼樹struct HtNode /* 哈夫曼樹結(jié)點的結(jié)構(gòu) int ww; int parent, llink, rlink;哈夫曼樹可定義為： struct HtTree struct HtNode htMAXNODE; int root；/* 樹根在數(shù)組中的下標(biāo)*/

7、;typedef struct HtTree *PHtTree;17哈夫曼算法（初始化）哈夫曼算法（初始化）18哈夫曼算法（構(gòu)造樹）哈夫曼算法（構(gòu)造樹）思考：如果用堆結(jié)構(gòu)實現(xiàn)huffman算法有沒有問題？19使用優(yōu)先隊列20二叉排序樹（又稱二叉搜索樹）二叉排序樹（又稱二叉搜索樹） 以關(guān)鍵碼值關(guān)鍵碼值為結(jié)點的二叉樹 如果任一結(jié)點的左子樹非空，則左子樹中的所有結(jié)點的關(guān)鍵碼都小于根結(jié)點的關(guān)鍵碼； 如果任一結(jié)點的右子樹非空，則右子樹中的所有結(jié)點的關(guān)鍵碼都大于根結(jié)點的關(guān)鍵碼。 10152040 6 2 815302521最佳二叉排序樹（續(xù)）最佳二叉排序樹（續(xù)） 在擴充二叉排序樹里，檢索一個關(guān)鍵碼的平均比

8、平均比較次數(shù)較次數(shù)為： 檢索中平均比較次數(shù)最小，即E(n)最小的二叉排序樹稱作最佳二叉排序樹最佳二叉排序樹。niniiiiilqlpwnE10) 1(1)(22最佳二叉排序樹的構(gòu)造最佳二叉排序樹的構(gòu)造 對于K=27,73,10,5,18,41,99,51,25，構(gòu)造最佳二叉排序樹的過程如下：首先將它們排序為：5，10，18，25，27，41，51，73，99，然后從空二叉樹出發(fā)，在排序的關(guān)鍵碼序列中用二分法檢索5，檢索中遇到的結(jié)點為27,10,5，將這三個結(jié)點插入二叉排序樹。再檢索第二個結(jié)點10，遇到的結(jié)點為27,10，二叉排序樹中已經(jīng)有這兩個結(jié)點。再檢索第三個結(jié)點18，。得到的插入次序為27

9、，10，5，18，25，51，41，73，99。2324平衡二叉排序樹平衡二叉排序樹 以上的“最佳”二叉排序樹，不僅構(gòu)造的時間代價很大，而且很難動態(tài)的保持。通常用于表示一旦構(gòu)造后就不改動的靜態(tài)字典靜態(tài)字典； 對于動態(tài)字典動態(tài)字典，為了能夠在進行元素的插入和刪除操作時，較快地對二叉排序樹進行調(diào)整，通常不要求二叉排序樹總是保持“最佳的”檢索效率，而是希望達到一種比較容易調(diào)整的“較佳”的狀態(tài)。25平衡二叉排序樹，平衡二叉排序樹， 又稱AVL樹，樹，要求從整體上看，在動態(tài)插入或刪除后，每個結(jié)點的左右子樹能夠基本保持平衡。不會出現(xiàn)過分傾斜的現(xiàn)象，從而使得平均檢索長度保持比較短。 結(jié)點右子樹高度與左子樹高度之差稱為該結(jié)點的平衡因子平衡因子，平衡二叉排序樹中每個結(jié)點的平衡因子只能是1、0或1。 2627插入的影響插入的影響 在平衡二叉排序樹中插入新結(jié)點時，如果新結(jié)點插入后不影響其父結(jié)點為根的子樹高度，則不會破壞整個二叉排序樹的平衡；反之，若父結(jié)點為根的子樹高度增加了，則可能引起一連串的反映。 其結(jié)果又有兩種可能，一種是在其祖先的某一層上不再影響子二叉排序樹的高度，則整個二叉排序樹仍然是平衡的；另一種是在其祖先的某一層上破壞了平衡的要求，使整個二叉排序樹不再是AVL樹。 28最小不平衡子樹最小不平衡子樹 處理失去平衡的方法為首先找出最小不平衡子樹最小不平衡子