第 八 章 高等樹 課程名稱：資料結構 授課老師：________ 2019/4/28

本章學習目標 1.讓讀者了解進階的各種樹狀結構。 2.介紹各種高等樹的建立、加入及刪除方法。 2019/4/28

本章內容 8-1 引線二元樹(Threaded Binary Tree) 8-2 堆積(累堆)樹 ( Heap Tree ) 8-3 雙向堆積樹 ( DEAPS ) 8-4 高度平衡樹 ( AVL Tree ) 8-5 B-tree 8-6 B+-tree 8-7 霍夫曼樹(Huffman Tree) 8-8 2-3樹 8-9 2-3-4 樹 8-10 紅-黑樹 ( Red-Black tree ) 2019/4/28

8-1 引線二元樹 (Threaded Binary Tree) 【定義】 由於二元樹實際上用來指向左右兩個節點的指標只有n-1個鏈結，所以有n+1個指標都是空鏈結。因此，二元樹的空鏈結浪費了將近一半，引線二元樹就是把這些空的鏈結加以利用，用以指向樹的其他節點，而這些鏈結就稱為「引線」(thread)，而這種二元樹就稱為引線二元樹(Threaded Binary Tree)。如下圖中有7個節點，但是有8個空鏈結。如圖8-1所示。 2019/4/28

2. 由於充份使用空鏈結，所以避免鏈結浪費的情形。 3. 任何一個節點都容易找出它的中序後繼者與中序先行者。 【缺點】 【優點】 1. 不需要使用堆疊，就可以做中序追蹤。 2. 由於充份使用空鏈結，所以避免鏈結浪費的情形。 3. 任何一個節點都容易找出它的中序後繼者與中序先行者。 【缺點】 1. 插入和刪除的演算法比較複雜。 2. 彈性比較小，例如子樹不能共享。 2019/4/28

【引線二元樹之節點結構】 引線二元樹的節點結構，除了原有二元樹的欄位外，為了區分引線和實際指標的不同，必須額外加上兩個欄位標示指標的用途。 說明： 1. Left Thread： 當為True或1時，則代表Lchild為引線，指向中序追蹤的前一個節點。 當為False或0時，則代表Lchild為指標，指向左子樹的指標。 2. Right Thread： 當為True或1時，則代表Rchild為引線，指向中序追蹤的後一個節點。 當為False或0時，則代表Rchild為指標，指向右子樹的指標。 2019/4/28

【引線二元樹之表示】 圖8-2 引線二元樹之表示 2019/4/28

【將二元樹轉換為引線二元樹的步驟】 1. 先求二元樹的中序追蹤結果。 2. 將二元樹的所有空鏈結改成引線。 3. 左邊的引線指向中序追蹤的前一個節點，而右邊的引線指到 中序追蹤的後一個節點。 2019/4/28

【牛刀小試】在下圖中給予一個二元樹，請繪出其Thread B.T. 【解答】 1. 先寫出中序式: B C A F D E 2. 引線二元樹表示如下： 說明： 節點C的左引線指向其中序前行者(節點B)，右引線指向其中序後繼者(節點A)；節點E的左引線指向中序前行者(D)，而右引線指向其中序後繼者，由於該節點不存在，故未有所指，以此類推。 2019/4/28

8-2 堆積(累堆)樹 ( Heap Tree )  堆積樹（Heap Tree）是一種完整二元樹，若堆積樹的父節點小於子節點，則稱之為最小堆積樹(Min Heap Tree)，若父節點大於子節點，則稱之為最大堆積樹(Max Heap Tree)。其說明如下： 2019/4/28

一、最大堆積樹(Max Heap Tree) 指每一個節點的鍵值必須大於它的子節點的鍵值。其特性如下： 1. 每一棵Max Heap是一棵完整二元樹。 2. 樹根的鍵值大於左子樹與右子樹的鍵值。 3. 其左子樹與右子樹亦是 Max Heap。如圖8-3所示： 圖8-3最大堆積樹 2019/4/28

【作法】 1. 先將資料建立成完整二元樹。 2. 在完整二元樹中找出最大值並依序移到樹根。 3. 在完整二元樹中找出次大的值，並與其上一層的父節點比較， 如果大於時，則交換，否則，不須作任何交換。 4.重覆步驟3，直到全部的節點的鍵值大於它的左子樹與右子樹的 鍵值，即可成一棵最大堆積樹。 2019/4/28

