分類：圖說演算法-JavaScript

9-10平衡樹

由於二元搜尋樹的缺點是無法永遠保持在最佳狀態。當加入之資料部分以排序的情況下，極有可能產生歪斜樹，因而使樹的高度增加，導致搜尋效率降低。所以二元搜尋樹較不利於資料的經常變動(加入或刪除)。為了能夠盡量降低搜尋所需要的時間，讓我們在搜尋的時候能夠很快找到所要的鍵值，我們必須讓樹的高度越小越好。

所謂平衡樹(Balance Binary Tree)，又稱之為AVL樹(是由Adelson-Velskii 和 Landis兩人所發明的)，本身也是一棵二元搜尋樹，在AVL樹中，每次在插入資料和刪除資料後，必要的時候會對二元樹做一些高度的調整動作，而這些調整動作就是要二元搜尋樹的高度隨時維持平衡。T是一個非空的二元樹，Tl及Tr分別是它的左右子樹，若符合下列兩條件，則稱T是個高度平衡樹：

至於如何調整一二元搜尋樹成為一平衡樹，最重要找出(不平衡點)，再依照以下四種不同旋轉型式，重新調整其左右子樹的長度。首先，令新插入的節點為N，且其最近的一個具有+-2的平衡因子點為A，下一層為B，再下一層C，分述如下：

現在我們來實作一個範例，下圖的二元樹，下圖的二元樹原是平衡的，加入節點12後變為不平衡，請重新調整成平衡樹，但不可破壞原有的次序結構：

---

9-11決策樹的智慧

我們也常把決策樹(Decision Tree)稱為(遊戲樹)，這是因為遊戲中的AI經常以決策樹資料結構來實作的緣故。對資料結構而言，決策樹本身是人工智慧(AI)中一個重要理念，在資訊管理系統(MIS)中，也是決策支援系統(Decision Support System,DSS)的執行基礎。
簡單來說，決策樹是一種利用樹狀結構的方法，來討論一個問題的各種情況分布的可能性。例如最典型的(8枚金幣)問題來闡釋決策樹的觀念，內容是假設有8枚金幣a,b,c,d,e,f,g,h且其中有一枚是儰造的，儰造金幣的特徵為重量稍輕或偏重。請問如何使用決策樹方法，找出這枚儰造的錢幣；如果是以L表示輕於真品，H表示重於真品。第一次比較從8枚中挑選6枚a,b,c,d,e,f分2組來比較，則會有下列三種情形產生：
(a+b+c)>(d+e+f)
(a+b+c)=(d+e+f)
(a+b+c)<(d+e+f)

不過如果今天您要設計的遊戲並不是屬於(棋類)或是(紙牌類)的話，所採用的技巧在於實現遊戲作決策的能力，簡單的說，該下哪一步或者該出哪一張牌，因為通常可能的狀況有很多，例如象棋遊戲的人工智慧就必須在所有可能的情況中選擇一步對自己最有利的棋，想想看如果開發此類的遊戲，您會怎麼作？這時決策樹也可派上用場。
通常此類遊戲的AI實現技巧為先找出所有可走的棋(或可出的牌)，然後逐一判斷如果走這步棋(或出這張牌)的優劣程度如何，或者說是替這步棋打個分數，然後選擇走得分最高的那步棋。
一個最常被用來討論決策型AI的簡單例子是(井字遊戲)，因為它的可能狀況不多，也許您只要花個十分鐘便能分析完所有的狀況，並且找出最佳的玩法，例如下圖可表示某個狀況下的O方的決策樹：

上圖是井字遊戲的某個決策區域，下一步是X方下棋，很明顯的X方絕對不能選擇第二層的第二個下法，因為X方必敗無疑，而您也看出這個決策形成樹狀結構，所以也稱之為(決策樹)，而樹狀結構正是資料結構所討論的範圍，這也說明了資料結構正是人工知會的基礎，而決定型人工智慧的基礎則是搜尋，在所有可能的狀況下，搜尋可能獲勝的方法。

9-8延伸二元樹入門   Extended Binary Tree

