Chapter 5 樹狀結構.

Presentation on theme: "Chapter 5 樹狀結構."— Presentation transcript:

1 Chapter 5 樹狀結構

2 樹狀結構包含：樹根(root)、節點(node)、樹葉(leaf)
樹狀結構 - 定義 樹狀結構包含：樹根(root)、節點(node)、樹葉(leaf) A為樹根，分別與B、C、D相連接。從A到L稱為節點，共有11個節點。

3 每個節點都有父節點(樹根除外) 每個節點的下一個節點稱為子節點 同一個高度的節點稱為兄弟節點 尾端的樹葉稱為外部節點或終端節點 一棵樹除了樹葉外其餘為內部節點或非終端節點。 去除樹根，其餘稱為子樹，這些子樹構成一個”森林”，一個節點擁有的子樹數目稱為”分支度”。

4 樹狀結構-階度(高度) 像是人類的族譜，祖父母到孫子一共三代；在樹狀結構是以「階度、高度」來表示

5 樹狀結構 - 樹的串列表示法 樹狀結構的串列表示法： (A(B(E，F)，C，D(G(K)，H，I(L)))) 樹的記憶體表示法： data
樹狀結構 - 樹的串列表示法 樹狀結構的串列表示法： (A(B(E，F)，C，D(G(K)，H，I(L)))) 樹的記憶體表示法： data link dlink rlink

6 (A(B(E，F)，C，D(G(K)，H，I(L))))
一般化串列節點結構表示法： (A(B(E，F)，C，D(G(K)，H，I(L)))) Tag Data Link

7 樹狀結構 - 二元樹(Binary Tree)
樹狀結構每個節點的分支度沒有固定，處理不便。 二元樹為一個樹根與兩個以下的分支所構成的樹狀結構，二元樹的節點結構為 二元樹的分支度為一左一右，左子樹與右子樹。順序上通常小的置於左子樹，大的置於右子樹，因此二元樹又稱為有序樹。 Llink Data Rlink

8 樹與二元樹： 樹的子樹之間沒有順序關係，二元樹有。 樹至少要有一個樹根，不可以為空集合，二元樹可以。
樹的分支度大於等於 0，而二元樹的分支度小於等於 2 及大於等於 0。

9 樹狀結構-二元樹的特性 高度為1，節點只有樹根A，節點數為1；高度為2，節點數為3(A,B,C)；高度為3，節點數為7(A,B,C,D,E,F,G)。以此類推，高度為n，最大節點數為2n-1，數學式為： …+2n-1=(2n-1)/(2-1)=2n-1 第一高度有一個節點(A)，第二高度有二個節點(B,C)，第三高度有四個節點(D,E,F,G)，則第m高度的節點數目最多有2m-1個。 樹葉總數等於分支度2的節點總數加一。

10 結論： 例題 page174 高度為n的二元樹，其最大的節點數為2n-1 高度為n的二元樹，第m高度的節點樹目最多有2m-1個(其中n≧m)
非空的二元樹，若樹葉總數為n0，且分支度2的節點總數為n2，則n0=n2+1 例題 page174

11 樹狀結構-歪斜樹(Skewed Tree)
當二元樹只有在左邊的節點上或是只有在右邊的節點上，稱為歪斜樹。只有左子樹，稱為左歪斜樹；只有右子樹，稱為右歪斜樹。

12 樹狀結構-完整二元樹(Complete Binary Tree)
若二元樹的高度為n，節點依出現順序排成二元樹，且節點總數≦2n-1，此種二元樹稱為完整二元樹。若節點總數為m，則此完整二元樹的高度為log2m +1。 上圖完整二元樹m=10個節點，log210 +1=4.32，取整數4 非完整二元樹？如：少F或G

13 樹狀結構-完滿二元樹(Full Binary Tree)
若二元樹的高度為n，節點依出現順序排成二元樹，而且節點總數等於 2n-1，此種二元樹稱為完滿二元樹。若二元樹為完滿二元樹，節點總數為m，則此完滿二元樹的高度為log2(m+1)。 節點總數滿足log2(m+1)等於整數為完滿二元樹，否則為非完滿二元樹。該整數即為二元樹高度。 例題 page177