二、最小堆積樹(Min Heap Tree) 指每一個節點的鍵值必須小於它的子節點的鍵值。其特性如下： 1. 每一棵Min Heap是一棵完整二元樹。 2. 樹根的鍵值小於左子樹與右子樹的鍵值。 3. 其左子樹與右子樹亦是 Min Heap。如圖8-4所示： 圖8-4最小堆積樹 2019/4/28

【作法】 1. 先將資料建立成完整二元樹。 2. 在完整二元樹中找出最小值並依序移到樹根。 3. 在完整二元樹中找出次小的值，並與其上一層的父節點比較， 如果小於時，則交換，否則，不須作任何交換。 4.重覆步驟3，直到全部的節點的鍵值小於它的左子樹與右子樹的 鍵值，即可成一棵最小堆積樹。 2019/4/28

【實例】請依照下列資料先建立二元樹，再轉換成最大堆積樹 (Max Heap Tree) 38, 78, 10, 65, 19, 86, 33, 72, 20 【解答】 步驟一：建立完整二元樹 2019/4/28

步驟二：在完整二元樹中找出最大值86，依序移到樹根(86與10交換， 再將與38交換) 2019/4/28

步驟三：在完整二元樹中找出第二大的值78，此時78鍵值小於父節點86。 因此，不須作任何交換。 步驟四：最後在完整二元樹中找出第三大的值72，與其上一層的父節點比 較，比65大，所以65與72位置交換。直到全部的節點的鍵值大於 它的左子樹與右子樹的鍵值，即可成一棵最大堆積樹。 2019/4/28

【老師上課動態展示】檔案在附書光碟中。 2019/4/28

【實例】請依照下列資料先建立二元樹，再轉換成最小堆積樹 (Min Heap Tree) 38, 78, 10, 65, 19, 86, 33, 72, 20 【解答】 步驟一：建立完整二元樹 2019/4/28

步驟二：在完整二元樹中找出最小值10，依序移到樹根(38與10交換) 2019/4/28

步驟三：在完整二元樹中找出第二小的值19，與其上一層的父節點 比較，比78小，所以19與78位置交換。 2019/4/28

步驟四：在完整二元樹中找出第三小的值20，與其上一層的父節點 比較，比65小，所以20與65位置交換。 2019/4/28

步驟五：最後在完整二元樹中找出第四小的值33，與其上一層的父節點 比較，比38小，所以33與38位置交換。直到全部的節點的鍵值 小於它的左子樹與右子樹的鍵值。即可成一棵最小堆積樹。 2019/4/28

8-2.1 堆積樹加入節點 堆積樹加入節點的規則如下： 1.遵循Complete Binary Tree的規則 2.進行調整(交換) 8-2.1 堆積樹加入節點  堆積樹加入節點的規則如下： 1.遵循Complete Binary Tree的規則 2.進行調整(交換) 2019/4/28

2019/4/28

8-2.2 堆積樹刪除節點 堆積樹刪除節點的規則如下： 1. 刪除根節點 2. 在左右子樹中選擇最後一個節點來補位 3. 進行調整 8-2.2 堆積樹刪除節點  堆積樹刪除節點的規則如下： 1. 刪除根節點 2. 在左右子樹中選擇最後一個節點來補位 3. 進行調整 2019/4/28

【實例】請在下列的最大堆積樹中，刪除一個節點86。 2019/4/28

【牛刀小試】 下圖為最大堆積樹，若將88節點刪除，該堆積樹最後結果為何？ 2019/4/28

2019/4/28

8-2.3 最小-最大堆積樹 (Min-Max Heaps Tree) 【定義】最小-最大堆積樹(Min-Max Heaps Tree)是一個完整二元樹。此二元樹是交替的階層方式呈現，分別為最小階層 ( min level ) 和最大階層 ( max level ) ，其中樹根為最小鍵值。如圖8-5所示。 圖8-5 最小-最大堆積樹 2019/4/28

1. 階度1的鍵值 ＜ 階度3的鍵值 ＜ 階度5的鍵值…＜ 階度n的鍵值(n為奇數) 以上最小-最大堆積樹的建立規則為： 1. 階度1的鍵值 ＜ 階度3的鍵值 ＜ 階度5的鍵值…＜ 階度n的鍵值(n為奇數) 2. 階度2的鍵值 ＞ 階度4的鍵值 ＞ 階度6的鍵值…＞ 階度n的鍵值(n為偶數) 2019/4/28

【實例】請問下列的二元樹是否為最小-最大堆積樹呢？為什麼？ 【解答】 (1)此棵二元樹不是最小-最大堆積樹。 (2)因為階度3的右子樹之鍵值5比階度1的樹根10小，因此， 它是違反最小-最大堆積樹的建立規則之第1條。 2019/4/28

8-2.4 最小-最大堆積樹中加入節點 最小-最大堆積樹加入節點的規則如下： 1.遵循Complete Binary Tree的規則 8-2.4 最小-最大堆積樹中加入節點  最小-最大堆積樹加入節點的規則如下： 1.遵循Complete Binary Tree的規則 2.進行調整(遵循Min-Max Heaps Tree的規則) 2019/4/28

2019/4/28

8-2.5 最小-最大堆積樹中刪除節點 最小-最大堆積樹刪除節點的規則如下： 1. 刪除根節點 2. 在左右子樹中選擇最後一個節點來補位 8-2.5 最小-最大堆積樹中刪除節點  最小-最大堆積樹刪除節點的規則如下： 1. 刪除根節點 2. 在左右子樹中選擇最後一個節點來補位 3. 尋找根節點以下的最小鍵值與根節點交換 4. 進行調整 2019/4/28

2019/4/28

8-3 雙向堆積樹 ( DEAPS ) 【定義】Deap 是一個完整二元樹，它是可以為空，若不為空，則必須滿足下列特性： (１)樹根不包含任何的元素。 (２)左子樹為最小堆積樹(Min Heap)。 (３)右子樹為最大堆積樹(Max Heap)。 (４)左子樹節點鍵值必須要小於右子樹 節點鍵值。如圖8-6所示。 2019/4/28

8-3.1 雙向堆積樹加入節點 雙向堆積樹加入節點的規則如下： 1.遵循Complete Binary Tree的規則 2.左右子樹相對位置比較鍵值大小，若i>j時，就要互相交換 3.進行調整 2019/4/28

2019/4/28

8-3.2 雙向堆積樹刪除節點 雙向堆積樹刪除節點的規則如下： 1.當刪除節點為最小鍵值時： (1)刪除左子樹的樹根。 (2)將Deap的最後一個節點上拉補位到左子樹的樹根，並且也要 保持完整二元樹。 (3)將該節點往下調整為最小堆積樹的樹葉節點。若發現右子樹 中與其相對位置的節點小於該節點時，則必須要進行交換。 2019/4/28

(2)將Deap的最後一個節點上拉補位到右子樹的樹根，並且也要 保持完整二元樹。 (3)將該節點往下調整為最大堆積樹的樹葉節點。若發現左子樹 2.當刪除節點為最大鍵值時： (1)刪除右子樹的樹根。 (2)將Deap的最後一個節點上拉補位到右子樹的樹根，並且也要 保持完整二元樹。 (3)將該節點往下調整為最大堆積樹的樹葉節點。若發現左子樹 中與其相對位置的節點大於該節點時，則必須要進行交換。 2019/4/28

2019/4/28

2019/4/28

8-4 高度平衡樹 ( AVL Tree ) 在前面章節中所介紹的二元搜尋樹，如果左子樹與右子樹的高度能夠維持在平衡的情況時，則其搜尋時間會減低。因此，在本單元中將介紹AVL Tree的平衡樹，就是調整二元搜尋樹的左右子樹的高度，來達到二元樹的平衡，因此，我們稱AVL Tree又稱為高度平衡二元搜尋樹，而平衡二元樹(Balanced Binary Tree)的觀念是由Adelson-Velskii與Landis兩位專家提出，所以就稱為AVL樹。 2019/4/28

基本上，AVL樹必須要合乎下列兩個條件： 1.是一種二元搜尋樹。 2.高度須保持平衡狀態。 2019/4/28

