Embedded Files
13-1 2-3-Tree
2-3-Tree的定義如下。
(1) 樹中每一個內部節點的分支度為2或3，分支度為2的節點有1個鍵值，分支度為3的節點有2個鍵值。
(2) 分支度為2的節點有1個鍵值，假設其鍵值為x，則鍵值x的左子樹的每一個鍵值都小於x，鍵值x的右子樹的每一個鍵值都大於x，如下圖。
(3) 分支度為3的節點有2個鍵值，假設其鍵值分別為x與y，x小於y，則鍵值x的左子樹的每一個鍵值都小於x，鍵值x的右子樹(或鍵值y的左子樹)的每一個鍵值都大於x且小於y，鍵值y的右子樹的每一個鍵值都大於y。
(4) 所有葉節點都在同一階層。
13-1-1 2-3-Tree搜尋元素的概念說明
2-3-Tree內搜尋某個元素存不存在，原理同二元搜尋樹的搜尋，經由節點內的鍵值決定要搜尋的子樹，一層一層的往下縮小搜尋範圍，直到找到該元素，或找不到該元素，舉例如下。假設搜尋元素83是否存在，則從根節點36開始，發現83比36大，所以搜尋根節點的右子樹，發現83比79大，但比85小，所以搜尋節點「79,85」中間的子樹，往下找到節點「83」，回傳找到元素83。
13-1-2 2-3-Tree新增元素的概念說明
若插入到2個鍵值的節點，變成3個鍵值的節點，不符合2-3-Tree的定義，需要將中間值往上提插入上一層的節點，若上一層節點的鍵值也是2個鍵值，則中間值繼續往上提插入上一層的節點，不斷的往上提，直到符合2-3-Tree的定義為止，舉例如下。
假設插入數值95到2-3-Tree，如下圖。
因為節點「93,98」的鍵值個數為2，加入元素95，變成3個鍵值的節點，不符合2-3-Tree的定義，將節點「93,95,98」中間值95往上提到上一層節點「79,85」，節點「79,85」加入95後，也變成3個鍵值的節點，不符合2-3-Tree的定義，將節點「79,85,95」中間值85往上提到上一層節點，如下圖。由上往下找尋95要插入的節點，插入後造成由下往上的不斷往上提，這就是2-3-Tree的缺點，演算法效率較差，而2-3-4-tree(下一節介紹)會在由上往下的搜尋過程中事先分割，就可以避免由下往上的走訪，演算法效率較佳。
13-1-3 2-3-Tree刪除元素的概念說明
(一)旋轉(rotate)
2-3-Tree在刪除元素過程中，如果該節點只有一個元素時，刪除該元素會造成節點元素不足，如果相鄰的左右手足是兩個元素的節點，則可以向相鄰的左手足或右手足借用元素，稱作旋轉，再刪除該元素，如以下範例。
如果要刪除元素83，該節點只有一個元素，但右手足有兩個元素，所以跟右手足借元素93取代上一層的元素85，元素85移到元素83的右側，該節點就會有兩個元素，稱作旋轉。
元素83所屬節點有兩個元素，直接刪除元素83。
(二)合併(combine)
如果該節點只有一個元素時，刪除該元素會造成節點元素不足，此時相鄰的左右手足都是一個元素的節點，則合併左手足或右手足，稱作合併，再刪除該元素，如以下範例。
如果要刪除元素85，該節點只有一個元素，且相鄰的左右手足都只有一個元素，所以跟左手足或右手足合併，本範例選擇與右手足合併，如下圖。
再刪除元素85，就符合2-3 tree的定義。
13-2 2-3-4-Tree
2-3-4-tree的定義如下。
(1) 樹中每一個內部節點的分支度為2、3或4，分支度為2的節點有1個鍵值，分支度為3的節點有2個鍵值，分支度為4節點有3個鍵值。
(2)分支度為2的節點有1個鍵值，假設其鍵值為x，則鍵值x的左子樹的每一個鍵值都小於x，鍵值x的右子樹的每一個鍵值都大於x，如下圖。
(3)分支度為3的節點有2個鍵值，假設其鍵值分別為x與y，x小於y，則鍵值x的左子樹的每一個鍵值都小於x，鍵值x的右子樹(或鍵值y的左子樹)的每一個鍵值都大於x且小於y，鍵值y的右子樹的每一個鍵值都大於y。
(4)分支度為4的節點有3個鍵值，假設其鍵值分別為x、y與z，x小於y且y小於z，則鍵值x的左子樹的每一個鍵值都小於x，鍵值x的右子樹(或鍵值y的左子樹)的每一個鍵值都大於x且小於y，鍵值y的右子樹(或鍵值z的左子樹)的每一個鍵值都大於y且小於z，鍵值z的右子樹的每一個鍵值都大於z。
(5)所有葉節點都在同一階層。
13-2-1 2-3-4-Tree搜尋元素的概念說明
2-3-4-Tree內搜尋某個元素存不存在，原理同2-3-Tree與二元搜尋樹，經由節點內的鍵值決定要搜尋的子樹，一層一層的往下縮小搜尋範圍，直到找到該元素，或找不到該元素。
13-2-2 2-3-4-Tree新增元素的概念說明
新增元素到2-3-4-Tree時，如果超過節點元素的最大上限，則中間元素往上提，併入上一層節點，如果在根節點(root)發生超過最大上限的元素個數，則樹的高度增加1。非根節點的上層節點已達最大上限的元素個數，則繼續往上併入上一層節點，如此會產生由下往上的走訪，如果要避免這個問題，可以由上往下找尋插入節點的位置時，將搜尋過程中經過的所有節點，如果鍵值個數達到最大上限的節點，先進行分割往上提，讓上層都未達最大上限的鍵值個數，如此新增節點到2-3-4-Tree時，是由上往下找到插入的位置，避免接著由下往上的走訪。
以上為2-3-4-Tree，插入元素93時，會插入在節點83,85,98，造成85往上提到節點6,36,79，此時節點6,36,79也需要分割，增加一個階層，根節點改成節點36，造成由下往上的走訪，如下圖。
為了避免由下往上的走訪，如果在找尋元素93的插入節點時，從根節點開始找，發現根節點有3個元素，達到元素個數的最大上限，先進行分割，將元素36往上提。
結果如下，就可以防止插入新元素93時，造成元素85往上提，形成由下往上的走訪，因為上層節點79未達元素個數的最大上限。
當插入93時，會造成元素85往上提到上一層節點79，再插入93。
13-2-3 2-3-4-Tree刪除元素的概念說明
(一)旋轉(rotate)
如果相鄰節點的元素個數足夠，就可以使用旋轉借用相鄰節點內的元素。
以上為2-3-4 -Tree，刪除元素83時，會跟節點「93,98」，借用元素93，將元素93移動到上一層，將元素85移動到元素83所在節點，就可以刪除元素83，稱作旋轉(rotate)，如下圖。
(二) 合併(combine)
如果相鄰節點的元素個數都只有最低元素個數，則可以與其中一個相鄰節點合併。
以上為2-3-4 -Tree，刪除元素57時，會與79與83合併成一個節點，稱作合併，如下圖。
讓節點數足夠，再將元素57刪除。
(三)刪除非葉節點內的元素
若刪除元素為葉節點，就可以直接刪除元素；若刪除元素不是葉節點，則可以找尋刪除元素的左子樹最大值，或右子樹最小值的元素為替代元素，此替代元素一定在葉節點上，將此替代元素從2-3-4-Tree刪除，2-3-4-Tree內找到原來要刪除元素，將刪除元素改回替代元素。
以上為2-3-4-Tree，刪除元素85時，不是葉節點，假設找尋右子樹最小值為替代元素，就會選用右子樹最小元素93為替代元素，元素93所在節點個數如果足夠就直接刪除，否則進行旋轉或合併，增加節點內元素個數，再刪除元素93，該節點元素個數足夠所以直接刪除，如下圖。
但因為要刪除的元素是85而不是93，接著找尋元素85，將其值改成93，到此完成刪除非葉節點的元素85。
2-3-4-Tree的程式實作，請參考下一節B-tree的程式實作，因為2-3-4-Tree為B-Tree的特例。
13-3 B-Tree
2-3-Tree與2-3-4-Tree都是B-Tree的特例，B-Tree可以在很短時間內找尋資料是否存在，與儲存資料到B-Tree，例如：B-Tree廣泛應用於資料庫系統，讓資料庫能有效率的搜尋與儲存資料。
分支度為m的B-tree須滿足以下屬性：
(1)每一個節點至多有m個小孩
(2)除了根節點以外的非葉節點，至少要有⌈m/2⌉個小孩。
(3)根節點至少有兩個小孩。
(4)有n個小孩的非葉節點，包含n-1個鍵值。
(5)所有葉節點都在同一階層。
(6)鍵值k的左子樹的每一個元素一定小於鍵值k，鍵值k的右子樹的每一個元素一定大於鍵值k。
下圖為最大分支度為4(m=4)，分支度最小為2的B-Tree，也是2-3-4-Tree，2-3-4-Tree是B-Tree的特例。鍵值6的左子樹的每一個元素小於6，鍵值6的右子樹的每一個元素大於6；鍵值36的左子樹的每一個元素小於36，鍵值36的右子樹的每一個元素大於36；鍵值79的左子樹的每一個元素小於79，鍵值79的右子樹的每一個元素大於79。
13-3-1 B-Tree新增元素的概念說明
新增元素到B-Tree時，如果超過節點元素的最大上限，則中間元素往上提，併入上一層節點，如果在根節點(root)發生超過最大上限的元素個數，則樹的高度增加1。
以下是分支度最大為6，分支度最小為3的B-Tree為了避免由下往上的走訪，如果在找尋元素93的插入節點時，從根節點開始找，發現根節點有5個元素，達到元素個數的最大上限，先進行分割，將元素79往上提。
結果如下，就可以防止插入新元素93時，造成元素98往上提，形成由下往上的走訪，因為上層節點「130,196」未達元素個數的最大上限。
當插入93時，會造成元素98往上提到上層節點「130,196」，再插入93。
以下示範將10個數值新增到B-Tree
假設將以下元素「36, 2, 6, 57, 12, 98, 79, 83, 85, 93」依序插入分支度最大為6，分支度最小為3的B-Tree，也就是節點的最多元素個數為5，最少元素個數為2，B-Tree插入的步驟如下。
13-3-2 B-Tree新增元素的程式實作
(a)想法
新增類別Node，該類別需要串列childs儲存節點的小孩，串列keys儲存節點的鍵值。為了計算⌈m/2⌉而產生過多的除法與無條件進位運算，本範例程式轉換成B-Tree節點鍵值個數最多為2*order-1個，最少為order-1個，相當於節點的分支度最多為2*order個，最少為order個，也符合B-Tree的定義。建立類別BTree，內建變數order為限制B-Tree的元素個數最多為2*order-1個，最少為order-1個。內建變數root用於指向根節點，方法getChild，找出變數x在node的第幾個小孩下，方法insert與insert2，將變數x插入到node下。方法split將元素一分為二，中間的鍵值移動到上一層。方法print_btree印出目前B-Tree的節點狀態。
(b)程式碼與解說
(ch14\BTree-insert.py)
第1到4行：定義類別Node，方法__init__內定義串列childs用於儲存節點的子樹，串列keys用於儲存節點的鍵值。
第5到66行：定義類別BTree，方法__init__內定義變數order為限制B-Tree的元素個數最多為2*order-1個，最少為order-1個(第7行)，變數root為Node物件。
第9到15行：定義方法getChild，找出x在node的第幾個小孩下，使用迴圈變數i由0變化到node鍵值的長度-1，使用node.keys[i]依序存取node內的每一個鍵值，若node.keys[i]小於x，變數i遞增1，否則回傳變數i。若都沒執行第14行，則最後回傳node鍵值的長度。
第16到27行：定義方法insert，若根節點root的鍵值個數等於2*order-1個，表示根節點滿了，將根節點一分為二，且增加一層，變數tmp指向根節點root(第18行)，根節點指向新的物件Node(第19行)，將變數tmp加入根節點root的串列childs(第20行)，呼叫函式split將根節點的childs[0]的中間元素往上提到根節點，其餘分成兩個子樹(第21行)。若根節點的第1個鍵值小於x，使用方法insert2將x插入到根節點的第2個小孩下，否則使用方法insert2將x插入到根節點的第1個小孩下(第22到25行)。否則，根節點還未滿，則使用方法insert2將x插入到根節點(第27行)。
第28到40行：定義方法insert2，若node內的串列childs長度等於0(第29行)，表示在B-Tree的最下層，使用方法getChild找出x要插入在node的哪一個子樹下儲存到變數i(第30行)，將x插入在node的鍵值串列keys的第i個位置(第31行)，否則不在B-Tree最下層，使用方法getChild找出x要插入在node的哪一個子樹下儲存到變數i(第33行)，若節點node第i個小孩的鍵值個數等於2*order-1個(第34行)，表示節點滿了，使用方法split將節點node第i個小孩一分為二(第35行)，若節點node的第i個鍵值小於x(第36行)，變數i遞增1(第37行)，使用方法inserts將變數x插入在節點node的第i個小孩(第38行)。否則(節點node第i個小孩的鍵值個數未達最大上限) ，使用方法inserts將變數x插入在節點node的第i個小孩(第40行)。
第41到53行：定義方法split，將node的第i個小孩一分為二，設定變數tmp為node.child[i] (第43行)，將tmp.keys[self.order – 1]插入在串列node.keys的第i個元素，也就是將節點node第i個小孩中間的鍵值提到節點node(第44行)，設定right為物件Node，設定left為物件Node(第45到46行)，設定right的鍵值為變數tmp內鍵值第order到2*order-2個元素(第47行)，設定left的鍵值為變數tmp內鍵值第0到order-2個元素(第48行)。若tmp的小孩大於0個，設定right的小孩為變數tmp內小孩第order到2*order-1個元素(第50行)，設定left的小孩為變數tmp內小孩第0到order-1個元素(第51行)，設定node第i個小孩為left(第52行)，將right插入在node第i+1個小孩的位置(第53行)。
第54到66行：定義方法print_btree列印B-Tree，設定串列node初始化為串列每一個元素都是tuple，第一個元素為根節點與1所組成(第55行)，當串列node還有元素(第56行)，取出node第一個元素到n與i(第57行)，若node的長度大於0，且變數i等於串列node第1個元素的第2個元素，表示屬於同一階層，印出n的所有鍵值且不換行，否則印出n的所有鍵值且換行(第58到61行)。若n的小孩不是空串列(第62行)，變數i遞增1(第63行)，取出n的所有小孩到變數c，節點node新增變數c與i的tuple(第64到65行)，最後換行(第66行)。
第67行：變數btree指向最大分支度為6的B-Tree。
第68行：設定串列data為36、2、6、57、12、98、79、83、85與93。
第69到71行：使用迴圈依序取出串列data的每一個數值到變數item，使用btree的方法insert插入變數item的數值到btree(第70行)，呼叫btree的方法print_btree印出B-Tree目前狀態(第71行)。
(c)程式結果預覽
執行結果顯示在螢幕如下。
[36]
[2, 36]
[2, 6, 36]
[2, 6, 36, 57]
[2, 6, 12, 36, 57]
[12]
[2, 6][36, 57, 98]
[12]
[2, 6][36, 57, 79, 98]
[12]
[2, 6][36, 57, 79, 83, 98]
[12, 79]
[2, 6][36, 57][83, 85, 98]
[12, 79]
[2, 6][36, 57][83, 85, 93, 98]
(d)程式效率分析
B-Tree是高度平衡的樹，會維持節點的鍵值至少為⌈m/2⌉-1個，假設k等於⌈m/2⌉-1，整個B-Tree的鍵值總個數為N，所以B-Tree樹的高度約為〖log〗_k N，所以B-Tree的插入演算法最多比較O(logN)次就可以找到插入的節點，演算法效率為O(logN)。
13-3-3 B-Tree刪除元素的概念說明
刪除元素所在節點內的元素如果足夠，就直接刪除該元素，否則若造成節點元素個數低於B-Tree的最低元素個數，就需要旋轉(rotate)或合併(combine)讓節點內元素個數增加。如果相鄰節點的元素個數足夠，就可以使用旋轉借用相鄰節點內的元素；如果相鄰節點的元素個數都只有最低元素個數，則可以與其中一個相鄰節點合併。如果合併根節點的兩個子樹，則樹的高度會減少1階層。合併會造成上層節點的元素個數少1個，有可能會讓上層節點低於最少元素個數，上層節點也需要進行旋轉或合併，為了避免由下往上的走訪，可以由上往下找尋刪除的元素時，先進行旋轉或合併，讓走訪過程中所有節點的元素個數足夠，不會刪除一個元素就低於B-Tree的最低元素個數。2-3-4-Tree為B-Tree的一個特例，B-Tree的刪除鍵值原理與2-3-4-Tree的刪除鍵值原理相同，本節仍然使用2-3-4-Tree進行說明，鍵值少較容易聚焦在操作細節的說明，如果在2-3-4-Tree已經瞭解刪除鍵值原理，可以忽略此部分。
(一)旋轉(rotate)
如果相鄰節點的元素個數足夠，就可以使用旋轉借用相鄰節點內的元素。
以上為最大節點數3(最大分支度為4，分支度最小為2的B-Tree，也是2-3-4樹)的B-Tree，刪除元素83時，會跟節點93,98，借用元素93，將元素93移動到上一層，將元素85移動到元素83所在節點，就可以刪除元素83，稱作旋轉(rotate)，如下圖。
(二) 合併(combine)
如果相鄰節點的元素個數都只有最低元素個數，則可以與其中一個相鄰節點合併。
以上為最大節點數3(最大分支度為4，分支度最小為2的B-Tree，也是2-3-4樹)的B-Tree，刪除元素57時，會與節點79與83合併，稱作合併(combine)，如下圖。
讓節點數足夠，再將元素57刪除。
(三)刪除非葉節點內的元素
若刪除元素為葉節點，就可以直接刪除元素；若刪除元素不是葉節點，則可以找尋刪除元素的左子樹最大值，或右子樹最小值的元素為替代元素，此替代元素一定在葉節點上，將此替代元素從B-Tree刪除，B-Tree內找到原來要刪除元素，將刪除元素改回替代元素。
以上為最大節點數3(最大分支度為4，分支度最小為2的B-Tree，也是2-3-4樹)的B-Tree，刪除元素85時，不是葉節點，假設找尋右子樹最小值為替代元素，就會選用右子樹最小元素93為替代元素，元素93所在節點個數如果足夠就直接刪除，否則進行旋轉或合併，增加節點內元素個數，再刪除元素93，該節點元素個數足夠所以直接刪除，如下圖。
但因為要刪除的元素是85而不是93，接著找尋元素85，將其值改成93，到此完成刪除非葉節點的元素85。
(四)事先進行旋轉或合併
為了避免由下往上的走訪，可以由上往下找尋刪除的元素時，先進行旋轉或合併，讓走訪過程中所有節點的元素個數足夠，不會刪除一個元素就低於B-Tree的最低元素個數。
以上為最大節點數3(最大分支度為4，分支度最小為2的B-Tree，也是2-3-4樹)的B-Tree，刪除元素2時，由根節點走訪到節點6時，因為右邊相鄰節點「79,93」的元素個數足夠，事先使用旋轉增加節點6的元素個數，將元素79移動到根節點，元素36移動到節點6，如下圖。
因為節點2的元素個數不足，且相鄰節點元素個數也不足，所以使用合併增加節點2的元素個數，將元素2、6與12合併成一個節點。
將元素2、6與12合併成一個節點後，就可以直接刪除元素2。
到此刪除了元素2。
以下示範從B-Tree刪除元素的過程
假設將以下元素「36, 2, 6, 57, 12, 98, 79, 83, 85, 93」依序插入分支度最大為6，分支度最小為3的B-Tree，也就是節點的最多元素個數為5，最少元素個數為2，新增到B-Tree後，結果如下圖。
假設元素刪除順序為「12, 83, 36, 85, 2, 93, 6, 79, 57, 98」。
13-3-4 B-Tree刪除元素的程式實作
(一)旋轉(rotate)
(a)想法
上一層的鍵值儲存到串列keys內，keys[i]的左邊是childs[i]，而右邊是childs[i+1]。
當左邊可以借用時，旋轉的程式碼如下。
node.childs[i+1].keys.insert(0, node.keys[i])
if len(node.childs[i].childs) > 0:
node.childs[i+1].childs.insert(0, node.childs[i].childs[-1])
node.childs[i].childs.pop(-1)
node.keys[i] = node.childs[i].keys[-1]
node.childs[i].keys.pop(-1)
右邊可以借用的程式碼如下，與左邊可以借用的程式碼類似，就不重複說明。
node.childs[i].keys.append(node.keys[i])
if len(node.childs[i + 1].childs) > 0:
node.childs[i].childs.append(node.childs[i + 1].childs[0])
node.childs[i + 1].childs.pop(0)
node.keys[i] = node.childs[i + 1].keys[0]
node.childs[i + 1].keys.pop(0)
(b)程式碼與解說
(BTree.py)
第1行對應第54行，第15行對應第68行。
第54到68行：定義方法rotate，如果node的第i個小孩鍵值的個數大於order-1，表示可以跟左邊借(第55行)，將上一層的node的第i個鍵值，插入到node的第i+1個小孩的鍵值第一個位置，也就是將上層節點的鍵值移到下層節點(第56行)，當node的第i個小孩的小孩個數大於0時，表示node的第i個小孩有小孩，node的第i個小孩的最後一個小孩插入到node的第i+1個小孩的第一個小孩(第58行)，刪除node的第i個小孩的最後一個小孩(第59行)。將node的第i個小孩的最後一個鍵值，設定給node的第i個鍵值，也就是下一層的鍵值移動到上一層(第60行)，刪除node的第i個小孩的最後一個鍵值(第61行)；否則node的第i+1個小孩鍵值的個數大於order-1，表示可以跟右邊借(第62行)，將上一層的node的第i個鍵值，加入到node的第i個小孩的鍵值最後一個位置，也就是將上層節點的鍵值移到下層節點(第63行)，當node的第i+1個小孩的小孩個數大於0時，表示node的第i+1個小孩有小孩，node的第i+1個小孩的第一個小孩加入到node的第i個小孩的最後一個小孩(第65行)，刪除node的第i+1個小孩的第一個小孩(第66行)。將node的第i+1個小孩的第一個鍵值，設定給node的第i個鍵值，也就是下一層的鍵值移動到上一層(第67行)，刪除node的第i+1個小孩的第一個鍵值(第68行)。
(二)合併
(a)想法
以根節點root的合併為例，合併後高度減一，如下圖。
Step1)首先加入左子樹所有鍵值、自己與右子樹所有鍵值，如下方程式碼。
tmp = self.root
self.root = Node()
for k in tmp.childs[0].keys:
self.root.keys.append(k)
self.root.keys.append(tmp.keys[0])
for k in tmp.childs[1].keys:
self.root.keys.append(k)
Step2)加入左子樹與右子樹的所有小孩，如下方程式碼。
if tmp.childs[0].childs:
for c in tmp.childs[0].childs:
self.root.childs.append(c)
if tmp.childs[1].childs:
for c in tmp.childs[1].childs:
self.root.childs.append(c)
到此完成根節點root的合併，非根節點合併與此類似，就不再重複說明。
(b)程式碼與解說
(BTree.py)
第1行對應第69行，第34行對應第102行。
第69到102行：定義函式combine，如果node等於根節點root，且根節點root只有一個鍵值，表示合併後要少一階層，設定變數tmp為根節點root(第71行)，根節點root指向新的物件Node(第72行)。
第73到77行：將所有左子樹childs[0]的所有鍵值加入到根節點root(第73到74行)，將節點tmp(原本根節點)的鍵值加入到根節點root(第75行)，將所有右子樹childs[1]的所有鍵值加入到根節點root(第76到77行)。
第78到83行：如果左子樹childs[0]有小孩，則將所有左子樹childs[0]的所有小孩加入到根節點root的小孩(第78到80行)，如果右子樹childs[1]有小孩，則將所有右子樹childs[1]的所有小孩加入到根節點root的小孩(第81到83行)。
第84行：回傳此根節點root。
第85到102行：如果不是根節點或超過兩個小孩，永遠讓child[i]與child[i+1]合併，變數newNode指向新的物件Node(第86行)。
第87到91行：將所有左子樹childs[i]的所有鍵值加入到節點newNode(第87到88行)，將節點node的鍵值keys[i]加入到節點newNode(第89行)，將所有右子樹childs[i+1]的所有鍵值加入到節點newNode(第90到91行)。
第92到97行：如果左子樹childs[i]有小孩，則將所有左子樹childs[i]的所有小孩加入到節點newNode的小孩(第92到94行)，如果右子樹childs[i+1]有小孩，則將所有右子樹childs[i]的所有小孩加入到節點newNode的小孩(第95到97行)。
第98到101行：刪除節點node索引值為i的鍵值(第98行)，刪除節點node索引值為i與i+1的小孩(第99與100行)，將newNode插入到node的第i個小孩(第101行)。
第102行：回傳此節點node。
(三)刪除節點
(a)想法
定義函式search找尋變數x在B-Tree的所在位置，才能夠進行刪除，回傳變數x所在節點node與鍵值索引值i，也就是變數x出現在node.keys[i]。
定義函式find_right_child_min，找尋某個節點的右子樹的最小鍵值，當刪除的節點不在葉節點上，需轉換到右子樹的最小值節點或左子樹的最大值節點，這些節點一定在葉節點上，本程式使用右子樹的最小鍵值進行取代。
定義函式delete，從節點node往下找尋鍵值x並刪除鍵值x。若鍵值x在B-Tree的最後一層，呼叫函式delete_last_level進行刪除，否則(不在B-Tree的最後一層)呼叫函式find_right_child_min，找出鍵值x的右子樹最小鍵值設定給y，呼叫函式delete_last_level刪除B-Tree內的鍵值y。修正原本應該要刪除鍵值x但卻刪除鍵值y，呼叫函式search找出鍵值x所在節點與節點索引值，使用節點與節點索引值將B-Tree內的鍵值x改成y。
定義函式delete_last_level，如果節點內找到鍵值x則直接刪除，否則找出鍵值x所在小孩，若該小孩的鍵值個數只符合B-Tree的最少個數，且該小孩是最左邊的小孩，如果右邊的小孩有足夠的鍵值，則使用旋轉借用一個鍵值，否則使用合併，舉例如下圖，以下為分支度最大為6，分支度最小為3的B-Tree，也就是節點的最多元素個數為5，最少元素個數為2。
同理，若該小孩的鍵值個數只符合B-Tree的最少個數，且該小孩是最右邊的小孩，如果左邊的小孩有足夠的鍵值，則使用旋轉借用一個鍵值，否則使用合併。若該小孩的鍵值個數只符合B-Tree的最少個數，且該小孩是中間的小孩，如果左邊的小孩有足夠的鍵值，則使用旋轉借用一個鍵值，否則如果右邊的小孩有足夠的鍵值，則使用旋轉借用一個鍵值，否則選擇右邊小孩(也可以選擇左邊小孩)進行合併。
(b)程式碼與解說
(BTree.py)
第1行對應第103行，第56行對應第158行。
第103到111行：定義函式search，測試node的所有鍵值，若鍵值node.keys[i]小於x，則變數i遞增1(第105到106行)，否則若鍵值node.keys[i]等於x，則回傳node與i (第107到108行)，否則使用break中斷迴圈(第109到110行)。遞迴呼叫函式search，回傳node.childs[i]下的x所在位置(第111行)。
第112到115行：函式find_right_child_min找出右子樹的最小鍵值，當node的小孩個數大於0時，node更新為第一個小孩(第113到114行)，回傳節點node的第一個鍵值(第115行)。
第116到124行：定義函式delete，從節點node往下找尋鍵值x，回傳鍵值x所在節點與鍵值索引值到node與i(第117行)。若節點node沒有小孩，則鍵值x在B-Tree的最後一層，呼叫函式delete_last_level進行刪除(第118到119行)，否則(不在B-Tree的最後一層)呼叫函式find_right_child_min，找出鍵值x的右子樹(node.childs[i+1])最小鍵值設定給y(第120到121行)，呼叫函式delete_last_level刪除B-Tree內的鍵值y(第122行)。修正原本應該要刪除鍵值x但卻刪除鍵值y，呼叫函式search找出鍵值x所在節點與鍵值索引值到node與i(第123行)，鍵值x 在node.keys[i]，將node.keys[i]改成y(第124行)。
第125到158行：設定變數finish為False(第126行)，使用迴圈找尋節點node內的所有鍵值(第127行)，如果鍵值小於x則變數i遞增1 (第128到129行)，否則如果節點node有鍵值x則直接刪除，設定變數finish為True，回傳變數finish (第130到133行)，否則使用break中斷迴圈(第134到135行)。
第136到156行：若變數finish等於False且走訪過程的節點鍵值個數只符合B-Tree的最少個數(第136行)，如果該節點是最左邊的小孩(第137行)，如果右邊的小孩有足夠的鍵值，則呼叫函式rotate進行旋轉向右邊的小孩借用一個鍵值(第138到139行)，否則呼叫函式combine進行合併(第140到141行)，遞迴呼叫函式delete_last_level(第142行)。
第143到148行：否則若該節點是最右邊的小孩(第143行) ，如果左邊的小孩有足夠的鍵值，則呼叫函式rotate進行旋轉向左邊的小孩借用一個鍵值(第144到145行)，否則呼叫函式combine進行合併(第146到147行)，遞迴呼叫函式delete_last_level(第148行)。
第149到156行：否則節點屬於中間的子樹，如果右邊的小孩有足夠的鍵值，則呼叫函式rotate進行旋轉向右邊的小孩借用一個鍵值(第150到151行)，如果左邊的小孩有足夠的鍵值，則呼叫函式rotate進行旋轉向左邊的小孩借用一個鍵值(第152到153行)，否則(左右兩邊子樹的節點數皆不夠)使用函式combine與右子樹合併第154到155行)，遞迴呼叫函式delete_last_level(第156行)。
第157行：找出x在節點node所在的小孩索引值到變數i。
第158行：遞迴呼叫函式delete_last_level。
(c)程式效率分析
B-Tree是高度平衡的樹，會維持節點的鍵值至少為⌈m/2⌉-1個，假設k等於⌈m/2⌉-1，整個B-Tree的鍵值總個數為N，所以B-Tree樹的高度約為〖log〗_k N，所以B-Tree的刪除演算法最多比較O(logN)次就可以找到刪除的鍵值，演算法效率為O(logN)
(四)分層印出節點的所有鍵值
(a)想法
依序將節點加入串列node內，加入節點與所屬階層值，根節點所在階層值為1，從串列node取出一個節點後，就印出該節點的所有鍵值，加入該節點的所有小孩與遞增1後的階乘值到串列node，若階層值與前一個節點的階乘值相同，則不印出換行，否則印出換行。當串列node為空時，B-Tree就已經輸出完畢。
(b)程式碼與解說
(BTree.py)
第1行對應第159行，第22行對應第180行。
第159到171行：定義函式print_btree，串列node初始化為(self.root, 1)，表示根節點self.root，與階層值1所組成的tuple到串列node(第160 行)，當串列node長度大於0(第161 行)，則使用方法pop取出串列的第一個元素，節點到變數n，索引值到變數i(第162 行)。若串列node長度大於0，變數i等於串列node第1個元素的第2個數值，就是串列node第1個元素的階層值，表示在同一層，印出節點n的所有鍵值，且不印出換行(第163到164行)，否則印出節點n的所有鍵值，且印出換行(第165到166行)。
第167到170行：如果節點n的小孩不是空的，變數i遞增1(第168行)，將節點n的所有小孩與階層值i組成tuple，加入到串列node(第169到170行)。
第171行：輸出換行。
第172行：建立分支度最大為6，分支度最小為3的Btree，指定給btree。
第173行：串列data初始化為「36, 83, 85, 93, 12, 98, 2, 6, 57, 79」。
第174到176行：使用迴圈依序將串列data的每一個元素插入到btree(第175行)，並顯示btree狀態到螢幕上(第176行)。
第177行：串列data初始化為「2, 93, 6, 12, 83, 36, 85, 79, 57, 98」。
第178到180行：使用迴圈依序將串列data的每一個元素從btree刪除(第179行)，並顯示btree狀態到螢幕上(第180行)。
(c)程式結果預覽
執行結果顯示在螢幕如下。
[36]
[36, 83]
[36, 83, 85]
[36, 83, 85, 93]
[12, 36, 83, 85, 93]
[83]
[12, 36][85, 93, 98]
[83]
[2, 12, 36][85, 93, 98]
[83]
[2, 6, 12, 36][85, 93, 98]
[83]
[2, 6, 12, 36, 57][85, 93, 98]
[12, 83]
[2, 6][36, 57, 79][85, 93, 98]
[36, 83]
[6, 12][57, 79][85, 93, 98]
[36, 83]
[6, 12][57, 79][85, 98]
[83]
[12, 36, 57, 79][85, 98]
[83]
[36, 57, 79][85, 98]
[79]
[36, 57][85, 98]
[57, 79, 85, 98]
[57, 79, 98]
[57, 98]
[98]
[]
Page updated
Google Sites
Report abuse