二叉搜索樹(Binary Search Tree).
AVL樹(艾薇兒樹).
之前我們了解的樹吧史，都是一個節(jié)點可有多個孩子鹅巍，但是它自身只能存儲一個元素剔交。二叉樹限制更多请敦，節(jié)點最多只能有兩個孩子镐躲。一個節(jié)點只能存儲一個元素储玫，在元素非常多的時候，就是的要么樹的深度非常大(樹的高度非常大)萤皂，這就使得內存存儲次數(shù)非常多撒穷。
試想一下，為了要在一個擁有幾十萬個文件的磁盤中查找一個文本文件裆熙，你設計的算法需要讀取磁盤上萬次端礼，還是讀取幾十次，這是有本質差異的入录。此時蛤奥，為了降低對外存儲設備的訪問次數(shù)，就需要更好的數(shù)據(jù)結構來處理這樣的問題僚稿。為此凡桥，引入了B樹(多路查找樹)的概念。
B樹是一種平衡的多路搜索樹蚀同，多用于文件系統(tǒng)唬血、數(shù)據(jù)庫的實現(xiàn)。
我們先來看幾個B樹的樣子唤崭，如下圖所示：
一、 ★★★【B樹】性質：
?假設一個節(jié)點存儲的元素個數(shù)為 x
?根節(jié)點:1 ≤ x ≤ m ? 1
?非根節(jié)點:┌ m/2 ┐ ? 1 ≤ x ≤ m ? 1
?如果有子節(jié)點脖律，子節(jié)點個數(shù) y = x + 1
?根節(jié)點:2 ≤ y ≤ m
?非根節(jié)點:┌ m/2 ┐ ≤ y ≤ m
☆★☆
假如3階B數(shù)：
根節(jié)點：1 ≤ x ≤2
非根節(jié)點：┌ 3/2 ┐ ? 1 ≤ x ≤ 3 ? 1 ---> 1 ≤ x ≤ 2
如果有子節(jié)點谢肾，子節(jié)點個數(shù) y = 3;
注意：①┌ ┐是向上取整，即代碼中的Ceil()函數(shù)
②└ ┘是向下取整小泉，即代碼中的 Floor()函數(shù)
?比如 m = 3芦疏，2 ≤ y ≤ 3，因此可以稱為(2, 3)樹微姊、2-3樹
?比如 m = 4酸茴，2 ≤ y ≤ 4，因此可以稱為(2, 4)樹兢交、2-3-4樹
?比如 m = 5薪捍，3 ≤ y ≤ 5，因此可以稱為(3, 5)樹
B樹 VS 二叉搜索樹
?B樹 和 二叉搜索樹配喳，在邏輯上是等價的
? 多代節(jié)點合并酪穿，可以獲得一個超級節(jié)點
2代合并的超級節(jié)點，最多擁有 4 個子節(jié)點(至少是 4階B樹)
3代合并的超級節(jié)點晴裹，最多擁有 8 個子節(jié)點(至少是 8階B樹)
n代合并的超級節(jié)點被济，最多擁有 2n個子節(jié)點( 至少是 2n階B樹)
?m階B樹，最多需要 log2m 代合并01.jpg
二涧团、【B樹】節(jié)點的增加和刪除
對于B樹來說只磷，與二叉搜索樹相同经磅，插入操作一定是發(fā)生在葉子節(jié)點上∨プ罚可與二叉搜索樹不同的是预厌，B樹插入一節(jié)點的過程可能會對該樹的其余結構產生連鎖反應。
1.節(jié)點添加步驟：
B樹節(jié)點添加可分為兩種情況
第一種情況：正常添加節(jié)點到對應的葉子節(jié)點上
02.jpg
添加節(jié)點動畫如下：01.gif
第二種情況：添加節(jié)點上溢
上溢節(jié)點的元素個數(shù)必然等于 m
?假設上溢節(jié)點最中間元素的位置為 k
? 將 k 位置的元素向上與父節(jié)點合并
? 將 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 個子節(jié)點上溢-分裂為兩個節(jié)點.jpg
如下圖所示畏陕，一個4階B樹配乓，添加一個節(jié)點110，產生了上溢惠毁。
產生上溢的原因分析：
4階B樹需要滿足以下條件：① 根節(jié)點：1 ≤ x ≤ 3(滿足) ; ② 非根節(jié)點：1 ≤ x ≤ 3 （添加節(jié)點110后不滿足犹芹，所以產生了上溢）
03.jpg
添加節(jié)點動畫如下：02.gif
2.節(jié)點刪除步驟：
B樹節(jié)點刪除也分為兩種情況
第一種情況：刪除葉子節(jié)點(4階B樹)
04.jpg刪除節(jié)點動畫如下：
03.gif
第二種情況：刪除非葉子節(jié)點(包含節(jié)點下溢的情況)
?1. 假如需要刪除的元素在非葉子節(jié)點中
①. 先找到前驅或后繼元素，覆蓋所需刪除元素的值
②. 再把前驅或后繼元素刪除
? 非葉子節(jié)點的前驅或后繼元素鞠绰，必定在葉子節(jié)點中
? 所以這里的刪除前驅或后繼元素 腰埂，就是最開始提到的情況:刪除的元素在葉子節(jié)點中
? 真正的刪除元素都是發(fā)生在葉子節(jié)點中如下圖所示，刪除節(jié)點60蜈膨，真正被刪除的是60的前驅節(jié)點55屿笼。
05.jpg刪除節(jié)點動畫如下：
04.gif
?2. 假如需要刪除的元素產生了下溢
下溢的解決分兩種情況：(1).兄弟充足，兄弟節(jié)點可借 (2).兄弟節(jié)點不可借翁巍，父節(jié)點下來合并驴一。
(1).兄弟充足，兄弟節(jié)點可借
下溢-借兄弟節(jié)點.jpg
注意：這里不可以直接借用灶壶，即：不可以直接將A放到綠色的框中肝断，因為B樹葉滿足二叉樹的性質，左邊小于右邊驰凛，如果直接放過來胸懈，破壞了二叉樹的性質。(2).兄弟節(jié)點不可借恰响，父節(jié)點下來合并趣钱。
下溢-父節(jié)點合并.JPG
這個操作可能會導致父節(jié)點下溢,下溢現(xiàn)象可能會一直往上傳播。
如下圖所示胚宦，刪除節(jié)點12首有，就產生了下溢。
產生下溢的原因分析：我們假定這是一棵5階B樹
5階B樹需要滿足以下條件：① 根節(jié)點：1 ≤ x ≤ 4(滿足) ; ② 非根節(jié)點：2 ≤ x ≤ 4 （刪除節(jié)點12后不滿足间唉，所以產生了下溢）
06.jpg
刪除節(jié)點-父節(jié)點下來合并動畫：
05.gif
好了绞灼，B樹學習告一段落，其實學習B樹呈野，最終是為了紅黑樹低矮。
最后，推薦一個神奇的網站Data Structure Visualizations被冒，可以幫助我們學習B樹军掂。