【定義】為一棵高度平衡的二元搜尋樹，可以為空，若不為空， 則必須滿足： 1. TL 和 TR 為高度平衡樹。 2. | hL - hR | <= 1，其中 hL 和 hR 分別為 TL 和 TR 的高度。 如圖8-7所示。 2019/4/28

8-4.1 平衡因子(Balance Factor) 【定義】在二元樹中，一個節點 T 的平衡因子 ( Balance Factor ;BF) 的定義為 hL - hR ，其中  hL和hR  為T 的左子樹和右子樹的高度。對 AVL 樹中的任一節點 T 而言， BF(T) = 0 , -1 或 1等三種情況。如圖8-8所示。 2019/4/28

在圖8-8之圖(a)中，每一個內部節點的左子樹與右子樹的高度相差最多是 1，因此是AVL樹。而在圖8-8之圖(b)中，因為節點A的左子樹的高度為3，右子樹的高度為1，所以相差2。 在圖8-8之圖(a)與圖(b)中，每一個節點上面的數字我們稱為該節點的「平衡因子」( Balance Factor；BF)。其計算方式為：此節點的左子樹高度(hL)減掉右子樹高度(hR)。所以在AVL樹中，每一個節點的平衡因子均為0 , -1 或 1 2019/4/28

8-4.2 AVL 樹的不平衡點調整之四種型式 我們在進行AVL樹的加入與刪除動作時，往往會造成不平衡狀態， 因此，我們必須要加以調整，最後必須要保持平衡狀態。我們將不 平衡狀態分為四種： (一) LL型(Left-Left) (二)RR型(Right-Right) (三) LR型(Left-Right) (四)RL型(Right-Left) 2019/4/28

2019/4/28

(一)LL型(Left-Left) 1.新節點C加入到節點B的左子樹 2.將中間鍵值(B節點)往上拉，小的放左邊(C節點)，大的順時針旋轉 後，放右邊(A節點)。 2019/4/28

2019/4/28

(２)RR型(Right-Right) 1.新節點C加入到節點B的右子樹 2.將中間鍵值(B節點)往上拉，大的放右邊(C節點)，小的逆時針旋轉後，放左邊(A節點)。 2019/4/28

2019/4/28

(３)LR型(Left-Right) 1.新節點C要被加入到A節點的左兒子（B節點）的右子樹 2.將中間鍵值(C節點)往上拉，大的放在C節點的右邊，小的放在C 節點的左邊。 2019/4/28

2019/4/28

(４)RL型(Right-Left) 1.新節點C要被加入到A節點的右兒子（B節點）的左子樹 2.將中間鍵值(C節點)往上拉，大的放在C節點的右邊，小的放在C 節點的左邊。 2019/4/28

【老師上課動態展示】檔案在附書光碟中。 2019/4/28

2019/4/28

8-4.3 AVL Tree 之平衡調整步驟 1. 找出關鍵路徑，計算路徑上每一個節點的平衡因子。 2. 從樹根開始，找到最後一個平衡因子為 2 以上的節點， 稱之為關鍵節點。 3. 決定調整方式（LL, RR, LR, RL）。 4. 進行調整，必須保持二元搜尋樹的定義。 2019/4/28

【實例】依序輸入5個資料分別為：2, 4, 6, 8, 10來建立二元搜尋樹 及平衡二元樹。 【解答】 hL=1並且hR=5，所以| hL - hR | = | 1-5 | >=1 所以，產生斜曲樹的現象，因此，5筆資料最多需要比較5次才能找到。 2019/4/28

2019/4/28

8-5 B-tree 二元搜尋樹中每個節點最多有2個子樹，而在m-way搜尋樹中，每一個節點最多有m個子樹，而以上這兩種搜尋樹的使用時機是當電腦所需要處理的資料量逐漸變大，使記憶體的容量無法容納所要處理的資料時，此時就必須藉由輔助記憶體來協助處理，也就是說B-tree就是用來處理這些外部搜尋的一種資料結構。 2019/4/28

它是一平衡的m-way 搜尋樹，可以為空，若不為空，則滿足： ①樹根至少有2個子節點。 所謂「B-tree」是指order為m的一種m-way搜尋樹，在 order 為 m 的 B - tree 中，每一個節點的鍵值數目少於 m - 1 個。因此，必須具備下列的性質： 它是一平衡的m-way 搜尋樹，可以為空，若不為空，則滿足： ①樹根至少有2個子節點。 ②除了樹根及樹葉節點之外，其餘節點的分支度(Degree)介於 及m之間。 ③所有的樹葉節點皆位於同一階層中。如圖8-9所示。 在下面兩個圖之中圖8-10不屬於B-tree，因為其終端節點不在同一階層。 2019/4/28

一、「插入」新節點到原有的B-Tree結構 在B-tree of order m 之插入 X動作，其步驟如下： 步驟2：檢查該節點是否有溢位(Overflow)現象 (1)Case 1: 沒有溢位即(key數≦ m-1)，則直接加入。 (2)Case 2: 有溢位即(key數≧ m) 則進行「節點分裂」 2019/4/28

當新加入的鍵值使該節點的鍵值數目大於 m - 1 個時，該節點便需進行分裂。其分裂的方式如下： 二、節點分裂的規則 當新加入的鍵值使該節點的鍵值數目大於 m - 1 個時，該節點便需進行分裂。其分裂的方式如下： 1. 找出該鍵值數目大於 m - 1 的節點之中間鍵值，即K 2. 將該鍵值提至該節點的父節點之中。 2019/4/28

二、節點分裂的規則<續> 其方法如圖8-11所示： 2019/4/28

2019/4/28

2019/4/28

2019/4/28

2019/4/28

【老師上課動態展示】檔案在附書光碟中。 2019/4/28

(一)刪除的節點是樹葉節點 ( leaf node ) (二)刪除的節點為非樹葉節點 ( non - leaf node ) 三、從B-Tree結構「刪除」某些節點 B - tree 的刪除分為兩個部份： (一)刪除的節點是樹葉節點 ( leaf node ) (二)刪除的節點為非樹葉節點 ( non - leaf node ) B-tree of order m 之刪除X動作，其步驟如下： 步驟一：尋找 X 之所在節點 並且分成下列兩種情況來討論： 情況 1：X位於樹葉節點 情況2：X不是位於樹葉節點 2019/4/28

2019/4/28

<1>以X的右子樹中最小鍵值取代X 或<2>以X的左子樹中最大鍵值取代X 並且返回步驟二：後續處理。 則： <1>以X的右子樹中最小鍵值取代X 或<2>以X的左子樹中最大鍵值取代X 並且返回步驟二：後續處理。 2019/4/28

2019/4/28

2019/4/28

2019/4/28

2019/4/28

試依序畫出由下列資料所形成的 order為3的B-Tree。 20, 40, 10, 30, 15, 35 提示：每個節點最大的分支度則為m(最多有m個兒子)， 最多的Key數為m-1。 【解法】 2019/4/28

2019/4/28

2019/4/28

2019/4/28

8-6 B+-tree 是B-tree的改良，它將所有鍵值存於葉節點上，而其他非葉節點的上面各層只含有索引和鍵結指標。且B+-tree的內部節點與葉節點的結構不同。 2019/4/28

一、內部節點 2019/4/28

二、葉節點 2019/4/28

試依序畫出由下列資料所形成的 order為3的B+-Tree 8, 5, 1, 7, 3, 12, 9, 6 【範例】 試依序畫出由下列資料所形成的 order為3的B+-Tree 8, 5, 1, 7, 3, 12, 9, 6 2019/4/28

2019/4/28

2019/4/28

2019/4/28

8-7 霍夫曼樹(Huffman Tree) 【定義】 霍夫曼樹(Huffman Tree)是二元搜尋樹的延伸應用，它是霍夫曼(D.A.Huffman)的編碼模式，在霍夫曼編碼當中將資料視為有權重的葉子，再將各資料依出現頻率及次數加以分類，構築出一個叫<霍夫曼樹>的樹狀資料結構，然後再加以分配資料的位元列。 2019/4/28