14 樹狀結構-二元樹的儲存表示法 二元樹儲存方式可用陣列和鏈結串列來表示。 循序陣列表示法：
將二元樹視為一個完滿二元樹，依節點的階度依序存放入記憶體內。 節點 1 2 3 4 5 6 7 8 9 10 11 鍵值 A B C D E F G H I J K Level 1 Level 2 Level 3 Level 4

15 二元樹的儲存表示法 二元樹若為完整或完滿二元樹，則使用陣列表示法將有效節省空間；否則將浪費記憶體空間。 圖5-12 E D F 節點 1 2
3 4 5 6 7 8 9 10 11 鍵值 A B C D E F Level 1 Level 2 Level 3 Level 4

16 二元搜尋樹(binary search tree)為二元樹，具下列性質：
左子樹節點的值小於(≦)根節點的值 右子樹節點的值大於(≧)根節點的值 左、右子樹仍為二元搜尋樹 例題 ko5_1

17 樹狀結構-二元樹的儲存表示法 鏈結串列表示法： 陣列表示法較鏈結串列表示法浪費記憶體空間。 例題 ko5_2，例題page 184, 185
F C B E D A B C D E F

18 樹狀結構-二元樹的追蹤 二元樹的追蹤就是拜訪二元樹的每一個節點。
假設L、D、R分別代表節點的左子樹、資料、右子樹，依據二元樹由左而右追蹤的特性，會有三種情況：LDR(中序追蹤 inorder traversal)、LRD(後序追蹤 postorder traversal)、DLR(前序追蹤 preorder traversal)。 Llink Data Rlink

19 樹狀結構-二元樹的追蹤 中序追蹤(LDR) 指拜訪二元樹節點的順序為左子樹→樹根節點→右子樹(樹根在拜訪二元樹節點的過程置於中間)。
中序追蹤是由左子樹→樹根→右子樹 D→B→E→A→F→C 例題 ko5_3 (中序追蹤)

20 樹狀結構-二元樹的追蹤 後序追蹤(LRD) 指拜訪二元樹的順序為左子樹→右子樹→樹根節點(樹根在拜訪二元樹節點的過程置於最後)。
後序追蹤是由左子樹→右子樹→樹根 D→E→B→F→C→A 例題 ko5_4 (後序追蹤)

21 樹狀結構-二元樹的追蹤 前序追蹤(DLR) 指拜訪二元樹節點的順序為樹根節點→左子樹→右子樹(樹根在拜訪二元樹節點的過程置於最前面)
前序追蹤是由樹根→左子樹→右子樹 A→B→D→E→C→F 例題 ko5_5 (前序追蹤)，PAGE193~196

22 樹狀結構-引線二元樹 Fig5-23(Page 196) 充分使用沒有被使用的鏈結欄，避免浪費，使其指向其他的節點。 指標的接法規則：
1.將所有的空鏈結改成指標引線。 2.若引線是從該節點的左子樹指向另一個節點時，此引線應指向中序追蹤的前一個節點。D----A 3.若引線是從該節點的右子樹指向另一個節點時，此引線應指向中序追蹤的後一個節點。F---C 中序追蹤 B—A—D—F—C—E See page 197~8 for example LBit LChild Data RChild RBit See Page 197、198

23 樹狀結構-樹的二元樹表示法 一般樹轉換成二元樹的方法： 1.將一般樹所有節點的鏈結刪除，但鏈結至最左子樹的鏈結除外。
2.將所有兄弟接點的鏈結在一起。 See fig 5-28 (page199) fig5-29(a)、(b)、(c) 森林轉換成二元樹的方法： 1.將各樹的樹根從左至右連結起來。 2.再以一般樹轉換成二元樹的方法的方法，即可完成森林轉換成二元樹。 See fig 5-30 (page200) fig5-31(a)、(b)、(c)、(d) See例題page202、203

24 樹狀結構-二元樹的計數 二元樹的計數在於討論n個節點可以排成幾種不同的二元樹： 1.n=1，有一種不同的排列。
n=p，有 種不同的排列。 例題(page204)

25 樹狀結構-樹的種類 以下是樹的種類：二元搜尋樹、延伸二元樹、最小加權外路徑長度二元樹、解碼樹、最佳二元搜尋樹、平衡樹、累堆樹、決策樹、選擇樹、輸家樹、遊戲樹、B 樹 二元搜尋樹 二元搜尋樹必須合乎下列條件： 若存在左子樹時，其鍵值須小於樹根的鍵值。 若存在右子樹時，其鍵值須大於樹根的鍵值。 Fig5-33 (page 205) {28, 24, 46, 59, 26, 40, 19, 40*} STEPS see page 205 若一組鍵值中有兩個以上的鍵值相同，後面的鍵值比前面的鍵值大。

