【高阶数据结构】B-树详解

文章目录

  • 1. 常见的搜索结构
  • 2. 问题提出
    • 使用平衡二叉树搜索树的缺陷
    • 使用哈希表的缺陷
  • 3. B-树的概念
  • 4. B-树的插入分析
    • 插入过程分析
    • 插入过程总结
  • 5. B-树的代码实现
    • 5.1 B-树的结点设计
    • 5.2 B-树的查找
    • 5.3 B-树的插入实现
      • InsertKey
      • 插入和分裂
      • 测试
  • 6. B-树的删除(思想)
  • 7. B-树的高度
    • 最小高度
    • 最大高度
  • 8. B-树的性能
  • 9. B-树的简单验证(中序遍历)

1970年,R.Bayer和E.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树,称为B树。

那么在此之前,我们也已经学过很多的搜索结构了,我们来一起回顾一下:

1. 常见的搜索结构

在这里插入图片描述
以上结构适合用于数据量相对不是很大,能够一次性存放在内存中,进行数据查找的场景(内查找)。

2. 问题提出

如果数据量很大,比如有100G数据,无法一次放进内存中,那就只能放在磁盘上了,如果放在磁盘上,有时需要搜索某些数据,那么该如何处理呢?

我们可以考虑将关键字及其映射的数据的地址放到一个内存中的搜索树的节点中,当通过搜索树找到要访问数据的关键字时,取这个关键字对应的地址去磁盘访问数据。
在这里插入图片描述

但是呢,实际中我们去查找的这个key可能不都是整型:

可能是字符串比如身份证号码,那这时我们还把所有的key和对应数据的地址都存到内存,也可能是存不下的。

那这时候可以做一个改动:

我不再存储key了,只存储地址
在这里插入图片描述
那这样的话我如何判断找到了呢?
那就需要拿着当前的地址去访问磁盘进行判断。
比如现在要找key为77的这个数据,那从根结点开始,首先访问根结点中的地址对应磁盘的数据,是34,那77大于34,所以往右子树找,右子树0x77对应的是89(有一次访问磁盘),77比89小,再去左子树找,左子树地址0x56访问磁盘对应的是77找到了。

那这样做的问题是什么呢?

最坏的情况下我们要进行高度次的查找,那就意味着要进行高度次的磁盘IO。
如果我们使用红黑树或者AVL树的话,就是O( l o g 2 N log_2 N log2N)次。
那如果是在内存中的话,这个查找次数还是很快的,但是现在数据量比较大是在磁盘上存的,而磁盘的速度是很慢的。

所以:

使用平衡二叉树搜索树的缺陷

平衡二叉树搜索树的高度是logN,这个查找次数在内存中是很快的。但是当数据都在磁盘中时,访问磁盘速度很慢,在数据量很大时,logN次的磁盘访问,是一个难以接受的结果。

那如果用哈希表呢?

使用哈希表的缺陷

哈希表的效率很高是O(1),但是一些极端场景下某个位置哈希冲突很严重,导致访问次数剧增,也是难以接受的。

那如何加速对数据的访问呢?

1. 提高IO的速度(SSD相比传统机械硬盘快了不少,但是还是没有得到本质性的提升)
2. 降低树的高度——多叉树平衡树

那我们今天要学的B-树其实就是多叉平衡搜索树

3. B-树的概念

1970年,R.Bayer和E.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树并且是绝对平衡,称为B树(后面有一个B树的改进版本B+树,然后有些地方的B树写的的是B-树,注意不要误读成"B减树")。

一棵m阶(m>2)的B树(B树中所有结点的孩子个数的最大值称为B树的阶),是一棵M路的平衡搜索树,可以是空树或者满足一下性质的树:

在这里插入图片描述
1. 树中每个结点至多有m棵子树,即至多含有m-1个关键字。
2. 若根结点不是终端结点,则至少有两棵子树。
3. 除根结点外的所有非叶子结点都包含k-1个关键字和k个孩子(终端结点孩子都是NULL),其中 ceil(m/2) ≤ k ≤ m (ceil是向上取整函数)
4. 所有的叶结点都出现在同一层次上,并且不带信息(可以视为外部结点或类似于折半查找判定树的查找失败结点,实际上这些结点不存在,指向这些结点的指针为空)
5. 每个节点中的关键字从小到大(也可以从大到小)排列,节点当中k-1个元素正好是k个孩子包含的元素的值域划分
6. 每个结点的结构为:(n,A0,K1,A1,K2,A2,… ,Kn,An)其中,Ki(1≤i≤n)为关键字,且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1,Ai+1所指子树所有结点中的关键字均大于Ki+1。(结点中关键字升序的情况下)
n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。

大家可以对照上面的图先来自行理解一下B树的这些性质,等后面我们熟悉了B树的结构之后大家可以再来反复理解这几条性质为什么是这样。
在这里插入图片描述

4. B-树的插入分析

那下面我们就来学习一下B-树的插入是怎样的。

那为了方便讲解,也方便大家理解,我们这里选取B-树的阶数取小一点,给一个3:

即三阶B-树(三叉平衡树),那每个结点最多存储两个关键字,两个关键字可以将区间分割成三个部分,因此节点应该有三个孩子(子树)
那每个结点的结构就应该是这样的在这里插入图片描述

但是呢,为了后续实现起来简单,节点的结构如下:

在这里插入图片描述
关键字和孩子我们都多给一个空间(后面大家就能体会到为什么要多给一个)

插入过程分析

那下面我们就来找一组数据分析一下插入的过程,用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下:

1. 插入53
在这里插入图片描述
满足B-树的性质,不用动
2. 插入139(关键字我们升序排列)
在这里插入图片描述
也不用做任何处理
3. 插入75
在这里插入图片描述
75插入之后是这样,但是因为我们多开了一个空间,3阶的话每个结点最多3-1=2个关键字。
所以现在这个结点关键字个数超了。
那此时怎么办呢?
要进行一个操作——分裂
怎么分裂呢?
在这里插入图片描述
1. 找到关键字序列的中间数,将关键字序列分成两半
2. 新建一个兄弟结点出来,将右半边的m/2个关键字分给兄弟结点
3. 将中间值提给父亲结点,新建结点成为其右孩子(没有父亲就创建新的根)
为什么中位数做父亲?——满足搜索树的大小关系(左<根<右)
4. 结点指针链接起来
在这里插入图片描述
那通过这里大家来体会一下上面的规则中为什么要求除根结点外的所有非叶子结点都包含k-1个关键字(ceil(m/2) ≤ k ≤ m,即k的最小值是ceil(m/2)),即最少包含ceil(m/2)-1个关键字
如果m是奇数比如9,那ceil(m/2)是5个,5-1是4,而9个的话分裂之后正好两边每个结点都是4个关键字,中间的一个提取给父亲。
如果是偶数比如10的话,ceil(m/2)是5,5-1是4,而10个分裂的话,肯定不平均,一边4个(最少的),一边5个,还有一个中间值要提取给父亲。
所以它们最少就是ceil(m/2)-1个关键字。

那我们再来插入几个看看:

还是我们上面给的那组数据,再往后插入49,145
在这里插入图片描述
在这里插入图片描述
接着再往后,36
在这里插入图片描述
那此时36插入的这个结点又满了,然后就要进行分裂。
大家现在体会,为什么我们要多开一个空间?这样的话我们就可以在插入之后关键字顺序已经调整好的情况下去分裂,就方便很多。
那然后我们来看这里的分裂怎么做?
在这里插入图片描述
新增一个兄弟结点之后,相当于它们的父亲结点就多了一个孩子,所以也需要增加一个关键字(关键值始终比孩子少一个),就把中间值提给父亲结点。
49上提插入到父亲,它比75小,所以45往后移(它的孩子也跟着往后移),然后49插入到前面。

再往下插入101:

在这里插入图片描述
那插入之后这个结点的关键字数量大于m-1了,进行分裂
分裂的步骤还是和上面一样
在这里插入图片描述
但是此时分裂之后我们发现父亲满了,所以需要继续向上分裂
在这里插入图片描述
那这就是一个完整的插入过程。
并且我们会发现B-树每一次插入之后他都是天然的完全平衡,不需要想红黑树AVL树那样,插入之后不满足平衡条件了,再去调整。
并且B-树的平衡是绝对平衡。每一棵树的左右子树高度之差都是0。
为什么他能保持天然的完全平衡呢?
通过上面的插入过程我们很容易发现B-树是向右和向上生成的,只会产生新的兄弟和父亲。