【特性】 1. 霍夫曼樹可用來編碼，也可用來解碼以達成資料壓縮的目的。    1. 霍夫曼樹可用來編碼，也可用來解碼以達成資料壓縮的目的。    2. 根據資料出現頻率多寡來建造的二元樹 。    3. 霍夫曼樹的樹葉節點用以儲存資料元素 。    4. 若該元素出現頻率愈高則從根節點到該元素所經過的節點路徑 愈短，反之則愈長。 2019/4/28

【霍夫曼樹的構成】 (1)從資料中找出兩個出現頻率最低者，利用樹狀資料結構來表現之，並將 兩者出現頻率的子樹合併為新資料出現的頻率。     當然在霍夫曼編碼當中，首先必須求出霍夫曼樹，而霍夫曼樹的產生方式如下所示： (1)從資料中找出兩個出現頻率最低者，利用樹狀資料結構來表現之，並將 兩者出現頻率的子樹合併為新資料出現的頻率。 (2)將(1)製作出來的資料值和下一個出現頻率最低者來做合併處裡，一直重 複這個動作 ，直到所有節點都被放到霍夫曼樹為止。     霍夫曼樹被求出之後，接下來就順著樹枝位元列給各個的數值，也就是說由根部開始，若向左邊為"0"，若向右邊為"1"，然後走到某一個葉之前所經過的路程的值作為資料的編碼，當然也可用向左為"1"向右為"0"。 2019/4/28

【作法】 1. 以所有的外部節點形成一個串列。 2. 挑出兩個最小加權的子樹 x, y，結合成一個新子樹 z，新子樹的 加權z=x+y，將新子樹放回串列。 3. 回到步驟2，直到串列中只剩一個元素。 【特性】擁有最小的加權外徑長度。 2019/4/28

【用途】 霍夫曼樹是二元樹的一種，而霍夫曼碼常常應用在資料壓縮領域中，它是以外部節點來代表訊息，而訊息的編碼則是採用二進位方式，並且以”0”或”1”來決定分支情況，如下將左分支當作”0”，而右分支當作”1”。 2019/4/28

【實例】假設有使用頻率為1, 3, 5, 7, 10, 14, 18的7個訊息需要傳送， 求得Huffman的解碼樹之過程。 2019/4/28

2019/4/28

2019/4/28

2019/4/28

8-8 2-3樹 【定義】一棵2-3樹可以為空，若不為空，則必須滿足下列定義： 1. 2-3 樹中每1個節點最多存放2個鍵值資料、3個指標。 8-8 2-3樹 【定義】一棵2-3樹可以為空，若不為空，則必須滿足下列定義： 1. 2-3 樹中每1個節點最多存放2個鍵值資料、3個指標。 2. 若節點存放1個鍵值資料Ldata，其必須要存在2個子節點，分別為 「左子節點」與「右子節點」： (1)左子節點的鍵值小於Ldata (2)右子節點的鍵值大於Ldata 2019/4/28

3. 若節點中存放2個鍵值資料Ldata與Rdata，其必須要存在3個子節點， 分別為「左子節點」、「中子節點」及「右子節點」，則： 4. 樹中所有樹葉節點必須為同一階度（Level） 2019/4/28

8-8.1 2-3 樹加入的方法 2-3 樹加入節點的規則如下： 1.欲加入的節點，如果該2-3 樹的節點只有1個鍵值資料，則直接加入。 8-8.1 2-3 樹加入的方法 2-3 樹加入節點的規則如下： 1.欲加入的節點，如果該2-3 樹的節點只有1個鍵值資料，則直接加入。 2.欲加入的節點，如果該2-3 樹的節點已經有2個鍵值資料，則在加入 之後(會產生溢位現象)，必須再進行分離動作。 3.進行調整 2019/4/28

2019/4/28

8-8.2 2-3 樹的刪除方法 2-3 樹的刪除分為兩個部份：一為樹葉節點 ( leaf node ) ，另一為非樹葉節點 ( non-leaf node　) 。 2-3 樹 刪除節點的規則如下： 1.欲刪除的節點，如果該2-3 樹的節點已經有2個鍵值資料，則直接刪除。 2.欲刪除的節點，如果該2-3 樹的節點只有一筆資料，則在刪除之後(會產 生underflow現象)，必須再進行Rotation(周轉)。 3.進行調整 2019/4/28

(１) 若刪除的節點是樹葉節點 2019/4/28

2019/4/28

