第12章 樹狀搜尋結構 （Search Trees）

Presentation on theme: "第12章 樹狀搜尋結構 （Search Trees）"— Presentation transcript:

1 第12章 樹狀搜尋結構 （Search Trees）
12-1 再談二元搜尋樹 12-2 AVL高度平衡二元樹 12-3 M路搜尋樹 12-4 B樹

2 12-1 再談二元搜尋樹-說明 「二元搜尋樹」（Binary Search Tree）除了可以使用中序走訪來排序資料外，如同此名，它的主要目的是進行資料搜尋。例如：一棵二元搜尋樹，如下圖所示：

3 12-1 再談二元搜尋樹-情況 二元搜尋樹搜尋法在搜尋資料時，只需將資料與根節點比較，此時有二種情況，如下所示：
資料比較大：往右子樹繼續搜尋。 資料比較小：往左子樹繼續搜尋。 重覆上述比較，直到找到節點資料與找尋鍵值相等，或沒有找到。

4 12-1 再談二元搜尋樹-遞迴函數 BSTreeSearch()函數是一個遞迴函數，如下所示：
int BSTreeSearch(BSTree ptr, int d) { if ( ptr != NULL ) { /* 終止條件 */ if ( ptr->data == d ) /* 找到了 */ return 1; else if ( ptr->data > d ) /* 往左子樹找 */ return BSTreeSearch(ptr->left, d); else /* 往右子樹找 */ return BSTreeSearch(ptr->right, d); } else return 0; /* 沒有找到 */ }

5 12-1 再談二元搜尋樹-執行效率 二元樹搜尋法的效率如果不考慮建立二元搜尋樹的時間，其執行效率與二元搜尋法相同是O(Log n)。

6 12-2 AVL高度平衡二元樹 AVL樹的基礎 AVL樹的節點插入 AVL樹的節點刪除

7 AVL樹的基礎-說明 如果是一棵極度不平衡的二元搜尋樹，為了避免此特殊情況，需要重新平衝二元樹，其中最著名的方法是1962年由Adelson-Velskii和Landis提出的平衡演算法，可以建立高度平衡二元樹（Height Balanced Binary Trees），也稱為AVL樹。 AVL樹是一棵符合特殊條件的二元搜尋樹，它也是一棵平衡樹（Balanced Trees），即每一個節點的左右子樹，幾乎擁有一樣的樹高（Height）。 其特性如下所示： 空子樹的樹高是-1。任何一個節點的右子樹的樹高減左子樹的樹高值只能是-1、0或1，稱為平衡因子（Balanced Factor）。

8 AVL樹的基礎-圖例 AVL樹的每一個節點的左右子樹的樹高最多只是差1。例如：一棵AVL樹，如下圖所示：

9 12-2-1 AVL樹的基礎-標頭檔 01: /* 程式範例: Ch12-2.h */
02: struct Node { /* AVL樹的節點宣告 */ 03: int data; /* 儲存節點資料 */ 04: struct Node *left; /* 指向左子樹的指標 */ 05: struct Node *right; /* 指向右子樹的指標 */ 06: int height; /* 子樹的最大樹高值 */ 07: }; 08: typedef struct Node AvlNode; /* AVL樹節點的新型態 */ 09: typedef AvlNode *AvlTree; /* AVL樹鏈結的新型態 */ 10: AvlTree head = NULL; /* AVL樹根節點的指標 */ 11: /* 抽象資料型態的操作函數宣告 */ 12: extern void createAvlTree(int len, int *array); 13: extern AvlTree insertAvlNode(int data, AvlTree ptr); 14: extern int deleteAvlNode(int data); 15: extern void printAvlTree();

10 AVL樹的節點插入-說明 函數createAvlTree()使用for迴圈走訪參數的陣列元素，然後依序呼叫insertAvlNode()函數將一個一個陣列元素的節點資料插入AVL樹。 函數insertAvlNode()是一個遞迴函數，使用類似建立二元搜尋樹的方式來插入節點，當插入節點的平衡因子大於1或小於-1時，即造成不平衡，此時是使用旋轉來重新調整成平衡樹。

11 12-2-2 AVL樹的節點插入-種類 LL型：插入左子樹（Left Subtree）的左子節點（Left Child）。
RR型：插入右子樹（Right Subtree）的右子節點（Right Child）。 LR型：插入左子樹（Left Subtree）的右子節點（Right Child）。 RL型：插入右子樹（Right Subtree）的左子節點（Left Child）。

12 12-2-2 AVL樹的節點插入-單旋轉(說明) LL和RR型的不平衡情況屬於同一型，只是左右相反。

13 12-2-2 AVL樹的節點插入-單旋轉(LL型)

14 12-2-2 AVL樹的節點插入-單旋轉(RR型)
RR型和LL型左右相反，例如：在AVL樹插入節點80後，就產生RR型的不平衡情況，此時是將節點40向左轉，如下圖所示：

15 12-2-2 AVL樹的節點插入-雙旋轉(說明) LR和RL型的不平衡情況屬於同一型，只是左右相反。

16 12-2-2 AVL樹的節點插入-雙旋轉(LR型)
在LR型最左邊在插入節點30後，就超成50、20和40的LR型不平衡情況，此時我們需要執行兩次旋轉，首先是節點20的RR型向左轉，然後是節點50的LL型向右轉，

17 12-2-2 AVL樹的節點插入-雙旋轉(RL型)
RL型和LR型左右相反，換句話說，它是先執行LL型向右轉，然後才是RR型的向左轉，如下所示： ptr->right = singleRotateLL(ptr->right); return singleRotateRR(ptr);

18 12-2-2 AVL樹的節點插入-演算法 AVL樹節點插入的演算法是遞迴函數，遞迴函數insertAvlNode()的步驟，如下所示：
Step 1：使用第7章二元搜尋樹的節點插入的遞迴版來插入節點。 Step 2：從插入節點往回至根節點依序更新左右子樹的最高樹高，並且計算節點的平衡因子，如果不平衡值為2或-2，其處理方式如下所示： (1) 如果是LL或LR型的不平衡因子-2，判斷後進行單或雙旋轉。 (2) 如果是RR或RL型的不平衝因子2，判斷後進行單旋或雙旋轉。

19 12-2-3 AVL樹的節點刪除-演算法 AVL樹節點刪除的AVL樹節點刪除的演算法步驟，如下所示：
Step 1：使用第7章二元搜尋樹的節點刪除方法來刪除節點。 Step 2：以遞迴方式來更新AVL樹節點的最高樹高，並且計算平衡因子，如果不平衡，其處理方式如下所示： (1) 如果是LL或LR型的不平衡，判斷後進行單或雙旋轉。 (2) 如果是RR或RL型的不平衝，判斷後進行單旋或雙旋轉。

20 12-2-3 AVL樹的節點刪除- deleteAvlNode()函數(說明)
函數deleteAvlNode()首先呼叫deleteBSTreeNode()函數來刪除指定的節點資料，在刪除後呼叫 rebuildAVL()函數來重建AVL樹。 例如：當刪除節點90後，在重新計算平衡因子時，可以發現節點80的平衡因子是-2，節點80、60和70屬於LR型的不平衡情況，換句話說，我們可以執行雙旋轉doubleRotateLR()函數來重建AVL樹。

21 12-2-3 AVL樹的節點刪除- deleteAvlNode()函數(圖例)

22 12-3 M路搜尋樹-節點結構 M路搜尋樹（M-way Search Trees）是指樹的每一個節點都擁有至多M個子樹和M-1個鍵值，鍵值是以遞增方式由小至大來排序，其節點結構如下圖所示：

23 12-3 M路搜尋樹-節點結構宣告 四路搜尋樹的節點結構，最多有4個子節點，其結構宣告如下所示： struct Node {
int count; /* 鍵值數 */ int key[3]; /* 鍵值陣列 */ struct Node *link[4]; /* 連結子節點的指標 */ };

24 12-3 M路搜尋樹-節點結構宣告說明 結構最多有4個指標可以指向子節點，且擁有3個鍵值。
節點的第1個欄位是鍵值數是成員count，以M路搜尋樹來說，鍵值數為：count <= M - 1，即鍵值數最多是M個子節點減一，以此例是4個子節點和3個鍵值key[0]、key[1]和key[2]，其排列方式是遞增排序：key[0] < key[1] < key[2]。

25 12-3 M路搜尋樹-範例 例如：四路搜尋樹的每一個節點最多有3鍵值和4個子樹，如下圖所示：

26 12-3 M路搜尋樹-步驟 在四路搜尋樹搜尋資料，就是從根節點開始來進行比較，其步驟如下所示：
與節點的鍵值比較，如果在2個鍵值之間，就表示位在鍵值中指標所指的子樹，例如：搜尋76，就是位在根節點47和82間指標的子樹。 只需重複上述比較，就可以在M路搜尋樹搜尋指定的鍵值。

27 12-4 B樹 B樹的基礎 在B樹插入鍵值 在B樹刪除鍵值

