h5手机网站建设,安康免费做网站,好看的免费的小说网站模板,跨境网站书接上回小吉讲的是B树的搭建和新增方法的实现#xff08;blog传送门#x1f6aa;#xff1a;B树实现上#xff09;#xff08;如果有小可爱对B树还不是很了解的话#xff0c;可以先看完上一篇blog#xff0c;再来看小吉的这篇blog#xff09;。那这一篇主要讲的是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,i1);}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是要删除节点的前驱 2left中最大的孩子换爹被调整节点的左兄弟不为叶子节点要执行这一步 2left中最大的的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是要删除节点的后继 2right中最小的孩子换爹被调整节点的右兄弟不为叶子节点时要执行这一步 3right中最小的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-KeyNumber1, 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小吉真的写了很久还望大家多多支持点赞收藏关注小吉
