目标在葉節點
這種情況共有
4
種，我們隻需要考慮，删除節點後目前節點需要滿足的。
b樹的删除操作，都以這張圖為例，這裡為2-3階b樹：
-
目标删除後，該節點的鍵數量≥規定度數/2
直接删除即可，注意，需要讓B樹鍵值數量做自減。
如圖：删除圖中的葉節點節點中的
3
.
-
目标删除後，該節點的鍵數量＜規定度數/2
如果是左，那麼就借他的最大鍵；
如果是右，那麼就借他的最小鍵；
得到之後，要記得對兄弟節點的鍵數量做自減
接着，再得到在父節點中，分離這兩個節點的鍵，然後把這個鍵值賦給目标鍵所在的節點，删除目标鍵。
如圖：本次删除的目标鍵為
2
》》向兄弟借鍵時，需要考慮：
- 目前目标節點在父節點的孩子數組中的位置是啥？上圖中
2
5,9
5
- 假設現在删除
10
10
5,9
10
9
向兄弟節點借鍵，還有一種比較複雜的問題。記住，我會在最後一種情況進行闡述的。
- 若上述條件都不成立，那屆時就處于一種很困的地步了。那就是合并了。
warnning:套路較多，請系好安全帶，以免暈車哦
為避免暈車，我在這裡先上一幅圖，提前警備一下前方的坎坷路程。
舉一個特别糟糕的例子，如圖：
删除 B樹删除之迷魂大法感謝您的仔細閱讀。 5
B樹删除之迷魂大法感謝您的仔細閱讀。 B樹删除之迷魂大法感謝您的仔細閱讀。 B樹删除之迷魂大法感謝您的仔細閱讀。 總結 B樹删除之迷魂大法感謝您的仔細閱讀。 - 合并操作在葉節點的時候，隻管合并，然後注意一下參與鍵值合并的節點的鍵值數量變化 ；
- 若在内部，重中之重的問題，就是還要合并兩個節點的孩子，這裡需要強調的是要嚴格遵循b樹的定義，且看清楚兄弟節點的位置，然後進行父子相關聯的操作
接下來就是有關于遇到父節點滿足條件時進行合并的相關操作，與前面雷同，當在内部要進行這些操作時，也要進行兩節點的孩子合并操作。但與借兄弟節點鍵不同，這個操作比借兄弟的要簡單一些。
我們來回想一下，當删除的目标鍵在葉節點時，需要參照以下遵循：
1.當夠就删；
2.當不夠，就回溯；
3.若有兄弟可借酒，兄弟位置要準瞅，接着退出；
4.若兄弟不可借酒，就向父借酒，然後與兄弟共享之，但牢記要喊上孩子們,然後退出；
5.若實在都不行，則繼續合并；
上述都是我個人自己編的，其實旨在于幫助了解。
目标不在葉節點
目标在内部節點，這個時候，就要找與它挨邊兒的來逐漸下沉，交替。我還是畫個圖來感官的了解一下。
參照上面的那幅圖 本次删除
20
接下來的删除操作，就參照目标在葉節點來進行。
代碼部分
具體代碼：（主要用于處理合并的操作）
my_B_tree* addr[SONNODECOUNT] = { nullptr };//存儲節點位址。
size_t keyArray[SONNODECOUNT] = { 0 };//存儲鍵值
my_B_tree* mergeNode = nullptr;
while (1)
{
if ((parentNode->degress <= (DEGRESS >> 1) ||
parentNode->degress > (DEGRESS >> 1)) &&
brother->degress <= (DEGRESS >> 1))//合并
{
//此邏輯隻能處理父節點是否滿足删除後的鍵值是否滿足1/2，并且兄弟節點不夠借的情況。
mergeNode = new my_B_tree;
/*620--639 處理merge節點*/
NodesToOne(mergeNode, brother, findNode);//将兄弟和父裡面的鍵值合并到merge
if (isRight == true) {
mergeNode->key[mergeNode->degress++] = parentNode->key[levelPos];
keyMobile(parentNode, levelPos);//重新将par節點的鍵對進行歸位
}
else {
mergeNode->key[mergeNode->degress++] = parentNode->key[levelPos - 1];
keyMobile(parentNode, levelPos - 1);
}
int index = _insert_shellMode_Sort(mergeNode, key);//排序mergeNode節點
if (false == isDelete) {//delKey是否删除
keyMobile(mergeNode, index);
mergeNode->degress--;
isDelete = true;
}
/*對父節點進行移動，關聯父與子節點的關系*/
if (isRight == true)
{
move_Bro_Par_addr(parentNode, levelPos);
parentNode->sonPt[levelPos] = mergeNode;//關聯merge與parent的關系，将合并節點放在父節點的左邊
}
else
{
move_Bro_Par_addr(parentNode, levelPos - 1);
parentNode->sonPt[levelPos - 1] = mergeNode;
}
parentNode->degress--;
//par指針回溯到原始B樹的根節點，此時，merge節點中的parent指向為空
if (parentNode == tempRootNode)
{
mergeNode->parent = nullptr;
mergeAddr(mergeNode, findNode, brother, isRight);//将find孩子、par孩子合并至merge
FREE_MEMORY(parentNode);
tempRootNode = mergeNode;
FREE_MEMORY(findNode);
FREE_MEMORY(brother);
break;
}
else {//parent沒有回到之前的臨時根（tempRootNode)
mergeNode->parent = parentNode;
}
mergeAddr(mergeNode, findNode, brother);//将 findNode, brother兩個孩子的節點合并到mergeNode
FREE_MEMORY(findNode);//釋放findNode, brother
FREE_MEMORY(brother);
findNode = brother = nullptr;
//if (flag)//parent節點删除後依然滿足1/2，退出
// break;
//find指針向上追溯
findNode = mergeNode->parent;
parentNode = parentNode->parent;
levelPos = searchAdd(findNode, parentNode);
if (levelPos == parentNode->degress) {
isRight = false;//brother為左兄弟 控制與那個兄弟節點進行交換
brother = parentNode->sonPt[levelPos - 1];
}
else
{
brother = parentNode->sonPt[levelPos + 1];
isRight = true;
}
}
else
{
//該邏輯隻能處理單獨向兄弟借的情況。
//擷取findNode,brother節點的孩子鍵值以及位址，存儲在容器中，并将鍵值進行排序
getSonNodeKey(findNode, brother, addr, keyArray, isRight);//error
size_t parKey, broKey;
modifyBroParent(parentNode, brother, &parKey, &broKey, levelPos, isRight);
//将parKey, broKey分别放入到par節點和bro節點
parentNode->key[parentNode->degress++] = broKey;
_insert_shellMode_Sort(parentNode, broKey);//父節點的鍵值進行排序
findNode->key[findNode->degress++] = parKey;
_insert_shellMode_Sort(findNode, parKey);
fdndResetConnect(findNode, addr);
break;
}
}
有關于沉底的操作，在這裡就不提供代碼了。