2007年2月2日 星期五

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-TreeBinary Search Tree
m/2 <>0 =< degree ="<">
External SearchInternal Search
Balance TreeNot all Balance Tree


Balance Tree = All Terminal Node(leafs)in same level

沒有留言: