1 第八章 深入探討樹狀結構

2 目次 8.1 m-way 搜尋樹 8.2 B-tree 8.3 動動腦時間 8.4 練習題解答

3 8.1 m-way 搜尋樹 何謂 m-way 搜尋樹？ – 一棵 m-way 搜尋樹，所有節點的分支度均小於或等於 m – 可以是空樹 – 倘若 T 不是空樹，則必須具備下列的性質： 節點的型態是 n, A 0, (K 1, A 1 ), (K 2, A 2 ),…, (K n, A n ) ，其中 A i 是 子樹的指標 0 ≦ i ≦ n< m ； n 為節點上的鍵值數， K i 是鍵值 1 ≦ i ≦ n< m 節點中的鍵值是由小至大排列的，因此 K i < K i+1, 1 ≦ i< n 。 子樹 A i 的所有鍵值均小於鍵值 K i+1 ， 0<i< n 。 子樹 A n 的所有鍵值均大於 K n ，而且 A 0 的所有鍵值均小於 K 1 。 A i 指到的子樹， 0 ≦ i ≦ n 亦是 m-way 搜尋樹。

4 8.1 m-way 搜尋樹 (con.t) Ex ：下圖為 3-way 搜尋樹，共有 12 個鍵值 a 23, 48 12, 17 38, 45 55, 60 28, 32 b c d e f g 25 70

5 8.1 m-way 搜尋樹 (con.t) 下圖為上圖中每個節點之 3-way 搜尋表示法 – 由於 3-way 搜尋樹，每個節點的型態是 n, A 0, (K 1, A 1 ), (K 2, A 2 ),…,(K n, A n ) ，因此 a 節點的格式為 2, b, (23, c), (48, d) 節點格式 abcdefgabcdefg 2, b, (23, c),(48, d) 2, 0, (12, 0), (17, 0) 2, e, (28, 0), (32, f) 2, 0, (55, 0), (60, g) 1, 0, (25, 0) 2, 0, (38, 0), (45, 0) 1, 0, (70, 0)

6 8.1 m-way 搜尋樹 (con.t) m-way 搜尋樹的加入 – 以 3-way 搜尋樹為例，依序將 5 ， 7 ， 12 ， 6 ， 8 ， 4 ， 3 ， 10 加入到搜尋樹，其中 x 表示目前無鍵值存在 (1) 加入 5 (2) 加入 7 (3) 加入 12 5, x 5, 7 12, x 5, 7

7 8.1 m-way 搜尋樹 (con.t) (4) 加入 6 (5) 加入 8 (6) 加入 4 12, x 5, 7 6, x 8, 12 5, 7 6, x 8, 12 5, 7 6, x 4, x

8 8.1 m-way 搜尋樹 (con.t) (7) 加入 3 (8) 加入 10 8, 12 5, 7 6, x 3, 4 8, 12 5, 7 6, x 3, 4 10, x

9 8.1 m-way 搜尋樹 (con.t) m-way 搜尋樹的刪除 刪除方法與二元搜尋樹相同 – 樹葉節點：直接刪除 – 非樹葉節點：以左子樹中最大鍵值或右子樹中最小鍵值 取代之 假設有一棵 3-way 搜尋樹如下： 8, 12 5, 7 6, x 3, 4 10, x

m-way 搜尋樹 (con.t) – 刪除 3 ，則直接刪除 – 刪除 8 8, 12 5, 7 6, x 4, x 10, x 10,12 5, 7 6, x 4, x

m-way 搜尋樹 (con.t) – 刪除 12 – 刪除 7 – 刪除 10 10, x 5, 7 6, x 4, x 5, 10 6, x 4, x 5, 6 4, x

B-tree 何謂 B-tree ？ – 一棵 order 為 m 的 B-tree 是一 m-way 搜尋樹 – 可以是空樹 – 假若高度≧ 1 必需滿足以下的特性： 樹根至少有二個子節點，亦即節點內至少有一鍵值 除了樹根外，所有非失敗節點（即內部節點）至少有 個子節點，至多有 m 個子節點。此表示至少應有 –1 個 鍵值，至多有 m–1 個鍵值 ( 表示大於 m/2 的最小正整數 ) 所有的樹葉節點皆在同一階層

B-tree (con.t) 3-way 搜尋樹 vs. order 為 3 的 B-tree – 左圖不屬於 B-tree of order 3 ，主要是因為樹葉節點不在 同一階層上 ,30 6,8 50,70 a b c d e ,10 15, a b c d ef g h

B-tree (con.t) B-tree 的加入方法 – 從 B-tree 中開始搜尋，假使加入的鍵值 X 在 B-tree 中找 不到，則加入 B-tree 中。假設加入到 P 節點，若 該節點少於 m–1 個鍵值，則直接加入 該節點的鍵值已等於 m–1 ，則將此節點分為二，因為一棵 order 為 m 的 B-tree ，最多只能有 m–1 個鍵值 節點 P ： –1, A 0, (K 1, A 1 ), …, (K –1, A –1 ) 節點 P’ ： m–, A, (K +1, A +1 ), …, (K m, A m ) 並且將 K 和 P' 節點組成 (K, P') 加入其父節點。如下圖所示： P P' K

B-tree (con.t) Ex ：此處的 B-tree 為 order 5 ，表示最多鍵值數為 , 40 60, 70, 80 5,1025,30 45,48 53,54 62,67 72,76 85,90,95 a b c d e f g h i j

B-tree (con.t) – 加入 88 由於 j 節點的鍵值少於 m–1 即 4 個，則直接加入即可 50 20, 40 60, 70, 80 5,1025,30 45,48 53,54 62,67 72,76 85,88,90,95 a b c d e f g h i j

