Embedded Files
本章內容為霍夫曼(Huffman)編碼與AVL樹，霍夫曼編碼使用樹狀結構找出編碼長度最短的編碼，而AVL樹為平衡的二元搜尋樹，比起二元搜尋樹有較好的執行效率。
7-1 霍夫曼(Huffman)編碼
霍夫曼(Huffman)編碼需要瞭解外部路徑長(External Path Length)與加權外部路徑長(Weighted External Path Length)的概念。外部路徑長(External Path Length)為從根節點到外部節點的路徑長度總和，如下圖，節點a、b、c、d、e為外部節點，所以此圖的外部路徑長為2(節點a)+3(節點b)+3(節點c) +2(節點d) +2(節點e)=12。
加權外部路徑長(Weighted External Path Length)為從根節點到外部節點的路徑長度乘以權重的總和，如下圖，節點a(權重為4)、b(權重為3)、c(權重為7)、d(權重為7)、e(權重為2)為外部節點，所以此圖的加權外部路徑長為4*2(節點a)+3*3(節點b)+7*3(節點c) +2*2(節點d) +7*2(節點e)=56，霍夫曼(Huffman)編碼用於找出最小加權外部路徑長。
霍夫曼編碼的概念
貪婪準則是先將所有字元依照出現頻率的由小到大進行排序，優先考慮出現頻率最低的兩個字元，組合成新的節點，此節點的頻率為兩個目前最小字元頻率的加總，將此節點重新加入所有字元的排序，再取出最小的兩個字元或節點，組合成新的節點，此節點的頻率為兩個目前最小字元頻率的加總，將此節點重新加入所有字元的排序，如此不斷重複，直到最後剩下一個節點。編碼為最上層的左邊編碼0而右邊編碼1，從上到下重複左邊編碼0而右邊編碼1，直到無法下去為止，越下面字元編碼越長。
假設有五個英文分別是a、b、c、d與e，出現頻率分別為10、4、5、7與8，進行霍夫曼編碼解說，將這些資料輸入到陣列hf，示意圖如下。
輸入後的陣列hf
Step1)依照出現頻率的由小到大進行排序，排序後的陣列hf如下。
將陣列hf所有元素依序加入串列中，串列命名為tmp。
Step2)取出tmp中w值最小的兩個元素，字元分別是b與c，結合成一個新的節點，新節點的w等於節點b的w值加上節點c的w值等於9，加入到tmp的最後。
將tmp依照出現頻率的由小到大進行排序。
目前建立的霍夫曼樹。
Step3)取出tmp中w值最小的兩個元素，字元分別是d與e，結合成一個新的節點，新節點的w等於節點d的w值加上節點e的w值等於15，加入到tmp的最後。
將tmp依照出現頻率的由小到大進行排序。
目前建立的霍夫曼樹。
Step4)取出tmp中w值最小的兩個元素，字元分別是「b與c」與a，結合成一個新的節點，新節點的w等於節點「b與c」的w值加上節點a的w值等於19，加入到tmp的最後。
將tmp依照出現頻率的由小到大進行排序。
目前建立的霍夫曼樹。
Step5)取出tmp中w值最小的兩個元素，字元分別是「d與e」與「b、c與a」，結合成一個新的節點，新節點的w等於節點「d與e」的w值加上節點「b、c與a」的w值等於34，加入到tmp的最後。
將tmp依照出現頻率的由小到大進行排序。
完成建立的霍夫曼樹，左邊是0，右邊是1，編碼所有字元。
編碼結果為下表，每個字元的編碼長度不固定，字元出現頻率較高者編碼長度較短，若一篇文章字母出現頻率符合事先設定的字母出現頻率，則經由霍夫曼編碼的編碼長度最短。
霍夫曼解碼的過程
假設編碼字串「abcde」，經由查詢編碼對照表，如下表，會編碼成「111001010001」。
編碼後的字串「111001010001」，解碼過程如下，由左到右讀取到可以辨認出的字母為止。
Step1)讀取最左邊的「1」，發現可能會是a、b或c，再讀取第2個字元「1」時，就可以確認是「a」。
Step2)接著讀取第3個字元「1」，發現可能會是a、b或c，再讀取第4個字元「0」時，可以確認是「b或c」，再讀取第5個字元「0」時，可以確認是「b」。
Step3)接著讀取第6個字元「1」，發現可能會是a、b或c，再讀取第7個字元「0」時，可以確認是「b或c」，再讀取第8個字元「1」時，可以確認是「c」。
Step4)接著讀取第9個字元「0」，發現可能會是d或e，再讀取第10個字元「0」時，可以確認是「d」。
Step5)接著讀取第11個字元「0」，發現可能會是d或e，再讀取第12個字元「1」時，可以確認是「e」。
如此就可以將編碼「111001010001」唯一還原成「abcde」，保證不會有兩個以上的解碼結果。
如果不使用霍夫曼編碼，使用固定長度的編碼，則五個字母需要三個位元進行編碼，結果如下。
依照出現頻率產生字串「aaaaaaaaaabbbbcccccdddddddeeeeeeee」，利用霍夫曼編碼長度為10*2(a)+4*3(b)+5*3(c)+7*2(d)+8*2(e)=77；利用長度固定的編碼，每一個字母需要3個位元，編碼長度為10*3(a)+4*3(b)+5*3(c)+7*3(d)+8*3(e)=102。由此可以推估，若一篇文章字母出現頻率符合編碼前所設定的每種字母出現頻率，則霍夫曼編碼可以獲得較短的編碼長度。
7-1-1 實作霍夫曼編碼-使用Sort
這是貪婪演算法的經典問題，已知每個字元的出現頻率，經由霍夫曼編碼可以求得最短的編碼結果，霍夫曼編碼使用可以變動長度的0與1數字進行編碼。本題融合樹狀結構與深度優先搜尋的概念。
輸入說明
每次輸入數字n，n表示字元個數，輸入n小於26，之後有n行分別是每一行為一個小寫英文字母與一個整數組成，小寫英文字母表示被編碼的字元，而整數表示出現的頻率，數值越大表示頻率越高。
輸出說明
輸出每個小寫英文字母的編碼。
輸入範例
5
a 10
b 4
c 5
d 7
e 8
輸出範例
d 00
e 01
b 100
c 101
a 11
(a)程式碼與解說
霍夫曼編碼-使用Sort
第5到12行：宣告結構node，有六個元素分別是id、ch、w、t、le與ri。id表示節點的編號，建立霍夫曼樹時使用，ch表示節點所代表的字元，w表示該字元的出現頻率，t表示是否為字元節點，t為true表示為字元節點，le表示建立霍夫曼樹時的左邊節點編號，ri表示建立霍夫曼樹時的右邊節點編號。
第9行：宣告陣列hf為串列，有101個元素，每個元素都是0。
第10行：宣告陣列code為串列，有10個元素，每個元素都是0。
第11到21行：定義dfs函式，印出字元與霍夫曼編碼的對應。
第12到16行：若不是字元節點，往左邊走，字元陣列code[level]為字元0(第13行)，呼叫dfs進行遞迴，將節點hf[id]的le(左邊節點編號)與變數level加1為輸入參數(第14行)。往右邊走，字元陣列code[level]為字元1(第15行)，呼叫dfs進行遞迴，將節點hf[id]的ri(右邊節點編號)與變數level加1為輸入參數(第16行)。
第17到21行：否則就是字元節點，印出hf[id]的字元ch(第18行)，與使用迴圈印出該字元經的編碼陣列code的每個元素到螢幕(第19到20行)，最後輸出換行(第21行)。
第22行：宣告c為字元串列，初始化為「'a', 'b', 'c', 'd', 'e']」。
第23行：宣告w為頻率串列，初始化為「10, 4, 5, 7, 8」。
第24行：宣告tmp為空串列。
第25行：初始化變數num為串列c的長度。
第26到28行：使用迴圈輸入五個字元與對應的使用頻率，node的id初始化為迴圈變數i，node的字元ch初始化為c[i]，node的頻率w初始化為w[i] ，node的是否為字元節點的t設定為True，node的左子樹le設定為0，node的右子樹ri設定為0，最後hf[i]參考到此node(第27行)，將hf[i]加入到串列tmp(第28行)。
第29行：將tmp所有元素以字元頻率w由小到大進行排序。
第30到39行：當tmp元素個數大於1時，繼續執行while迴圈，表示還有節點要合併。
第31行：取出tmp中頻率最小的元素到a。
第32行：刪除tmp中頻率最小的元素。
第33行：取出tmp中頻率最小的元素到b。
第34行：刪除tmp中頻率最小的元素。
第35行：設定節點n的id為num，表示新產生節點的編號。設定節點n的ch為None，表示該節點沒有字元。設定節點n的w為a.w+b.w，表示權重為兩個節點的權重相加。設定節點n的t為0，表示不是字元節點，是由字元節點組合起來。設定節點n的le為節點a的編號(id)，設定節點n的ri為節點b的編號(id)。
第36行：將節點n儲存到hf[num]。
第37行：將節點n加到tmp的最後。
第38行：將tmp所有元素以字元頻率w由小到大進行排序。
第39行：變數num遞增1。
第40行：使用dfs產生所有字元的霍夫曼編碼。
(b)程式執行結果
d 00
e 01
b 100
c 101
a 11
(c)程式效率分析
第26到39行建立霍夫曼編碼樹，取出兩個點計算後產生一個點後，執行排序，排序所需時間複雜度為O(n*log(n))，n為字母個數，總共執行約n/2次，所以演算法效率為O(n^2*log(n))，排序花了比較多的時間，霍夫曼編碼適合使用堆積(Heap)將最小的元素放在最上面，不需要全部排序，取出最小的元素與插入元素的演算法效率只要O(log(n))，n為字母個數，總共執行約n/2次，所以演算法效率為O(n*log(n))，程式碼改寫如下。
(d)改寫後的程式碼與解說
霍夫曼編碼-使用Heap
第1行：匯入heapq函式庫。
第2行：宣告陣列hf為串列，有101個元素，每個元素都是0。
第3行：宣告陣列code為串列，有10個元素，每個元素都是0。
第4到14行：定義dfs函式，印出字元與霍夫曼編碼的對應。
第5到9行：若不是字元節點，往左邊走，字元陣列code[level]為字元0(第6行)，呼叫dfs進行遞迴，將節點hf[id][4](左邊節點編號)與變數level加1為輸入參數(第7行)。往右邊走，字元陣列code[level]為字元1(第8行)，呼叫dfs進行遞迴，將節點hf[id][5](右邊節點編號)與變數level加1為輸入參數(第9行)。
第10到14行：否則就是字元節點，印出字元hf[id][2](第11行)，與使用迴圈印出該字元經的編碼陣列code的每個元素到螢幕(第12到13行)，最後輸出換行(第14行)。
第15行：宣告c為字元串列，初始化為「'a', 'b', 'c', 'd', 'e']」。
第16行：宣告w為頻率串列，初始化為「10, 4, 5, 7, 8」。
第17行：宣告pq為空串列。
第18到21行：使用迴圈輸入五個字元與對應的使用頻率加入到一個堆積(Heap)內。建立一個tuple，第一個元素為w[i]表示頻率，第二個元素為i，表示節點編號，第三個元素為c[i]，表示字元，第四個元素為True，表示字元節點，第五個元素為0，表示沒有左子樹，第六個元素為0，表示沒有右子樹，最後node參考到此節點(第19行)。設定hf[i]為node(第20行)，使用函式heappush，將node加入pq，pq為Heap結構的串列，pq的最上層為頻率最小的元素(第21行)。
第22行：初始化變數num為串列c的長度。
第23到29行：當串列pq元素個數大於1時，繼續執行while迴圈，表示還有節點要合併。
第24行：使用函式heappop取出pq中頻率最小的元素到a。
第25行：使用函式heappop取出pq中頻率最小的元素到b。
第26行：建立一個tuple，第一個元素為a[0]+b[0]表示將頻率相加，第二個元素為num，表示節點編號，第三個元素為None，表示該節點沒有字元，第四個元素為False，表示不是字元節點，第五個元素為a[1]，表示左子樹，第六個元素為b[1]，表示右子樹，最後node參考到此節點。
第27行：設定hf[num]為node。
第28行：使用函式heappush，將node加入pq，pq為Heap結構的串列，pq的最上層為頻率最小的元素
第29行：變數num遞增1。
第30行：使用dfs產生所有字元的霍夫曼編碼。
7-2 AVL樹
AVL樹改進二元搜尋樹。如果插入已經排序的數列到二元搜尋樹，則會造成傾斜的二元搜尋樹，例如：將10、21、25與34依序插入二元搜尋樹，如下圖，搜尋元素的效率與循序搜尋相同。
為了保證二元搜尋樹左子樹與右子樹的元素數量差不多，不會傾斜一側，定義了AVL樹，如下。
7-2-1 AVL樹的定義
AVL樹是一種高度平衡的二元搜尋樹，任何一個節點的左子樹與右子樹的高度相減只允許1、0或-1，高度大於等於2或小於等於-2就需要調整，符合高度差要在1、0或-1。AVL樹在平均與最差情況下對於搜尋、新增與刪除元素，都有不錯的效率。以下為AVL樹範例，點10的左子樹比右子樹的高度多一個階層，標記為1，點5與點7的左子樹比右子樹的高度少一個階層，標記為-1。
以下不是AVL樹，因為節點5的左右子樹高度相減為-2，需要重新旋轉，才能滿足AVL樹的條件。
AVL樹的每一個節點需要兩個指標，一個指向左子樹，另一個指向右子樹，若子樹是空的時候設定為None，None就是空指標，在AVL樹走訪時遇到None，就不能再走訪下去，必須倒退回去，AVL樹的類別AVLTree宣告如下，val用於儲存資料，left與right指標用於指向左子樹與右子樹，height儲存節點的高度。
7-2-2 AVL樹的旋轉 LL RR LR RL
為了讓AVL樹符合任何一個節點的左子樹與右子樹的高度相減只允許1、0或-1，高度大於等於2或小於等於-2就需要調整，而定義了LL、RR、LR與RL旋轉，以下分別介紹。
(一)LL旋轉
以下AVL樹插入節點2，節點8的左子樹高度與右子樹高度相減為2，不滿足
AVL樹的定義，需要做LL旋轉，節點數較多的AVL樹，在圖中p、q、r與s可能還有其他子樹，在旋轉過程也需要跟著改變位置，LL旋轉是將節點5往上提，左邊是節點2，右邊是節點8，節點8的左子樹改成q。
LL旋轉過後，如下圖，就符合AVL樹的定義。
LL旋轉程式碼如下。
LL旋轉的程式說明如下，node為節點8，執行「left = node.left」，left參考到節點5。執行「left_right = left.right」，left_right參考到子樹q，如下圖。
執行「left.right = node」，left.right為節點5的右子樹，設定為節點8，如下圖。
執行「left.right.left = left_right」，left.right.left為節點8的左子樹，設定為子樹q，如下圖。
執行「return left」，就會使用節點5取代節點8，如下圖，完成LL旋轉。
(二)RR旋轉
以下AVL樹插入節點12，節點8的左子樹高度與右子樹高度相減為-2，不滿足
AVL樹的定義，需要做RR旋轉，節點數較多的AVL樹，在圖中p、q、r與s可能還有其他子樹，在旋轉過程也需要跟著改變位置，RR旋轉是將節點9往上提，左邊是節點8，右邊是節點12，節點8的右子樹改成q。
RR旋轉過後，如下圖，就符合AVL樹的定義。
RR旋轉程式碼如下，原理與LL旋轉類似，請參考LL旋轉。
(三)LR旋轉
以下AVL樹插入節點7，節點8的左子樹高度與右子樹高度相減為2，不滿足
AVL樹的定義，需要做LR旋轉，節點數較多的AVL樹，在圖中p、q、r與s可能還有其他子樹，在旋轉過程也需要跟著改變位置，LR旋轉是將節點7往上提，左邊是節點5，右邊是節點8，節點8的左子樹改成q，節點5的右子樹改成r。
LR旋轉過後，如下圖，就符合AVL樹的定義。
LR旋轉程式碼如下。
LR旋轉的程式如下，node為節點8，執行「left = node.left」，left參考到節點5。執行「left_right = left.right」，left_right指向節點7，如下圖。
執行「left_right_left = left_right.left」，設定left_right_left為節點7的左子樹r，執行「left_right_right = left_right.right」，設定left_right_right為節點7的右子樹q，如下圖。
執行「left_right.left = left」，設定left_right(節點7)的左子樹為left。執行「left_right.right = node」，設定left_right(節點7)的右子樹為node，如下圖。執行「left_right.left.right = left_right_left」，設定left_right.left.right為left_right_left(子樹r)。執行「left_right.right.left = left_right_right」，設定left_right.right.left為left_right_right (子樹q) ，如下圖。
執行「updateHeight」更新節點高度。最後執行「return left_right」，就會使用節點7取代節點8，如下圖，完成LR旋轉。
(四)RL旋轉
以下AVL樹插入節點11，節點8的左子樹高度與右子樹高度相減為-2，不滿足
AVL樹的定義，需要做RL旋轉，節點數較多的AVL樹，在圖中p、q、r與s可能還有其他子樹，在旋轉過程也需要跟著改變位置，RL旋轉是將節點11往上提，左邊是節點8，右邊是節點18，節點8的右子樹改成r，節點18的左子樹改成q。
RL旋轉過後，如下圖，就符合AVL樹的定義。
RL旋轉程式碼如下，原理與LR旋轉類似，請參考LR旋轉。
7-2-3 AVL樹
實作一個AVL樹，可以新增元素，並且每新增一個元素就使用中序走訪，印出AVL樹每一個節點的數值。如果符合AVL樹，使用中序走訪就會由小到大排序。
輸入說明
不須由外部輸入數值，讀取程式內串列的數值，依序輸入這些數值到AVL樹。
輸出說明
輸出每插入一個元素後的中序走訪結果。
(a)程式碼與解說
AVL樹.py
第1到58行：在前一節已經說明。
第59到64行：定義leftBalance方法，以node與x為輸入參數，若x小於node.left.val，則呼叫方法LL進行旋轉，回傳值更新變數node；否則呼叫LR進行旋轉，回傳值更新變數node，最後回傳node。
第65到70行：定義rightBalance方法，以node與x為輸入參數，若x小於node.right.val，則呼叫方法RL進行旋轉，回傳值更新變數node；否則呼叫RR進行旋轉，回傳值更新變數node，最後回傳node。
第71到84行：定義insertNode方法，以node與x為輸入參數，若node不等於None(第72行)，若node.val大於x(第73行)，遞迴呼叫函式insertNode在node.left插入x，回傳值更新node.left(第74行)。若左子樹(node.left)的高度與右子樹(node.right)的高度相減的絕對值等於2，則呼叫函式leftBalance，結果更新node(第75到76行)；否則遞迴呼叫函式insertNode在node.right插入x，回傳值更新node.right(第78行)。若左子樹(node.left)的高度與右子樹(node.right)的高度相減的絕對值等於2，則呼叫函式rightBalance，結果更新node(第79到80行)。否則node等於None，插入節點x到葉節點(第82行)。更新node的高度(第83行)，最後回傳node(第84行)。
第85到89行：使用中序走訪，走訪AVL樹。
第90到98行：定義search方法，以now與x為輸入。若now等於None，則回傳False(第91到92行)。若now的val等於x，則回傳True(第93到94行)，否則若now的val大於x，則遞迴呼叫search，以now的left與x為輸入(第95到96行)；否則遞迴呼叫search，以now的right與x為輸入(第97到98行)。
第99行：新增一個AVLTree物件，初始化數值為7，變數root指向此AVLTree物件。
第100行：新增一個一維陣列，有五個元素。
第101到104行：依序將串列data的每個元素使用函式insertNode插入到AVL樹(第102行)，回傳值更新root，使用方法inorder進行中序走訪(第103行)。輸出換行(第104行)。
第105行：呼叫方法search，找尋13是否在AVL樹內。
(b)程式執行結果
3 7
3 7 10
3 7 8 10
3 7 8 10 13
3 7 8 9 10 13
True
(c)程式效率分析
方法insertNode(插入節點)的演算法效率是O(log(n))，方法search(搜尋節點)的演算法效率也是O(log(n))。
Page updated
Google Sites
Report abuse