26 樹狀結構-樹的種類 二元搜尋樹插入元素 二元搜尋樹插入元素是在已存在的二元搜尋樹內，插入某一個元素，其插入的結果還是要符合二元搜尋樹的條件。如前例中加入鍵值30，see Fig 5-35 (page 207)。 刪除二元搜尋樹的元素 二元搜尋樹的元素刪除後，也不可以失去二元搜尋樹的特性。刪除方法如下： Ψ 如果是樹葉的鍵值直接刪除。 Ψ如果刪除非樹葉的鍵值，先從其右子樹找出大於且 最接近次鍵值來取代它，然後，刪除此鍵值。 Ψ如前例中刪除鍵值40、28，see Fig 5-36 (page 208)。

27 樹狀結構-樹的種類 延伸二元樹 指任何一個二元樹，若有n個節點，具有n-1個非空鏈結，n+1個空鏈結， 若在每一個空鏈結上加入一個特殊的節點，稱此節點為外節點，其餘節點為內節點。See Fig 5-37 (page 209) 如此利用內、外節點建立的二元樹，稱為延伸二元樹。用於搜尋時，搜尋到外節點，代表搜尋失敗。 節點長度為樹根至節點的分支數 Fig 5-37內節點長度I、外節點長度E I= =6 E= =16 E=I+2n n為延伸二元樹的節點數 歪斜二元樹I、E值最大，完整二元樹I、E值最小

28 樹的種類 最小加權外路徑長度二元樹 加權代表兩個節點間的距離或價錢。
外長度路徑是指由樹根到每個外節點的路徑長度之總和；內路徑長度是指由樹根到每個內節點的路徑長度之總和。 假設有n個節點，每個外節點(長度或距離為k)均設有一加權數q，則此二元樹的加權外路徑長度等於： see Fig5-38(page 210) Huffman碼see Fig5-3 (page 210) Huffman解碼樹：see page 211~213 & 213 最佳二元搜尋樹：指所有二元搜尋樹中具備有最小加權外路徑長度的二元樹。

29 樹狀結構-樹的種類 平衡樹 AVL樹必須合乎下列的條件：
AVL樹進行插入或刪除後，高度須平衡。如不平衡可用LL、RR、LR、RL型(see page 215~6)旋轉成平衡。 將串列鏈結二元樹 轉成平衡二元樹。 See Fig 5-43 (page 216~7)

30 平衡樹 n層平衡樹最少節點數： 平衡二元樹 例題 page 219~221 n層最少節點數= n-1層最少節點數+ n-2層最少節點數+1
1層 ：1個(root) 2層 : 2個 3層 : 4個 4層 : 7個 平衡二元樹 n層最少節點數= n-1層最少節點數+ n-2層最少節點數+1 例題 page 219~221

31 樹狀結構-樹的種類 累堆樹 累堆樹又稱為最大累堆樹。 最小累堆樹 累堆樹是一個完整二元樹。 每個節點之鍵值必須大於其子節點之鍵值。
累堆樹的樹根之鍵值是最大的。 累堆樹又稱為最大累堆樹。 最小累堆樹 每個節點之鍵值必須小於其子節點之鍵值，而且樹根之鍵值是最小的，這種累堆樹稱為最小累堆樹。 串列鏈結二元樹45、83、7、61、12、99、44、77、14、29轉換成最大累堆樹：see page 221~2。 例題page 223~225。 相同串列鏈結二元樹轉換成最小累堆樹see page 225~6。例題page 227。

32 樹的種類 最小-最大累堆樹 若有一個完整二元樹，此二元樹交互階度分別為最小階度及最大階度，其中樹根為最小鍵值。
建立最小-最大累堆樹的原則是：各(子)樹 階度1的鍵值<階度3的鍵值<階度5的鍵值………. 階度2的鍵值>階度4的鍵值>階度6的鍵值………. See Fig5-57~8 (page 228) 例題 page 228~230

