前言
B樹的基本原理是為了服務紅黑叔準備的，了解B樹可以幫助我們更好理解紅黑樹，
文章目錄
- 前言
- B樹的概念特點性質
- B樹和二叉搜索樹的比較
- 查找B樹元素
- 插入結點
- 上溢現象及其解決方案
- 洗掉B樹元素
- 下溢現象及其解決方案
B樹的概念特點性質
B樹又叫平衡的多路搜索樹；
解釋：
平衡的意思是又滿足平衡二叉樹的一些性質，左樹大于右樹；
多路意思是，可以多個結點，不再是像二叉樹只有兩個結點；
如12結點小于父節點18，在左子樹，23 30 介于 父節點 18 33 之間，48 大于 18 33 在右子樹；
B樹的一些特點：
一個結點有多個值；
父節點有多個子節點；
高度一致，每個結點的子節點高度一致，平衡；
B樹的一些性質：
-
m階B樹：一個結點，最多擁有m個子節點，就叫m階B樹；
如：
設B樹的一個結點的個數為 x 個，則有性質 -
根節點： 1<= x <= m-1;
比如：三階B樹，根節點最少有1個值，最多2個值； -
非根結點：m / 2 向上取整 - 1 <= x <= m-1;
比如：三階B樹，一個結點的值最少為 1個，最多為 2個； -
如果有某個結點有子結點個數，則子結點個數 y = x +1;這是結點元素和結點子節點的數量關系
根結點： 2 <= y <= m;
非根結點： m/2 向上取整<= y <= m;
B樹和二叉搜索樹的比較
解釋：
多代結點合并，是二叉搜索樹父結點和子節點；
組合成超級結點，超級結點就是，B樹中，每一個結點可以有多個值；
2代合并：
如下圖二叉搜索樹合并為B樹，父結點和子節點合并；
查找B樹元素
查找步驟：
先從結點內部從左往右找，找到就結束；
找不到，就往它的左子樹或者右子樹找；
如下圖b樹，假如查找 72；
查找程序：
72比 40 大，往右子樹找；
在結點內依次比較：72大于60；繼續節點內找，70小于80，說明72不在該結點內； 繼續向下找，介于6080 之間，72大于70，并且 70內部沒有其他值，只能找 70右子樹；
70右子樹為空；所以說明72不在；
插入結點
對于B樹來說，首先：新添加的結點一定是插入到葉子節點，這是比較重要的認知；
上溢現象及其解決方案
假如我要插入98，前提是在4階B樹插入：在下面這種情況：就是結點內部元素個數最多3個時候，你再插入，該節點就變成4個元素，結點元素個數不符合性質 ：x<=m-1;這就是上溢的現象
解決上溢現象：
上溢現象的結點必定為 m 個元素，
在發生上溢的結點去找中間的值，以中間值為分界點，把發生上溢的結點分為左右子樹，插入父節點中，并且中間值插入到父節點中，
比如，上圖的：發生上溢結點如下圖
中間元素為 95 ，分左子樹為 90 ，右子樹為 98 100；把 95 插入父節點
假如插入父節點后，又發生生上溢，則繼續重復上面的步驟，直到插入到根結點；（有遞回的思想）
洗掉B樹元素
葉子節點洗掉：洗掉的結點如果是葉子結點：直接找到洗掉即可，
非葉子結點洗掉：找到要洗掉元素的前驅后繼覆寫該洗掉的結點即可，然后刪掉前驅或者后繼；
前驅或者后繼結點一定在葉子結點哦，
結點的前驅：在該結點的左子樹的最右的那個節點；
結點后繼：在該節點的右子樹的最左的那個結點上；
想明白前驅后繼就是比結點小的值和大的值就可，
比如洗掉60
找前驅后繼：
覆寫后：
總結：真正被洗掉的元素還是在葉子結點發生
下溢現象及其解決方案
下溢的現象是在洗掉元素的時候，導致這個結點的元素個數不滿足 m/2向上取整 -1 <= x;
比如：下圖五階B樹，結點元素個數范圍是【2，4】；洗掉22后，該結點的元素個數為 1個，不滿足5階B樹的結點元素個數要求咯，這就是下溢現象，
下溢現象的解決辦法
首先有個認知，發生下溢的結點元素個數必定為 ：m/2向上取整 -2；
解決方案：
在發生下溢結點的兄弟結點（前提兄弟結點元素個數至少為：m/2向上取整個），取出最右邊的元素（也就是最大那個），插入到發生下溢結點的父節點上，把父節點的值插入到發生下溢的結點：
還有一種情況是，發生下溢的兄弟結點的元素，最少為 m/2向上取整-1；
即，不可以在兄弟節點借元素插入到發生下溢結點的兄弟結點了，此時，就用合并的方案，將，發生下溢的結點的父節點向下和左右子樹合并；
如下圖：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290873.html
標籤：其他