idc网站模板,查看一下测绘项目招投标信息,wordpress 永久链接,建设银行官网入口哈喽啊#xff01;好久不见#xff0c;甚是想念#xff01;失踪人口要回归了#xff0c;时隔一个多月小吉我终于要更新blog了#x1f389;。在停更的一个多月中#xff0c;小吉也有在好好学习提升自己#xff0c;立志给大家呈现好文章。 现在让我们进入正题吧#xf… 哈喽啊好久不见甚是想念失踪人口要回归了时隔一个多月小吉我终于要更新blog了。在停更的一个多月中小吉也有在好好学习提升自己立志给大家呈现好文章。 现在让我们进入正题吧今天我们这篇blog主要讲用c实现B树上一篇blog讲的是二叉搜索树中间还有avl树和红黑树小吉还没有把博客写出来。希望大家多多关注小吉在完成这篇blog后小吉将会出avl树实现的博客浅浅期待一下吧。 老规矩在正式实现B树之前我们先来了解了解什么是B树。
B树的概念 B树B树是一种自平衡的树形数据结构用于解决磁盘存储器上的数据管理问题减少磁盘i/o操作的次数从而提高数据访问的效率。 B树的特征 在讲B树的特征之前我们先来了解一下度和阶的概念 度(degree)指树中节点孩子数 阶(order)指所有节点孩子数最大值 在m阶的B树中即孩子数最大值为m B树的特征 1.B树的每个节点可以有多个子结点每个节点最多可以有m个子节点除根节点和叶子节点外其他每个节点至少有ceil(m/2)个孩子。ceil是指向上取整 2.每个节点的关键字(键值)数量与子节点数量相关通常比子节点数量少1。每个节点中的关键字数量k满足ceil(m/2)-1km-1。 3.B树的所有叶子节点都在同一层 4.B树通过动态调整节点中的关键字数量来保持树的平衡 5.B树中的关键字按照升序排序 6.父节点中第i个关键字小于其第i个子节点的所有关键字且大于其第i-1个子节点中所有的关键字 小吉在这里提醒一下一定要好好理解B树的特征后面在实现的过程有什么不能理解的地方一定要回头好好读一下特征大部分问题都能在看过特征后得到解答小吉的小经验✨
B树节点类 _t代表最小度数也就是最小的孩子数ceil(m/2)因此最大孩子数m可以由2*t表示 节点类代码呈现
class Node
{
public:Node(int t, bool leaf true) :_t(t), _leaf(left), _children(2 * t, nullptr),_keys(2*t-1),KeyNumber(0){}//初始化列表
public:vectorint _keys;//键值vectorNode* _children;//孩子int KeyNumber;//有效键值数目bool _leaf;//是否为叶子节点int _t;//最小度数最小孩子数
};B树节点类成员方法
主要实现3个方法 1.Node* get(int key);//多路查找 2.void insertKey(int index,int key);//向指定索引处插入key 3.void insertChild(int index, Node* child);//向指定索引处插入child 代码呈现
Node* Node::get(int key)
{int i 0;while (i KeyNumber){if (_keys[i] key){return this;}if (_keys[i] key){break;}i;}//比key值大且为叶子节点if (this-_leaf){return nullptr;}//非叶子节点(采用递归)return _children[i]-get(key);
}void Node::insertKey(int index,int key)
{_keys.insert(_keys.begin() index, key);KeyNumber;
}void Node::insertChild(int index, Node* child)
{_children.insert(_children.begin() index, child);
}B树类
class BTree
{
public:BTree(int t) :_t(t), _root(new Node(t)), MAX_KEYNUMS(2 * t - 1), MIN_KEYNUMS(t - 1) { }//初始化列表
public:Node* _root;int _t;//树中最小度数const int MIN_KEYNUMS;const int MAX_KEYNUMS;
};注意const成员变量必须在构造函数的初始化列表中进行初始化而不能在构造函数体内部通过赋值语句来初始化 B树类成员方法 bool contains(int _key)//判断节点是否存在 代码实现
//是否存在bool contains(int _key){return _root-get(_key) ! nullptr;}B树put插入节点初实现 put实现思路 1.首先查找本节点中的插入位置如果没有空位key被找到应该走更新的逻辑 2.如果找到空位该节点是叶子节点可以直接插入该节点是非叶子节点需要继续在children[i]处继续递归插入 代码架构
void BTree::doput(Node* node, int key,Node* parent,int index)
{int i 0;while (i node-KeyNumber){if (node-_keys[i]key){node-_keys[i] key;//更新return;}if (node-_keys[i] key){break;//找到了插入位置}i;}if (node-_leaf){node-insertKey(i, key);}else{doput(node-_children[i], key,node,i);//递归}
}void BTree::put(int key)
{doput(_root, key,nullptr,0);
}B树split分裂 无论哪种情况插入完成后都可能超过节点keys数目限制应执行节点分裂 注较小的数字代表索引 void BTree::split(Node* left, Node* parent, int index) left为待分裂节点index是该待分裂节点作为孩子的索引 split分裂思路 1.创建right节点分裂后大于当前left节点的把t最小孩子数以后的key和child都拷贝过去 2.t-1处的key插入到parent的index处index指left作为孩子时的索引 3.right节点作为parent的孩子插入到index1处 分为三种情况待分裂节点为叶子节点非叶子节点和根节点。1️⃣我们先来实现最简单的一种情况待分裂节点为叶子节点。 代码展示
void BTree::split(Node* left, Node* parent, int index)
{
//1.创建right节点把left中t之后的key和child移动过去Node* right new Node(_t);right-_leaf left-_leaf;right-_keys.assign(left-_keys.begin() _t, left-_keys.end());right-KeyNumber _t - 1;left-KeyNumber _t - 1;//2.中间的key(t-1处)插入到父节点int mid left-_keys[_t - 1];parent-insertKey(index, mid);//3.right节点作为父节点的孩子parent-insertChild(index 1, right);
}实现叶子节点的分裂就按照上面的思路就可以了相对比较简单我们现在可以小小测试一下代码这里提供一个小的测试案例
void splitTest()//split分裂方法的测试案例
{BTree tree(2);Node* root tree._root;root-_leaf false;root-_keys[0] 2;root-KeyNumber 1;root-_children[0] new Node(2);root-_children[0]-_keys { 1 };root-_children[0]-KeyNumber 1;root-_children[1] new Node(2);root-_children[1]-_keys { 3,4,5 };root-_children[1]-KeyNumber 3;tree.split(root-_children[0], root, 0);
}分裂结果可以参照小吉上面给的图
2️⃣待分裂节点为非叶子节点这种情况就比叶子节点多一个步骤就是处理孩子 代码实现
void BTree::split(Node* left, Node* parent, int index)
{
//1.创建right节点把left中t之后的key和child移动过去Node* right new Node(_t);right-_leaf left-_leaf;right-_keys.assign(left-_keys.begin() _t, left-_keys.end());//分裂节点是非叶子节点的情况if (!left-_leaf){right-_children.assign(left-_children.begin() _t, left-_children.end());}right-KeyNumber _t - 1;left-KeyNumber _t - 1;//2.中间的key(t-1处)插入到父节点int mid left-_keys[_t - 1];parent-insertKey(index, mid);//3.right节点作为父节点的孩子parent-insertChild(index 1, right);
}3️⃣待分裂节点为根节点这里小吉先画个图来帮小可爱们想象一下 思路如果parentnullptr表示要分裂的是根节点此时需要创建新根原来的根节点作为新根的0索引孩子 代码实现
if (parent nullptr)//分裂的是根节点{Node* newRoot new Node(_t);newRoot-_leaf false;newRoot-insertChild(0, left);this-_root newRoot;parent newRoot;}三种情况已经全部分析完了现在小吉把三种情况的代码进行汇总封装在split方法中
void BTree::split(Node* left, Node* parent, int index)
{if (parent nullptr)//分裂的是根节点{Node* newRoot new Node(_t);newRoot-_leaf false;newRoot-insertChild(0, left);this-_root newRoot;parent newRoot;}//1.创建right节点把left中t之后的key和child移动过去Node* right new Node(_t);right-_leaf left-_leaf;right-_keys.assign(left-_keys.begin() _t, left-_keys.end());//分裂节点是非叶子节点的情况if (!left-_leaf){right-_children.assign(left-_children.begin() _t, left-_children.end());}right-KeyNumber _t - 1;left-KeyNumber _t - 1;//2.中间的key(t-1处)插入到父节点int mid left-_keys[_t - 1];parent-insertKey(index, mid);//3.right节点作为父节点的孩子parent-insertChild(index 1, right);
}节点的分裂到这里已经全部讲完了下面就是要把split方法和put方法结合起来
B树put插入节点最终实现 思路叶子节点加入key时要做分裂的检查当节点中的有效键值数等于最大键值数时要进行节点的分裂 void BTree::put(int key)
{doput(_root, key,nullptr,0);
}void BTree::doput(Node* node, int key,Node* parent,int index)
{int i 0;while (i node-KeyNumber){if (node-_keys[i]key){node-_keys[i] key;//更新return;}if (node-_keys[i] key){break;//找到了插入位置}i;}if (node-_leaf){node-insertKey(i, key);}else{doput(node-_children[i], key,node,i);//递归}if (node-KeyNumber MAX_KEYNUMS)//进行分裂{split(node, parent, index);}
}这篇blog到这里已经全部结束了浅浅预告一下小吉的下一篇blog讲的是B树的删除操作又是一个大工程️还望大家多多支持小吉❤️ 这篇博客有点长也有点难希望小可爱们给自己多一点耐心静下心来慢慢学还有一定要敲代码只有敲了代码才能发现问题。
创作不易还望大家多多支持小吉写了整整3个小时