33 樹狀結構-樹的種類 雙累堆樹 雙累堆樹是一個完整二元樹。 雙累堆樹的樹根不包含任何元素。 雙累堆樹的左子樹為一個最小累堆樹。
雙累堆樹的右子樹為一個最大累堆樹。 左子樹節點鍵值必須小於或等於對應右子樹節點鍵值。 例題 page 231~3

34 樹狀結構-樹的種類 決策樹 決策樹是從八個錢幣找出偽幣的問題。
假設有八枚硬幣，其中有一枚與其他七枚重量不同，因為他是偽造的，現在利用一個等臂天平將偽幣找出，希望以最少比較次數，找出偽幣。將一連串比較的可能結果列出一樹狀結構，此樹狀結構稱為決策樹。 例題 ko5_6 (決策樹) 選擇樹 輸家樹 遊戲樹 通常用於#字遊戲、圍棋、象棋、黑白棋、NXN陣列的棋子等等。

35 樹狀結構-樹的種類 B樹 m-路搜尋樹 二元搜尋樹節點最多有2個子樹，而m-路搜尋樹節點最多有m個子樹，此兩種搜尋樹用於I/O資料存取的次數，有截然不同的結果 m-路搜尋樹用於I/O資料存取的次數比二元搜尋樹的次數減少許多。

36 B樹 m-路搜尋樹是指一棵樹的根節點最多有m個子樹，具有下列性質： 節點的結構為：
n, A0,(K1, A1), (K2, A2),…,(Kn, An) 其中Ai，0≦i≦n是指向m-路搜尋樹子樹的指標，且Ki，1≦i≦n為m-路搜尋樹的鍵值。 節點的鍵值是由小而大排列的。 Ai所有的鍵值小於Ki+1 An所有的鍵值大於Kn。 所有的子樹Ai，0≦i≦n也是m-路搜尋樹。 See Fig 5-74(page 242) 3-路搜尋樹

37 B樹 B樹 B樹是指度數(order)為m的m-路搜尋樹。有如下特性： 根節點至少有兩個子樹節點 每一節點的分支度≦m
非終端節點(樹根除外)每一節點所含的節點數為n，則m/2≦n≦m 所有樹葉節點都在同一層 高度為h，order為m的B樹，最多有(mh-1)/(m-1)個節點數，最多有mh-1個鍵值數 2-3樹、 2-3-4樹 see Fig 5-75, Fig 5-76 (page243)

38 B樹 B樹鍵值的插入 通常一個鍵值插入到B樹，須找到該鍵值的適當位置，此適當位置不會因加入某一鍵值後，而形成該節點鍵值爆滿，即可將此鍵值插入到此節點內。 如果加入鍵值後而形成節點鍵值爆滿，須將此節點一分為二，同時將鍵值Km/2提升到其父節點上，若因鍵值Km/2提升到其父節點上，直到上述情況不再發生為止。 Fig 5-75 B樹中插入15成Fig 5-77 Fig 5-75 B樹中插入30成Fig 5-78修改後成Fig 5-79 例題see page245~7

39 B樹 B樹鍵值的刪除 在B樹中欲刪除某一鍵值p，先找出其位置，其次再判斷此鍵值所在位置的節點是否為終端節點。 鍵值所在位置的節點為終端節點
刪除後，節點內尚有其他鍵值see page 248 (a) (b) 鍵值所在位置的節點不為終端節點 刪除後，尋找其右節點的所有鍵值中最小者取代刪除鍵值。 刪除後，若鍵值數＜(m/2)-1，必須回到先前步驟調整節點內的鍵值 例題see page248~251

40 樹狀結構-樹的種類 B樹的搜尋 若x為欲搜尋的鍵值，在B樹的節點找到一個i值，滿足Ki≦x＜Ki+1，則：
如果x> Ki ，則繼續搜尋Ai指向的節點。 如果x= Ki ，表示找到搜尋值。 如果Ai=0，表示沒有找到搜尋值，搜尋失敗。

41 樹狀結構-集合的表示法 森林所代表的集合是互斥的
如上圖一共有九個元素存在四顆子樹內，而構成一座森林，子樹與子樹之間彼此沒有任何關係，換言之，九個元素形成四個互斥的集合S1.S2.S3.S4。每一個集合的內容：S1={A.B.C}、S2={D.E}、S3={F.G.H}、S4={I}

42 樹狀結構-樹的種類 S1∪S2∪S3∪S4={A.B.C.D.E.F.G.H.I} 以A為樹根的聯集表示法如下：