c++实现B树(下)

 书接上回小吉讲的是B树的搭建和新增方法的实现（blog传送门🚪：B树实现上）（如果有小可爱对B树还不是很了解的话，可以先看完上一篇blog，再来看小吉的这篇blog）。那这一篇主要讲的是B树中删除操作的实现。
 在看小吉的数据结构与算法（c++实现）系列博客中，各位小可爱们应该能发现，其实在实现一个数据结构时，删除操作普遍比新增操作要难。小吉浅浅预告一下B树的删除操作可以说是天花板级别的难。但是各位小可爱们不要怕，跟着小吉的博客看下去B树删除易如反掌（哈哈，夸张了🤣）

在实现B树删除操作之前，小吉先在这声明一下：B树的删除是删除某个节点的key并不是将节点删除（无需使用delete）

九个成员方法

 在正式分析B树删除之前，先要实现9个方法（不要害怕，这九个方法都非常简单），这九个方法在后期实现删除操作代码时大有用处（可以小小期待一下）

int removeKey(int index);//移除指定index处的key
int removeRightmostKey();//移除最右边的key
Node* removeChild(int index);//移除指定index处的child
Node* removeLeftmostChild();//移除最左边的child
Node* removeRightmostChild();//移除最右边的child
Node* childLeftSibling(int index);//index孩子处左边的兄弟
Node* childRightSibling(int index);//index孩子处右边的兄弟
void moveToTarget(Node* target);//复制当前节点的所有key和child到target

这些方法都定义在Node节点类中，这些方法都比较简单，小吉在这就不详细讲解了，直接上代码。

int Node::removeKey(int index)
{int t = _keys[index];_keys.erase(_keys.begin() + index);KeyNumber--;return t;
}int Node::removeLeftmostKey()
{return removeKey(0);
}int Node::removeRightmostKey()
{return removeKey(KeyNumber - 1);
}Node* Node::removeChild(int index)
{Node* t = _children[index];_children.erase(_children.begin() + index);return t;
}Node* Node::removeLeftmostChild()
{return removeChild(0);
}Node* Node::removeRightmostChild()
{return removeChild(KeyNumber - 1);
}Node* Node::childLeftSibling(int index)
{return index > 0 ? _children[index - 1] : nullptr;
}Node* Node::childRightSibling(int index)
{return index == KeyNumber ? nullptr : _children[index + 1];
}void Node::moveToTarget(Node* target)
{int start = target->KeyNumber;if (!this->_leaf){for (int i = 0; i <= this->KeyNumber; i++){target->_children[start + i] = this->_children[i];}}for (int i = 0; i < this->KeyNumber; i++){target->_keys[target->KeyNumber++] = this->_keys[i];}
}

搭建remove删除方法的架子

首先明确一点要删除节点的前提是要先找到节点才能进行删除操作，所以remove方法最初的雏形就是找要删除的节点(采用递归进行查找)

 找节点的思路在上一篇blog新增节点时有体现，小吉在这也不详细讲解了，直接上代码👇

void BTree::remove(int key)
{doremove(_root, key,0);
}void BTree::doremove(Node* node, int key)
{int i = 0;while (i < node->KeyNumber){if (node->_keys[i] >= key){break;}i++;}if (node->_leaf)//叶子节点{if (i < node->KeyNumber && node->_keys[i] == key)//i找到：代表待删除key的索引{}else//i没找到{return;}}else//非叶子节点{if (i < node->KeyNumber && node->_keys[i] == key)//i找到：代表待删除key的索引{}else//i没找到：代表第i个孩子继续查找{doremove(node,node->_children[i], key,i);}}
}

remove删除情况分类

主要分为以下4种情况：
case1：当前节点是叶子节点，没找到
case2：当前节点是叶子节点，找到了
case3：当前节点是非叶子节点，没找到
case4：当前节点是非叶子节点，找到了

叶子节点

 分析当前节点是叶子节点的情况，这种情况比较简单，找到就删除当前节点要删除的key值（调用前面实现的九个小方法中的removeKey方法即可），没找到说明B树中没有我们要删除的key值，直接return退出即可。

if (node->_leaf)//叶子节点{if (i < node->KeyNumber && node->_keys[i] == key)//i找到：代表待删除key的索引{node->removeKey(i);}else//i没找到{return;}}