插入过程总结

  1. 如果树为空,直接插入新节点中,该节点为树的根节点
  2. 树非空,找待插入关键字在树中的插入位置(注意:找到的插入节点位置一定在终端节点中)
  3. 检测是否找到插入位置(假设树中的key唯一,即该元素已经存在时则不插入)
  4. 按照插入排序的思想将该关键字插入到找到的结点中
  5. 检测该节点关键字数量是否满足B-树的性质:即该节点中的元素个数是否等于M,如果小于则满足,插入结束
  6. 如果插入后节点不满足B树的性质,需要对该节点进行分裂:
    申请新的兄弟节点
    找到该节点的中间位置
    将该节点中间位置右侧的元素以及其孩子搬移到新节点中
    将中间位置元素(新建结点成为其右孩子)提取至父亲结点中插入,从步骤4重复上述操作

5. B-树的代码实现

那下面我们就来写写代码

5.1 B-树的结点设计

那首先我们来定义一下B-树的结点:

我们这里还是搞成模板,简单一点,我们就不实现成KV模型了,就搞个K,当然在搞个非类型模板参数M控制B树的阶
template<class K, size_t M>
然后结点的话,我们上面分析过一棵3阶的B-树
在这里插入图片描述
为了方便插入之后分裂,我们要多开一个空间:正常每个结点最多M-1个关键字,M个孩子;那增加一个就是M个关键字,M+1个孩子。
那我们如何定义这样一个结构呢?
在这里插入图片描述
那这就是两个数组嘛。
然后还需要一个父亲指针,指向父结点;还需要再给一个成员变量记录当前结点实际存储关键字的个数
然后我们也可以写一个默认构造
在这里插入图片描述
那结点我们就定义好了

5.2 B-树的查找

那我们先来实现一个find,因为后面插入也要先find嘛:

这里我们实现一个不允许键值冗余的版本,如果存在就不再插入了,如果不存在我们让find直接给我们返回找到的那个要插入位置的结点,便于我们在Insert函数中直接将值插入到该结点中。

画个图我们来分析一下:

在这里插入图片描述
就比如这个图,我们现在要查找53。
那首先和根结点的关键字进行比较,当前根结点只有一个值75,53小于75,所以去他的左子树查找。
那我们来分析一下一个关键字和它的左右孩子之间的关系:
在这里插入图片描述
其实很容易看出来,在b-树中
一个关键字的左孩子在_child数组中的下标和该关键字在_keys数组中的下标是一样的,而右孩子的话,比关键字的下标大1
在这里插入图片描述
所以就走到它的左子树49这个结点,也只有一个关键字,53大于49,所以再去关键字49的右子树(如果49后面还有关键字的话,就继续跟后面的比)
在这里插入图片描述
那此时就走到50,53这个结点。
首先跟第一个关键字50比,比50大,那就继续往后比,后面是53,相等,找到了
那如果查找52呢(不存在)?
前面是一样的,走到这个结点,比50大,往后比,比53小,所以去53的左子树,53的左子树为空,所以找不到了。
在这里插入图片描述

find就写好了:

pair<Node*, int> Find(const K& key)
{Node* parent = nullptr;//从根结点开始找Node* cur = _root;while (cur){// 在一个结点中查找size_t i = 0;while (i < cur->_n){if (key < cur->_keys[i]){break;}else if (key > cur->_keys[i]){++i;}else{return make_pair(cur, i);}}// 往孩子结点去跳parent = cur;cur = cur->_subs[i];}//没找到,返回parentreturn make_pair(parent, -1);
}

5.3 B-树的插入实现

接下来我们来写一下插入:
在这里插入图片描述

首先如果是第一次插入的话我们需要做一个单独处理:

判断root==nullptr,为空的话就是第一次插入

if (_root == nullptr)
{_root = new Node;_root->_keys[0] = key;_root->_n++;return true;
}

那再往下呢就是已经有结点的情况下插入:

那首先判断一下如果key已经存在,就不再插入
在这里插入图片描述

如果不存在,那就去插入(find顺便带回了要插入的那个目标位置的结点)
那我们接收一下find的返回值,在这个结点里面插入即可

InsertKey

那插入的时候需要保证结点里面关键字的顺序,可以用插入排序的思想把新的关键字插进去(如果是分裂之后向父亲插入的话,它可能还有孩子),那我们这里再单独封装一个InsertKey的函数:

在这里插入图片描述
代码就是这样的,插入排序如果大家遗忘了可以看之前的文章,还有不理解的地方建议大家看着我们上面分析插入的图走一遍代码

void InsertKey(Node* node, const K& key, Node* child)
{int end = node->_n - 1;while (end >= 0){if (key < node->_keys[end]){// 挪动key和他的右孩子node->_keys[end + 1] = node->_keys[end];node->_subs[end + 2] = node->_subs[end + 1];--end;}else{break;}}node->_keys[end + 1] = key;node->_subs[end + 2] = child;if (child){child->_parent = node;}node->_n++;
}

插入和分裂

然后我们就可以调用InsertKey接口去插入关键字,但是插入的话:

按理说是插入一次,但是如果插入之后存储关键字的数组满了(我们多开了一个空间,满的话就不满足B-树的性质——至多含有m-1个关键字了),就需要进行分裂
分裂的话,就又需要往parent去插入(插入中间值),当然分裂的兄弟结点也要成为parent的孩子(孩子和关键字都增加1,依然符合规则)
然后插入之后满了还需要再往上分裂,所以应该写成一个循环

最终完整的Insert函数:

在这里插入图片描述
这里还是比较麻烦的,不过注释写的比较清晰了,我就不过多解释了。
建议大家对照着我们上面画的图去理解。

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node;_root->_keys[0] = key;_root->_n++;return true;}// key已经存在,不再插入pair<Node*, int> ret = Find(key);if (ret.second != -1){return false;}// 如果不存在,find顺便带回了要插入的那个目标位置的结点//因为后面可能需要分裂继续往父结点插入,//所以这里我们接收find的返回值直接命名为parentNode* parent = ret.first;//参数中的key,const修饰不能修改,定义一个newkeyK newKey = key;//分裂的兄弟也要作为孩子插入到父结点,所以再定义一个child//当然第一次插入关键字的时候孩子是空Node* child = nullptr;//有可能多次分裂往上一直插入,所以需要写成循环while (1){InsertKey(parent, newKey, child);// 没有满,插入就结束if (parent->_n < M){return true;}else// 满了就要分裂{size_t mid = M / 2;// 分裂一半[mid+1, M-1]给兄弟Node* brother = new Node;size_t j = 0;size_t i = mid + 1;for (; i <= M - 1; ++i){// 拷贝key和key的左孩子给兄弟结点brother->_keys[j] = parent->_keys[i];brother->_subs[j] = parent->_subs[i];//如果孩子不为空,链接父亲指针if (parent->_subs[i]){parent->_subs[i]->_parent = brother;}++j;// 拷走的key清除重置一下方便调式观察parent->_keys[i] = K();parent->_subs[i] = nullptr;}// 还有最后一个右孩子也拷过去brother->_subs[j] = parent->_subs[i];if (parent->_subs[i]){parent->_subs[i]->_parent = brother;}parent->_subs[i] = nullptr;//重新设置它们的有效关键字数量brother->_n = j;parent->_n -= (brother->_n + 1);//+这个1是因为还提走了中位数K midKey = parent->_keys[mid];//清除重置提走的mid中位数parent->_keys[mid] = K();if (parent->_parent == nullptr)// 说明分裂是根节点{//那要创建新的根_root = new Node;_root->_keys[0] = midKey;//上面分裂的结点及分裂出的兄弟成为新的根的孩子_root->_subs[0] = parent;_root->_subs[1] = brother;_root->_n = 1;//将原结点和分裂的兄弟链接到新的根上parent->_parent = _root;brother->_parent = _root;break;}else// 分裂的不是根,转换成往parent->parent 去插入parent->[mid] 和 brother{newKey = midKey;child = brother;parent = parent->_parent;}}}return true;
}