至於什麼叫最小搜尋成本呢？就讓我們先從延伸二元樹(Extension Binary Tree)談起。任何一個二元樹中，若有n個節點，則有n-1個非空鏈結及n+1個空鏈結。如果在每一個空鏈結加上一個特定節點，則稱為外節點，其餘的節點稱為內節點，且定義此種樹為(延伸二元數)，另外定義外徑長=所有外節點到樹根距離的總和，內徑長=所有內節點到樹根距離的總和。我們將以下例來說明(A)(B)兩圖，它們的延伸二元樹繪製：

以上(A)、(B)二圖為例，如果每個節點有加權值(例如搜尋機等)，則外徑常必須考慮相關加權值，或稱為加權外徑長，以下將討論(A)、(B)的 加權外徑長：

iT幫幫忙-解說：延伸二元樹

---

9-9霍夫曼樹特訓班

霍夫曼樹經常用於處理資料壓縮的問題，可以根據資料出現的頻率來建構的二元樹。例如資料的儲存和傳輸是資料處裡的二個重要領域，兩者皆和資料量的大小息息相關，而霍夫曼樹正可用來進行資料壓縮的演算法。

簡單來說，如果有n個權值(q1,q2…qn)，且構成一個有n個節點的二元樹，每個節點節點外部節點權值為qi，則加權徑長度最小的就稱為(最佳化二元樹)或(霍夫曼樹)Huffman Tree。對上一小節中，(A)、(B)二元樹而言，(A)就是二者的最佳化二元樹。接下來我們將說明，對一含權值的串列，該如何求其最佳化二元樹，步驟如下：

1.產生兩個節點，對資料中出現過的每一元素各自產生一樹葉節點，並賦予樹葉節點該元素之出現頻率。
2.另N為T1和T2的父親節點，T1和T2是T中出現頻率最低的兩個節點，令N節點的出現頻率等於T1和T2的出現頻率總和。
3.消去步驟的兩個節點，插入N，再重複步驟1。

我們將利用以上的步驟來實作求取霍夫曼樹的過程，假設現有五個字母BDACE的頻率分別為0.09、0.12、0.19、0.21和0.39，請說明霍夫曼樹建構之過程：

9-7堆積樹排序法-2

下面我們利用堆積排序法針對34、19、40、14、57、17、4、43的排序過程示範如下：

1.依下圖數字順序建立完整二元數。

2.建立堆積樹

3.將57自樹根移除，重新建立堆積樹

4.將43自樹根移除，重新建立堆積樹。

5.將40樹根移除，重新建立堆積樹

6.將34自樹根移除，重新建立堆積樹

7.將19自樹根移除，重新建立堆積樹

8.將17自樹根移除，重新建立堆積樹

9.將14自樹根移除，重新建立堆積樹

最後將4自樹根移除。得到的排序結果為57、43、40、34、19、17、14、4

JS                    heap.js

var heap=(data,size)=> {
	for (let i=Math.floor(size/2); i>0; i--)
		ad_heap(data, i, size-1);
	process.stdout.write('\n');
	process.stdout.write('堆積內容：');
	for (let i=1; i<size; i++)
		process.stdout.write('['+data[i]+'] ');
	process.stdout.write('\n\n');
	for (let i=size-2; i>0; i--) {
		temp=data[1];
		data[1]=data[i+1];
		data[i+1]=temp;
		ad_heap(data, 1, i);
		process.stdout.write('處理過程：');
		for (let j=1; j<size; j++)
			process.stdout.write('['+data[j]+'] ');
		process.stdout.write('\n');
	}
}

var ad_heap=(data, i, size)=> {
	j=2*i;
	tmp=data[i];
	post=0;
	while (j<=size && post==0) {
		if (j<size) {
			if (data[j]<data[j+1])
				j+=1;
		}
		if (tmp>=data[j])
			post=1;
		else {
			data[Math.floor(j/2)]=data[j];
			j=2*j;
		}
	}
	data[Math.floor(j/2)]=tmp;
}
data=[0,5,6,4,8,3,2,7,1];
size=9;
process.stdout.write('原始陣列：');
for (i=1; i<size; i++)
	process.stdout.write('['+data[i]+'] ');
heap(data,size);
process.stdout.write('排序結果：');
for (i=1; i<size; i++)
	process.stdout.write('['+data[i]+'] ');