Advanced Tree

高等樹

二元搜尋樹的評估
à依照平均比較次數來看，二元搜尋樹的樹高越低越好，可以縮短搜尋所花費的時間。其中也意味著，左右子樹樹高越平均越好。
那些演算法會受到資料輸入的情況不同而受到影響？
1. Binary Search Treeà會退化成左斜曲或右斜曲
2. Insertion Sort（插入搜尋）
3. Bubble Sort（泡泡搜尋）
4. Quick Sort（快速搜尋）

Extended Binary Search Tree（延伸二元樹）
作法：於任一個二元搜尋樹中，若有n個節點，則有n+1個空連結，而在延伸二元樹中，會於此增加一個節點，稱為外部會是失敗節點。

代號E：稱為外部節點，代號I：稱為內部節點。將用此來計算外部路徑長度與內部路徑長度。定理：E=I+2N，E與I成正比；在無加權的情況下，越平衡的二元樹E.I.越小；加權則結果未必。

最小加權外部路徑長度
通常加權值為階層數，外部節點才有加權值。à求取加權外部路徑長度。
此情況下，斜曲樹情況加權值有可能會小於平均樹。

當有加權值à需考慮加權外部路徑，此時應該如何求得最小值？
即是求「最小加權外部路徑長度」（Minimum Weight External Path Length）
求法：利用Huffman Algorithm（霍夫曼演算法）àM.W.E.P.L的解決方案
作法：每次挑選兩個最小值來建立二元樹，將刪除挑選的加權值，之後將加權總和再加入集合之中，重複前述步驟，直到全部挑完為止。
霍夫曼編碼非唯一解！T(n)=O(n*logn)
應用：解碼問題最短時間、編碼方式、平均編碼長度
編碼規則：出現頻率越低者，編碼長度愈長；出現頻率越高者，編碼長度越短。
解編碼問題技巧：給與頻率的話，表示Root為頻率分母值，各分子為樹末端。依照霍夫曼方式進行二元樹建立。左子樹給予編碼位元0；右子樹給予編碼位元1。各符號的編碼即為0與1的組合長度。若求編碼平均長度，就以每個編碼的長度乘以出現頻率，相加後，即為答案。

About AVL Tree
我們都知道AVL Tree為一個平衡的二元搜尋樹。
這一部分屬於高等樹，不過已經拉到二元樹去講了，畢竟這個部份是不會被拆開來考的。
最重要的莫過於二元搜尋樹的繪圖與

About B-Tree
它不是二元搜尋樹！
Degree=m > 2，這種二元搜尋樹稱為B-Tree。用來解決解決外部搜尋問題，以降低樹高減少搜尋次數。故B-Tree為Balance m-way Search Tree，可以是空樹。非空樹，則同時符合下列條件：Root Child>=2；除Root以外，所有NODE Degree必介於m/2與m的中間，以及所有的Terminal Node皆在同一Level。

B-Tree v.s. Binary Search Tree

B-Tree	Binary Search Tree
m/2 <>	0 =< degree ="<">
External Search	Internal Search
Balance Tree	Not all Balance Tree

Balance Tree = All Terminal Node（leafs）in same level