测试

那下面我们就来构建一棵树来测试一下:

就拿我们上面画图分析对应的那棵树:
在这里插入图片描述
我们通过监视窗口来观察一下
在这里插入图片描述
对比一下,是没什么问题的。

6. B-树的删除(思想)

学习B树的插入足够帮助我们理解B树的特性了,那至于删除呢我们这里可以给大家讲一讲思路,代码的话我们就不实现了,删除的代码也要比插入更加复杂,大家有兴趣的话呢可以参考《算法导论》-- 伪代码和《数据结构-殷人昆》–C++实现代码。

那下面我们来讲一下删除的思想:

同样也需要分情况讨论:

  1. 删除的关键字在非终端结点
    处理方法是:
    用其直接前驱或直接后继替代其位置,转化为对“终端结点”的删除
    直接前驱:当前关键字左边指针所指子树中“最右下”的元素
    直接后继:当前关键字右边指针所指子树中“最左下”的元素
    比如:
    在这里插入图片描述
    现在要删除75
    首先第一种方法可以用直接前驱55替代其位置
    在这里插入图片描述
    或者用直接后继101替代
    在这里插入图片描述
    所以对非终端结点关键字的删除操作,必然可以转化为对终端结点的删除

所以下面我们重点来讨论终端结点的删除

  1. 删除的关键字在终端结点且删除后结点关键字个数未低于下限
    若删除后结点关键字个数未低于下限ceil(m/2)-1,直接删除,无需做任何其它处理
    比如:
    在这里插入图片描述
    现在要删除36,所在的结点是终端结点,且删除之后,关键字的个数不少于ceil(3/2)-1=1,所以直接删除即可
    在这里插入图片描述

那如果删除之后关键字的个数低于下限ceil(m/2)-1呢?

  1. 若删除的关键字在终端结点且删除后结点关键字个数低于下限ceil(m/2)-1
    这时候的处理思路是这样的:
    删除之后关键字数量低于下限,那就去“借”结点,跟父亲借,父亲再去跟兄弟借
    如果不能借(即借完之后父亲或兄弟关键字个数也不满足了),那就按情况进行合并(可能要合并多次)

    最终使得树重新满足B-树的性质。
    比如:
    在这里插入图片描述
    现在要删40,那40删掉的话这个结点关键字个数就不满足性质了,那就去跟父亲借,49借下来,那这样父亲不满足了,父亲再向兄弟借(要删除的那个关键字所在结点的兄弟结点),53搞上去
    变成这样
    在这里插入图片描述
    此时就又符合是一棵B-树了
    那如果不能借的情况呢?
    比如:
    在这里插入图片描述
    现在要删除160
    160如果跟父亲借的话,150下来,那父亲不满足了,因为3个孩子,必须是2个关键字。而且此时兄弟145所在的这个结点也不能借了。因为此时它只有一个关键字,父亲借走一个的话,就不满足了。
    所以此时借结点就不行了,就需要合并了。
    如何合并呢?
    如果结点不够借,则需要将父结点内的关键字与兄弟进行合并。合并后导致父节点关键字数量-1,可能需要继续合并。
    那我们先来看这个
    在这里插入图片描述
    这个情况我们分析了不够借,所以要合并。大家看,160删掉的话,父亲就少了一个孩子,那关键字也应该减少一个,所以可以把父结点的150与145这个孩子合并
    在这里插入图片描述
    这样就可以了。
    当然还有些情况可能需要多次合并:
    比如:
    在这里插入图片描述
    现在要删145,怎么办呢?
    肯定是不够借的,所以要合并,确保合并之后依然满足B-树的规则就行了。
    大家看这个可以怎么合并:
    145干掉之后,左子树这里就不满足了,可以先将139跟102合并。
    在这里插入图片描述
    但是此时不平衡了(B-树是绝对平衡的)。
    那就要继续合并缩减高度:
    很容易看出来,我们可以将101和53合并作为根,这个正好两个关键字,3个孩子
    在这里插入图片描述
    就可以了

7. B-树的高度

问:含n个关键字的m阶B树,最小高度、最大高度是
多少?(注:大部分地方算B树的高度不包括叶子结点即查找失败结点)

