书接上回小吉讲的是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.找到后继key
Node* s = node->_children[i + 1];
while (!s->_leaf)
{
s = s->_children[0];
}
int skey = s->_keys[0];
//2.替换待删除key
node->_keys[i] = skey;
//3.删除后继key
doremove(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小吉真的写了很久),还望大家多多支持(点赞收藏关注小吉🌹)