28 B樹的基礎-說明 B樹（B-Tree）屬於一種樹狀搜尋結構，它是擴充自二元搜尋樹的一種平衡的M路搜尋樹。M為B樹的度數（Order），由Bayer和McCreight提出的一種平衡的M路搜尋樹，其定義如下所示： B樹的每一個節點最多擁有M個子樹。 B樹根節點和葉節點之外的中間節點，至少擁有ceil(M/2)個子節點，ceil()函數可以大於等於參數的最小整數，例如：ceil(4) = 4、ceil(4.33) = 5、ceil(1.89) = 2和ceil(5.01) = 6。 B樹的根節點可以少於2個子節點。葉節點至少擁有ceil(M/2) - 1個鍵值。 B樹的所有葉節點都位在樹最底層的同一階層（Level），換句話說，從根節點開始走訪到各葉節點所經過的節點數都相同，它是一棵相當平衡的樹狀搜尋結構。

29 B樹的基礎-範例 例如：一棵度數5的B樹，所有中間節點至少擁有ceil(5/2) = 3個子節點（即至少2個鍵值），最多5個子節點（4個鍵值），葉節點至少擁有2個鍵值，最多為4個鍵值，如下圖所示：

30 在B樹插入鍵值-1 在B樹插入鍵值是使用搜尋方式來找尋新鍵值的插入位置，如果找到的節點有空間就直接插入鍵值，若沒有空間，就需要以中間的鍵值來進行分割，並且將中間值移至父節點。例如：以插入方式來建立一棵度數5的B樹，依序新增鍵值3、14、7和1，如下圖所示：

31 在B樹插入鍵值-2 左邊是插入的節點，可以看到節點的鍵值由小至大排序。接著插入鍵值8，此時節點鍵值已滿沒有空間，我們需要進行分割，以中間值7來分割，保留鍵值1和3的左子節點，新增根節點7和右子節點鍵值8和14。 然後依序插入鍵值5、11和17，這些鍵值並不需要分割節點，如下圖所示：

32 在B樹插入鍵值-3 左邊可以看到5是插入左子節點，11和17是插入右子節點。接著插入鍵值13，因為右子節點已經沒有空間，所以找到中間值13且移至父節點，就可以分割成2個子節點8、11和14、17。 然後依序插入鍵值6、23、12和20，這些鍵值並不需要分割節點，如下圖所示：

33 在B樹插入鍵值-4 左邊可以看到6是插入左子節點，12是插入中間的子樹，20和23是插入右子節點。接著插入鍵值26，因為右子節點已經沒有空間，所以找到中間值20且移至父節點，就可以分割成2個子節點14、17和23、26。 然後插入鍵值4，因為最左的子節點已經沒有空間，所以找到中間值4且移至父節點，就可以分割成2個子節點1、3和5。

34 在B樹插入鍵值-5

35 在B樹插入鍵值-6 接著依序鍵值16、18、24和25，這些鍵值並不需要分割節點。最後插入鍵值19，因為14、16、17和18節點已滿，所以找到中間值17且移至父節點。 此時父節點（即根節點）也已滿沒有空間，所以取得中間值13新增為根節點，然後分割成2個子節點4、7和17、20，就完成第12-4-1節的B樹範例。

36 在B樹刪除鍵值-說明 在B樹刪除鍵值可以分成幾種情況，如果欲刪除鍵值所在節點的鍵值數夠多，直接刪除即可，若鍵值數不足，就需要和兄弟節點借鍵值或進行合併。

37 12-4-3 在B樹刪除鍵值-情況1 情況1：刪除葉節點的鍵值且鍵值數足夠
如果在B樹刪除的是葉節點的鍵值，而且該節點的鍵值數足夠，直接刪除即可，例如：刪除上一節建立B樹的鍵值8，因為該節點有3個鍵值，直接刪除即可，此時節點的鍵值就只剩下11和12，如下圖所示：

38 12-4-3 在B樹刪除鍵值-情況2 情況２：刪除中間節點鍵值且子節點的鍵值數足夠

39 12-4-3 在B樹刪除鍵值-情況3(1) 情況3：葉節點的鍵值數不足

40 在B樹刪除鍵值-情況3(2) 左邊在刪除鍵值18後，因為鍵值數不足，在檢查後，可以向右兄弟節點借一個鍵值，所以將父節點鍵值23搬入，下一個鍵值24成為父節點的新鍵值。 接著刪除節點16，因為鍵值數不足且左右兄弟節點也沒有多餘鍵值，所以合併14、父鍵值17、兄弟節點的19、23成為左子節點，如下圖所示：