B-tree (con.t) – 加入 98 ，由於 j 節點已有 m–1 個鍵值 ( 即 4 個 ) ，因此必須 將 j 節點劃分為二， j 、 k ，然後選出 K = K 3 = 90 ，並組 成（ 90,k ）加入 c 節點 50 20, 40 60, 70, 80, 90 5,1025,30 45,48 53,54 62,67 72,76 95,98 a b c d e f g h ij 85,88 k

B-tree (con.t) – 加入 91 – 加入 , 40 60, 70, 80, 90 5,1025,30 45,48 53,54 62,67 72,76 91,95,98 a b c d e f g h ij 85,88 k 50 20, 40 60, 70, 80, 90 5,1025,30 45,48 53,54 62,67 72,76 91,93,95,98 a b c d e f g h ij 85,88 k

B-tree (con.t) – 加入 99 ，以同樣的方法將 k 劃分為 k ， l 並組成（ 95, l ） 加入 c 節點，由於 c 節點已有 m–1 個鍵值，若再加入一 鍵值勢必也要劃分 c 節點為二，其為 c 、 m ，並將（ 80, m ）加入其父節點 a 50, 80 20, 40 5,1025,30 45,48 53,54 62,67 72,76 98,99 a b c d e f g h i j 85,88 k 60, 70 90, 95 91,93 l m

B-tree (con.t) B-tree 的刪除方法 – 一為刪除的節點是樹葉節點 – 二為刪除的節點為非樹葉節點 – 我們以 B-tree of order 5 如下圖來說明。假設已找到相關 的節點 P 50 20, 30 60, 80 10,1525,26 35,40,45 55,59 65,70,75 85,90

B-tree (con.t) 刪除的節點是樹葉節點 – 刪除鍵值 X 後，若 P 節點還有大於或等於 –1 個鍵值， 則刪除完畢，因為尚符合 B-tree 的定義，此處的 m 為 5 。 如將下圖的鍵值 70 刪除，結果為下圖所示： 50 20, 30 60, 80 10,1525,26 35,40,45 55,59 65,75 85,90

B-tree (con.t) – 刪除鍵值 X 後，若 P 節點的鍵值小於 –1 個，其不符合 B-tree 的定義，因此必須調整。我們分四種情況說明： (1) 找右邊最近的兄弟節點 p’ ，若 p’ 尚有大於或等於 個 鍵值，則將取出 P 的父節點 P f 中最大的鍵值放入 P ，然 後從 p’ 節點取出最小的鍵值放入 P 的父節點 P f ，如將下 圖的鍵值 26 刪除 50 20, 35 60, 80 10,1525,30 40,45 55,59 65,70,75 85,90 P P' PfPf

B-tree (con.t) (2) 若在 P 節點右邊找不到有一節點含有大於或等於 個鍵 值時，則找其左邊的兄弟節點，若有一左兄弟節點 q‘ ，則從 P 的父節點 P f 取出最小鍵值放入 P ，然後從 q‘ 中取出最大 的鍵值放入 P 的父節點 P f 。若欲刪除 85 ，情形如下圖所示： 50 20, 35 60, 75 10,1525,30 40,45 55,59 65,70 80,90 P q' PfPf

B-tree (con.t) 刪除的節點為非樹葉節點 – 假若 P 節點的型態為 n,A 0,(K 1,A 1 ), (K 2,A 2 ),…,(K n,A n ) ， 其中 K i = x ， 1 ≦ i ≦ n 。刪除 k 時找尋其右子樹中的最左 邊的樹葉節點 P’ ，在 P’ 中找一個最小值 y ，將 y 代替 K i 值，如下圖，注意！也可以找尋其左子樹中最右邊的樹 葉節點 P’ ，在 P’ 中找一最大值 y ，將 y 代替 K i 值 50 20, 30 10,1525,26 35,40,45 52,55,59 85,90 i g f e d b c 65,70,75 60, 80 h

B-tree (con.t) – 若刪除 50 ，找到 P’ 節點為 g ，從中取出最小值 52 ，並 代替 , 30 10,1525,26 35,40,45 55,59 85,90 i g f e d b c 65,70,75 60, 80 h a

B-tree (con.t) – 若此時再刪除 52 ，由於從 P‘ 節點 ( 即 g) 找到鍵值 55 代替 52 後，其鍵值數小於 –1 個鍵值，此時就好比刪除樹 葉節點 g 的情形，可向其右兄弟節點 h 借一鍵值 65 （因為 在節點的鍵值個數大於 –1 ），其結果如下所示： a 55 20, 30 10,1525,26 35,40,45 59,60 85,90 i g f e d b c 70,75 65, 80 h

B-tree (con.t) – 若繼續刪除 55 ，找到 P‘ 節點為 g ，將最小值 59 代替 55 ， 由於其鍵值數小於 –1 個鍵值，且其兄弟節點 h 也沒有 大於 –1 的鍵值，故將 g 、 h 與 c 的鍵值 65 合併於 g' 節點， 結果如下圖所示： 59 20, 30 10,1525,26 35,40,45 60,65,70,75 85,90 i g' f e d b c 80 a

B-tree (con.t) – 此時 c 節點的鍵值數小於 –1 ，且其兄弟節點的鍵值數 不大於 –1 ，故將 b 、 c 與 a 節點合併為 a' ，結果如下： 20, 30, 59, 80 10,1525,26 35,40,45 60,65,70,75 85,90 i g f e d a'

B-tree (con.t)