非叶子节点

没找到：递归继续寻找
找到：1.找后继的key 2.替换待删除的key 3.删除后继的key

else//非叶子节点{if (i < node->KeyNumber && node->_keys[i] == key)//i找到：代表待删除key的索引{//1.找到后继keyNode* s = node->_children[i + 1];while (!s->_leaf){s = s->_children[0];}int skey = s->_keys[0];//2.替换待删除keynode->_keys[i] = skey;//3.删除后继keydoremove(node,node->_children[i + 1], skey,i+1);}else//i没找到：代表第i个孩子继续查找{doremove(node,node->_children[i], key,i);}}

删除完不平衡的处理

  在删除节点完可能存在删除后key数目<下限（根节点除外），导致不平衡的情况
 对平衡的调整又可以分为一下三种情况：
case1：左边富裕，右旋
case2：右边富裕，左旋
case3：两边都不够借，向左合并
 void balance (Node* parent,Node* x,int i) //x为要调整的节点，i为被调整孩子的索引
 注： 为了实现平衡函数的传参，doremove方法还要再加上两个参数void BTree::doremove(Node* parent,Node* node, int key,int index)//index被删除节点的索引

左边富裕，右旋

右旋：1）父节点中前驱key旋转下来（前驱key是要删除节点的前驱）
2）left中最大的孩子换爹（被调整节点的左兄弟不为叶子节点要执行这一步）
2）left中最大的的key旋转上去

下面👇是代码实现旋转的过程：

void BTree::balance(Node* parent, Node* x, int i)
{Node* left = parent->childLeftSibling(i);if (left != nullptr && left->KeyNumber > MIN_KEYNUMS){//左边富裕，右旋x->insertKey(0, parent->_keys[i - 1]);if (!left->_leaf){x->insertChild(0, left->removeRightmostChild());}parent->_keys[i-1]= left->removeRightmostKey();return;}
}

右边富裕，左旋

左旋：1）父结点中后继key旋转下来（后继key是要删除节点的后继）
2）right中最小的孩子换爹（被调整节点的右兄弟不为叶子节点时要执行这一步）
3）right中最小的key旋转上去

 和左边富裕，右旋的情况类似，小吉这里就不画图了，直接上代码

void BTree::balance(Node* parent, Node* x, int i)
{Node* right = parent->childRightSibling(i);if (right != nullptr && right->KeyNumber > MIN_KEYNUMS){//右边富裕，左旋x->insertKey(x->KeyNumber, parent->_keys[i]);if (!right->_leaf){x->insertChild(x->KeyNumber+1, right->removeLeftmostChild());}parent->_keys[i] = right->removeLeftmostKey();return;}

两边都不够借，向左合并

case1：被调整节点有左兄弟，往左兄弟处合并
case2：被调整节点没有左兄弟，父节点和右边的兄弟向自己处合并

case1:

case2：

代码呈现👇：

//两边都不够借，向左合并if (left != nullptr){//向左兄弟合并parent->removeChild(i);left->insertKey(left->KeyNumber, parent->removeKey(i - 1));x->moveToTarget(left);}else{//向自己合并parent->removeChild(i + 1);x->insertKey(x->KeyNumber, parent->removeKey(i));right->moveToTarget(x);}

到这里，B树删除的所有涉及到的知识点都已经讲完了，下面小吉给大家提供一个B树删除的测试代码。

B树删除的测试代码

void testRemove()
{BTree tree(3);for (int i = 1; i <= 6; i++){tree.put(i);}tree.remove(2);Node* root = tree._root;Node* leftchild = root->_children[0];cout << root->_keys[0] << endl;for (int i = 0; i < leftchild->KeyNumber; i++){cout << leftchild->_keys[i] << ' ';}cout << endl;
}

到这里，这篇blog要结束了，有点小长，也有点小难，可能一次性看完对一些小可爱们有难度，不要急，慢慢看，多给自己一点时间❤️
（其实这篇博客从9月份写到了11月🤣，可以说是小吉已经发表的博客中最长的一篇了，也是最难的一篇，原计划打算九月份写完的，中途去备考了一下软设，所以就一直拖到现在才写完，不好意思耽误了这么久了😖）

&emps;最后，创作不易（这篇blog小吉真的写了很久），还望大家多多支持（点赞收藏关注小吉🌹）