最小高度

首先我们来分析一下最小高度:

n个关键字的m阶B树,关键字个数和B-树的阶数已经确定的话,那要让高度最小,我们是不是要让每个结点存的关键字是最满的啊。
那对于m阶的B树来说,每个结点最多m-1个关键字,m个孩子
第一层肯定只有一个根结点(最满的话是m-1个关键字,m个孩子),那第二层最多就有m个结点,每个结点最多m-1关键字,那第三层就是m*m个孩子嘛,以此类推…
那我们假设这个高度是h的话,关键字的总个数n就等于(关键字个数*结点个数):
(m-1)*(1+m+m^2+m^3+…+m^h-1)
即有:
n=(m-1)*(1+m+m^2+m^3+…+m^h-1)
解得最小高度h= l o g m ( n + 1 ) log_m(n+1) logm(n+1)

最大高度

那最大高度呢:

那要让树变得尽可能高的话,那就要让每个结点得关键字数量尽可能少(分支尽可能少)。
第一层只有一个根结点(关键字最少是1,孩子是2),根结点最少两个孩子/分支,所以第二层2个结点。
又因为除了根结点之外的结点最少有ceil(m/2)个孩子,所以第三层就最少有2*ceil(m/2)个结点,第四层就是2*ceil(m/2)^2,以此类推…
第h就是2*ceil(m/2)^h-2个结点。
那么叶子结点(查找失败结点)的个数就是2*ceil(m/2)^h-1
那这里我们不再像上面那样求出总的关键字个数去算,怎么算呢?
这里补充一个结论:n个关键字的B-树必然有n+1个叶子节点
所以我们得出:
n+1=2*ceil(m/2)^h-1
那么解得最大高度h=[ l o g c e i l ( m / 2 ) ( n + 1 ) / 2 log_{ceil(m/2)}(n+1)/2 logceil(m/2)(n+1)/2] +1

当然也可以算出关键字的总个数来求解:

上面我们已经知道每层的结点个数,然后我们知道根结点最少一个关键字,其它结点最少k-1个关键字,k最小是ceil(m/2)
那么第一层就是1个关键字,第二层往后就是该层的节点个数*每个结点的最小关键字个数(k-1)
在这里插入图片描述
那么因此就有n=1+2(kh-1-1)
同样解得最大高度:
h=[ l o g c e i l ( m / 2 ) ( n + 1 ) / 2 log_{ceil(m/2)}(n+1)/2 logceil(m/2)(n+1)/2] +1

8. B-树的性能

B-树的效率是很高的,对于N = 62*1000000000个节点,如果度M为1024。
查找的坏最坏就是高度次嘛,h=[ l o g c e i l ( M / 2 ) ( N + 1 ) / 2 log_{ceil(M/2)}(N+1)/2 logceil(M/2)(N+1)/2] +1≈ l o g m / 2 N log_{m/2}N logm/2N
l o g m / 2 N log_{m/2}N logm/2N <= 4,即在620亿个元素中,如果这棵树的度为1024,则需要小于4次即可定位到该节点,然后利用二分查找可以快速定位到该元素,大大减少了读取磁盘的次数。

9. B-树的简单验证(中序遍历)

那B-树呢也是搜索树,同样满足左子树<根<右子树,那我们可以对它进行一个验证,看中序遍历是否能得到一个有序序列。

那下面我们就来实现一下B-树的中序遍历:

我们还是来搞一个图对照着分析一下思路:
在这里插入图片描述
就拿这个来分析:
对于我们之前学的二叉树来说中序遍历的思想是:左子树、根、右子树
那B-树的话它可能是一个多叉的,那它的中序遍历应该怎么走呢?
首先肯定还是先访问左子树,搜索树中最左的结点一定是最小的
在这里插入图片描述
当然如果算上空结点的话最左的应该是空,左子树,然后依然是根,就是36,36就是最小的,没问题。
左子树、根,那然后呢?
是36的右子树吗?可以认为是36的右子树,但是我们要把它当作40的左孩子看。
36这个关键字访问完,就走到后面的40,对于40,同样是先左子树,再根
在这里插入图片描述
那这个第二个访问到的元素就是40,此时当前结点所有的关键字访问完了,最后再去访问最后一个关键字的右子树:
在这里插入图片描述
此时整个结点才被访问完。
那此时就相当于是49的左子树访问完了,然后访问根49,后面就是一样的处理…
在这里插入图片描述
在这里插入图片描述
🆗,大家看这样就可以了
所以B-树的中序遍历是怎么样的呢?
左子树、根;(下一个关键字的)左子树、根;(再下一个)左子树、根;…(一直往后直至走完最后一个关键字);右子树(最后一个关键字的右子树)
左 根 左 根 … 右

