資料結構(DataStructures)要点.pdf

資料結構 (Data Structures) 資料結構 (Data Structures) Course 8: Advance Tree (高等樹) Course 8: Advance Tree (高等樹) 授課教師：陳士杰 授課教師：陳士杰 國立聯合大學 資訊管理學系 國立聯合大學 資訊管理學系 ▓Outlines ▓Outlines 本章重點 Extended Binary Tree Min-weighted External Path Length Binary Search Tree的效益 AVL Tree M-way Search Tree B Tree B+ Tree 2 國立聯合大學資訊管理學系 資料結構課程(陳士杰) 2 國立聯合大學資訊管理學系 資料結構課程(陳士杰) ▓Extended Binary Tree (延伸二元樹) ▓Extended Binary Tree (延伸二元樹) Def: 具有External Node的B.T.稱之。 External Node 一個二元樹具有n個節點，若以Link List表示，則會有n+1 條空 Link ，在這些空Link上加上特定節點，稱為External Node (或 Failure Node)，其餘Nodes稱Internal Nodes。 範例： A B D C E 外部節點數= 內部節點數+ 1 (P.S.: 2n – (n-1)=n+1) 為何外部節點又被稱為失敗節點？ 以二元搜尋樹的角度來説，若搜尋到外部節點時，代表在原本的二 元樹中找不到想要的資料，也就是搜尋失敗。 3 國立聯合大學資訊管理學系 資料結構課程(陳士杰) 3 國立聯合大學資訊管理學系 資料結構課程(陳士杰) Internal path Length (I) and Extended path Length (E) Internal path Length (I) and Extended path Length (E) Def: n I (Root 到內部節點 i 的路徑長度) ∑ i 1 n 1 + E (Root 到外部節點 j 的路徑長度) ∑ j 1 定理：E = I + 2n (n為內部節點個數) 範例 1：一個具有5個Internal Nodes的Extended B.T.，其 I値與E値分別為? 0 0 A 1 1