(２) 若刪除的節點是非樹葉節點 假設欲刪除的鍵值 x 為非樹葉節點，此時須找一節點 s'，此 s' 必需是樹葉點，並且是鍵值x的左子樹中最大值或是右子樹中最小值，但是不能取得s'之後，產生溢位或underflow的現象。 2019/4/28

2019/4/28

8-9 2-3-4 樹 【定義】2-3-4 樹為 2-3 樹的觀念擴充，它可以為空，若不為空，則必須滿足下列定義： 8-9 2-3-4 樹 【定義】2-3-4 樹為 2-3 樹的觀念擴充，它可以為空，若不為空，則必須滿足下列定義： 1. 2-3-4 樹中的節點最多可以存放3個鍵值資料、4個指標 。 2. 若節點存放1個鍵值資料Ldata，其必須要存在2個子節點，分別為「左子節點」與「右子節點」： (1)左子節點的鍵值小於Ldata (2)右子節點的鍵值大於Ldata 2019/4/28

3. 若節點中存放2個鍵值資料Ldata與Rdata，其必須要存在3個子節 點，分別為「左子節點」、「中子節點」及「右子節點」，則： 2019/4/28

4. 若節點中存放3個鍵值資料 Ldata 、 Mdata 與 Rdata ，其必須要存在 4個子節點，分別為「左子節點」、「左中子節點」、「右中子節 點」與「右子節點」，則： (1) Ldata < Mdata < Rdata 。 (2)左子節點的鍵值小於Ldata (3)左中子節點的鍵值必須要大於Ldata並且小於 Mdata。 (4)右中子節點的鍵值必須要大於Mdata並且小於 Rdata。 (5) 右子節點的鍵值必須要大於Rdata。 5. 樹中所有樹葉節點必須為同一階度（Level） 2019/4/28

8-9.1 2-3-4 樹加入的方法 2-3-4 樹加入節點的規則與2-3 樹十分相似，只是2-3-4樹之節點內的鍵值最多可以3個，而2-3樹之節點內的鍵值最多只能2個，如下： 1.欲加入的節點，如果該2-3-4 樹的節點只有1或2個鍵值資料時，則 直接加入。 2.欲加入的節點，如果該2-3-4 樹的節點已經有3個鍵值資料時，則在 加入之後(會產生溢位現象)，必須再進行分離動作。 3.進行調整 2019/4/28

分離動作，如圖8-16所示： 2019/4/28

2019/4/28

8-9.2 2-3-4 樹的刪除方法 2-3-4 樹的刪除分為兩個部份：一為樹葉節點 ( leaf node ) ，另一為非樹葉節點 ( non-leaf node　) 。 2-3-4 樹 刪除節點的規則如下： 1.欲刪除的節點，如果該2-3-4 樹的節點已經有2或3個鍵值資料， 則直接刪除。 2.欲刪除的節點，如果該2-3-4 樹的節點只有1個鍵值資料，則在刪除 之後(會產生underflow現象)，必須再進行Rotation(周轉)。 3.進行調整 2019/4/28

Rotation(周轉)，如圖8-17所示： 2019/4/28

(１) 若刪除的節點是樹葉節點 2019/4/28

(２) 若刪除的節點是非樹葉節點 假設欲刪除的鍵值 x 為非樹葉節點，此時須找一節點 s'，此 s' 必需是樹葉點，並且是鍵值x的左子樹中最大值或是右子樹中最小值，但是不能取得s'之後，產生溢位或underflow的現象。 2019/4/28

2019/4/28

8-10 紅-黑樹 ( Red-Black tree ) 【定義】 (１) 紅-黑樹為一棵二元搜尋樹 ( binary search tree ) 。 (２) 由根節點到葉節點，不論路徑如何，其皆有相同數目的黑色節點。 (３) 由根節點到葉節點，其所經過的路徑不會連續出現兩條紅色的節點。 2019/4/28

【特性】 在紅-黑樹中有一個很重要的特性-子節點分為黑與紅兩種，黑色代表實際的鏈結，紅色代表原本不存在的鏈結。假設下圖為將2-3-4 樹轉換成紅-黑樹，其中粗線(紅色)代表原本不存在的鏈結。 2019/4/28