那理清了思路,我来实现一下代码:

在这里插入图片描述
注释写的比较清晰,就不多解释了

// 左 根  左 根  ...  右
void _InOrder(Node* root)
{if (root == nullptr)return;size_t i = 0;//依次访问当前结点中每个关键字的左子树和根for (; i < root->_n; i++){_InOrder(root->_subs[i]);//先访问左子树cout << root->_keys[i] << " ";//再访问根}_InOrder(root->_subs[i]);//再访问最后一个关键字的右子树
}void InOrder()
{_InOrder(_root);
}

那我们来验证一下呗,中序遍历一下我们上面插入之后的那个B-树:

在这里插入图片描述
没有问题!

那对于B-树的讲解我们就先到这里…
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/253417.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Redis 命令大全

文章目录 启动与连接Key&#xff08;键&#xff09;相关命令String&#xff08;字符串&#xff09;Hash&#xff08;哈希&#xff09;List&#xff08;列表&#xff09;Set&#xff08;集合&#xff09;Sorted Set&#xff08;有序集合&#xff09;其他常见命令HyperLogLog&…

WordPress如何实现随机显示一句话经典语录?怎么添加到评论框中?

我们在一些WordPress网站的顶部或侧边栏或评论框中&#xff0c;经常看到会随机显示一句经典语录&#xff0c;他们是怎么实现的呢&#xff1f; 其实&#xff0c;boke112百科前面跟大家分享的『WordPress集成一言&#xff08;Hitokoto&#xff09;API经典语句功能』一文中就提供…

相机图像质量研究(6)常见问题总结:光学结构对成像的影响--对焦距离

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…

Spring Data Envers 数据审计实战

随着各行各业信息化发展&#xff0c;决策者们越来越意识到数据版本追踪的重要性&#xff0c;尤其是上市公司&#xff0c;数据对于他们尤为重要。考虑到研发成本&#xff0c;对重要表单数据支持页面级的修改历史查看、对所有业务数据支持DB级的版本查看是一个不错的选择。 对于…

闲聊电脑(5)装个 Windows(一)

​夜深人静&#xff0c;万籁俱寂&#xff0c;老郭趴在电脑桌上打盹&#xff0c;桌子上的小黄鸭和桌子旁的冰箱又开始窃窃私语…… 小黄鸭&#xff1a;冰箱大哥&#xff0c;上次说到硬盘分区和格式化&#xff0c;弄完之后&#xff0c;就该装系统了吧&#xff1f; 冰箱&#x…

【iOS ARKit】人形遮挡

人形遮挡简介 在 AR系统中&#xff0c;计算机通过对设备摄像头采集的图像进行视觉处理和组织&#xff0c;建立起实景空间&#xff0c;然后将生成的虚拟对象依据几何一致性原理嵌入到实景空间中&#xff0c;形成虚实融合的增强现实环境&#xff0c;再输出到显示系统中呈现给使用…

华为配置内部人员接入WLAN网络示例(802.1X认证)

配置内部人员接入WLAN网络示例&#xff08;802.1X认证&#xff09; 组网图形 图1 配置802.1X认证组网图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件 业务需求 用户接入WLAN网络&#xff0c;使用802.1X客户端进行认证&#xff0c;输入正确的用户名和密…

智慧城市:打造低碳未来,引领城市数字化转型新篇章

在“万物皆可数字化”的新时代浪潮下&#xff0c;智慧城市作为未来城市发展的先锋方向&#xff0c;正在以前所未有的速度和规模重塑我们的城市面貌。 智慧城市不仅是一个技术革新的标志&#xff0c;更是城市治理、民生服务等领域全面升级的重要引擎。 一、智慧城市的多元应用领…

Web前端入门 - HTML JavaScript Vue

ps&#xff1a;刚开始学习web前端开发&#xff0c;有什么不正确、不标准的内容&#xff0c;欢迎大家指出~ Web简介 90年代初期&#xff0c;Web1.0&#xff0c;静态页面&#xff0c;不和服务器交互&#xff0c;网页三剑客指Dreamweaver、Fireworks、Flash2000年代中期&#xf…

神经网络的权重是什么?

请参考这个视频https://www.bilibili.com/video/BV18P4y1j7uH/?spm_id_from333.788&vd_source1a3cc412e515de9bdf104d2101ecc26a左边是拟合的函数&#xff0c;右边是均方和误差&#xff0c;也就是把左边的拟合函数隐射到了右边&#xff0c;右边是真实值与预测值之间的均方…

Stable Diffusion 模型下载:Schematics(原理图)

文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十 下载地址 模型介绍 “Schematics”是一个非常个性化的LORA&#xff0c;我的目标是创建一个整体风格&#xff0c;但主要面向某些风格美学&#xff0c;因此它可以用于人物、物体、风景等…

spring boot整合 cache 以redis服务 处理数据缓存 便捷开发

我们常规开发中 就是程序去数据库取数据 然后返回给客户端 但是 如果有些业务业务量非常庞大 不断访问数据库 性能就会非常糟糕 从而造成不好的用户体验 那么 我们自然就可以将数据查到缓存中 然后 用户访问 从缓存中取 这样就会大大提高用户的访问效率 之前 我的文章 java …

CSS之盒子模型

盒子模型 01-选择器 结构伪类选择器 基本使用 作用&#xff1a;根据元素的结构关系查找元素。 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IE…

OpenCV-30 腐蚀操作

一、引入 腐蚀操作也是用卷积核扫描图像&#xff0c;只不过腐蚀操作的卷积核一般都是1&#xff08;卷积核内的每个数字都为1&#xff09;&#xff0c;如果卷积核内所有像素点都是白色&#xff0c;那么锚点&#xff08;中心点&#xff09;即为白色。 大部分时候腐蚀操作使用的都…

ROS2 CMakeLists.txt 和 package.xml

这里记录一下ROS2中功能包package.xml和CMakeLists.txt的格式。以LIO-SAM的ROS2版本为例&#xff1a; 一&#xff1a;CMakeLists.txt cmake_minimum_required(VERSION 3.5) project(lio_sam)if(NOT CMAKE_BUILD_TYPE AND NOT CMAKE_CONFIGURATION_TYPES)set(CMAKE_BUILD_TYPE…

【Linux】信号-下

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;题目解析 &#x1f30e;推荐文章&#xff1a;【LeetCode】winter vacation training 目录 &#x1f449;&#x1f3fb;信号递达&#xff0c;信号未决&#x…

天地伟业接入视频汇聚/云存储平台EasyCVR详细步骤

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…

RabiitMQ延迟队列(死信交换机)

Dead Letter Exchange&#xff08;死信交换机&#xff09; 在MQ中&#xff0c;当消息成为死信&#xff08;Dead message 死掉的信息&#xff09;后&#xff0c;消息中间件可以将其从当前队列发送到另一个队列中&#xff0c;这个队列就是死信队列。而 在RabbitMQ中&#xff0c;由…

计算机今年炸了99%的人都踩了这个坑

24年408考研&#xff0c;如果只用王道的复习资料&#xff0c;最多考100-120分 就是这么的现实&#xff0c;王道的资料虽然好&#xff0c;但是并不能覆盖全部的知识点和考点&#xff0c;而且24年的408真题考的很怪&#xff0c;总结起来就是下面这些特点&#xff1a; 偏&#x…

VM安装Centos7

目标&#xff1a; 一&#xff0c;安装Centos7 二&#xff0c;ssh可以连接 1 新建虚拟机 一直下一步 2 直到此处&#xff0c;选择稍后安装 一直下一步直到完成。 3 选中虚拟机&#xff0c;点击设置 选择CD/DVD&#xff0c;选取ISO映像文件。 4 等待安装 并且设置root密码 5…