函数insert中序遍历

在前面的学习过程中我们见过很多搜索结构比比如说顺序查找二分查找搜索二叉树平衡二叉树哈希表如果数据量不是很大能够一次性放在内存中的话上面的结构是没有问题的如果要处理的数据非常多的话就得对上面的结构进行处理比如说平衡二叉树如果数据不是很多的话平衡二叉树的每个节点会存储两个数据一个是用于比较和查找的关键字K另外一个就是存储的数据V如果存储的数据非常多并且每个数据占用的内存非常大的话那这里就得做出更改将存储的数据放到磁盘上而数据V里面存储的就是对应数据在磁盘上的地址通过K来对比数据找到目标数据之后就可以根据里面的地址对磁盘进行IO找到相应的数据并对其进行读取那如果数据的个数非常的多并且关键字所占用的空间大小也很大导致关键字也存不下去的话这里就又得进行修改将关键字也存储到磁盘上内存中每个节点就直接存储数据在磁盘上的地址那么在查找数据并比较数据的时候就是先通过地址将关键字从磁盘中提取出来然后进行比较但是这里就存在一个问题我们知道cpu是一个很快的东西而对磁盘进行读写是一个很慢的过程尽管通过平衡二叉树可以在log(n)的时间复杂度找到想要的数据可是因为要对磁盘读取这里的速度也会变的很慢具体有多慢呢我们来看看《算法导论》里面的描述

所以要想快速的在大量数据中找到指定数据就得减少对磁盘的io次数那么这个时候有小伙伴会想到哈希表好像可以减少io次数它的时间复杂度是o(1)那这里能不能使用哈希表呢答案是不行首先哈希表在面对一些特殊数据时可能会发生很严重的哈希冲突其次哈希表在搜索数据的时候也不是一次就能够找到这里的o(1)指的是常数次具体是多少次得看具体的实现所以哈希表也不能胜任这项工作那么为了解决这个问题就有了一个新的数据结构叫做B树这里大家别搞混了啊不是这个B数。

平衡二叉树效率低的原因是因为要多次从磁盘中提取一个节点的数据进行比较提取的次数最多为树的高度次那么B树的思想就是保持搜索二叉树的特性降低树的高度每次从磁盘中读取多个节点的数据进行比较比较的方法跟搜索二叉树一样通过数据的大小关系来做到一次比较排除多个数据一棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质

根节点至少有两个孩子。

每个分支节点都包含k-1个关键字和k个孩子其中

ceil(m/2)

m所有的叶子节点都在同一层。

每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分每个结点的结构为nA0K1A1K2A2…

KnAn其中Ki(1≤i≤n)为关键字且KiKi1(1≤i≤n-1)。

Ai(0≤i≤n)为指向子树根结点的指针。

且Ai所指子树所有结点中的关键字均小于Ki1。

n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。

假设m的值等于3那么通过规则二可以知道每个分支节点里面至少存在一个关键字和两个孩子最多含有2个关键字和3个孩子那么节点就长下面这样

那么这里就有个问题当前节点能不能存储一个关键字和三个孩子呢?答案是不能的因为规则而规定了每个节点都包含k-1个关键字和k个孩子也就是说不管分支节点的内部数据怎么样该节点内孩子的数目一定是要比关键字的数目多一那么这一点也恰好反应了规则一的内容我们知道根节点一定存在一个关键字那么根据规则二便可以知道根节点一定存在两个孩子这里大家要知道的一点虽然我们上面画的关键字最多有两个孩子最多有三个但是在实现的过程中我们为了方便节点的分裂我们会多加一个上去也就是说当M等于3时孩子最多有4个关键字最多有3个

我们上面描述的是分支节点的内部情况而对于叶子节点则是包含k-1个关键字其中

ceil(m/2)

m那么这就对应的是规则三而规则四就是告诉我们所有的叶子节点都处于同一层也就是说B树的每条路径的长度都是一样的规则五和规则六可以放到一起来理解节点里面的child表示一个指针它指向的是一个子树子树里面也存储着很多节点而规则五和六就是告诉我们子树child1中节点的值一定比关键字data1要小data1的值又比child2子树中的所有节点都要小child2子树中的所有值都要比关键字data2data2的值又比child3子树中的所有值要小那么这就是每个节点中数据的规律当我们要查找一个数据的时候就可以利用这个规律比如说dest数据比data1要大那么我们就知道它肯定不会在child1子树里面如果它比data2要小的话那么它一定在child2里面那么这个时候就可以用相同的规律在child2的根节点里面进行查找那么这就是B树的规则和原理接下来我们来B树是如何生成的。

假设M的值等于3那么这个B树里面就应该存储2个关键字和3个指针但是为了方便后面节点的分裂这里就各添加一个元素

139

365047101插入52时b树里面就只有一个节点所以B树里面也就不存在指向子树的指针那么这里的图片就是这样

按照规则来说当前节点存储的关键字已经满了但是为了方便后面的分裂这里还可以存储一个关键字因为75比52大比139小所以75就应该插入到中间位置那么这里的图片如下

当一个节点的空间用完时就得对这个节点进行分裂分裂的方法是创建一个新节点出来然后将已满的节点拷贝一半的数据到新节点里面这里拷贝的顺序是从右往左进行拷贝那么这里存有三个节点所以就是将3/2个节点移动到另外一个节点里面那么这里的图片如下

但是仅这里做的话无法将两个节点连接起来所以这个时候再创建一个节点让这个节点作为B树的根然后将老节点的最右边的数据这里就是75移动到根节点(父节点)里面并且根节点父节点的第一个指针指向老节点第二个指针指向新节点那么这里的图片就变成下面这样

然后插入数据49因为49比75小所以49应该在75左边的子树又因为49比52要小所以49应该在52的前面

然后插入数据145因为145比75要大所以他应该在75右边的子树又因为145比139要大所以他应该在139的右边

然后插入数据36因为36比75要小所以他应该75左边的子树又因为26比49要小所以他应该插入到49的左边

那么这个时候又出现一个吃饱了的节点所以这个时候得对该节点进行分裂创建一个新的节点将已满节点的一半数据52移动进来然后让父节点的中的一个指针指向自己但是这里有个问题我们说每个节点中指针的数目一定比关键字的数目大一如果按照上面的步骤做的话会导致指针的数目比关键字的数目大二就变成了下面这样

所以为了解决这个问题我们还得将老节点中最右边的数据移动到父节点里面所以这里大家可以发现不管是创建根节点还是已经有了父节点在节点分裂的时候都要将原来节点中的一个元素移动到父节点或根节点里面来保证关键字和指针的平衡那么这里的图片如下

然后插入数据50因为50比49大比75小所以50应该插入到49和75之间的子树

然后插入数据101图片就会变成下面这样

那么这里就又出现了一个吃饱了的节点所以得再创建一个节点然后将已满节点的一半移动到新节点里面然后将老节点中最右节点移动到父节点里面那么这里的图片就变成下面这样

通过图片我们可以发现子节点进行分裂之后父节点吃饱了所以在插入节点的过程中很可能会出现连续的分裂情况那么这个时候还得进行分裂因为这里是对根节点进行分裂所以我们得创建两个节点一个节点做根一个节点做原来根节点的兄弟那么这里的图片如下

那么这就是节点插入的过程。

这里有个细节大家要注意一下创建兄弟节点之后要会将一半的关键字拷贝过去但是拷贝的同时要将对应的指针也拷贝到兄弟节点里面并且转移n个关键字就得转移n1个指针那么这就是节点插入的过程接下来我们要模拟实现B树。

准备工作

首先每个节点里面会存有很多的数据那么这里我们就得创建一个类来描述每个节点并且这个类得是一个模板类模板中存在两个参数一个参数用来表示关键字或者指针的类型另外一个参数用来表示当前树的阶树

templateclass

{};节点中需要一个K类型的数组来关键字数组的大小为M然后需要一个TreeNode类型的指针数组用来存储子树的地址数组的大小为M1因为节点满了之后需要对父节点插入数据所以还需要一个指针用来指向当前节点的父节点为了方便判断节点是否需要分裂这里就再创建一个变量用来记录当前节点的个数那么构造函数里面就将指针数组全部初始化为nullptr将K类型的数组全部初始化为K类型的默认构造将计数变量初始化为0指向父节点的指针初始化为空那么这里的代码如下

struct

然后可以创建一个B数类这个类也是一个模板类并且模板的参数和节点的参数一样在这个类里面就只有一个指向节点的指针那么这里代码如下

templateclass

};那么准备工作到这里就结束了接下来我们要实现B树的查找函数。

find函数

find函数需要一个K类型的参数并且返回类不能只为bool因为我们需要通过find函数来找到数据所在的地址并且还能够获取到数据所以返回值的类型为pair类型并且pair的第一个参数表示节点的地址第二个参数用来表示节点中的第几个元素那么这里函数声明就长这样

pairNode*,

K)通过之前的规律我们知道指针数组第i1号元素指向的所有节点一定是比关键字数组中第i号元素大比i1号元素小所以我们就可以使用循环来进行比较如果K的值比关键字数组第i号元素小的话就跳转到指针数组中的第i号元素那么这里我们就可以创建一个指针变量cur来进行跳转因为根节点指针数组的每个元素都为空所以当查找的元素不存在时cur指针一定会走向根节点并且值为空所以判断循环的条件就可以是cur的值

pairNode*,

-1);}因为指针数组的数目比关键字数组多一个所以我们先创建一个变量用来记录找到元素的下标创建while循环如果i的值比当前节点内部元素数目要少的话就执行循环如果K的值比当前下标的元素要大的话就对i如果小的话就直接break结束循环如果相等的话就直接返回当前的下标和节点的地址循环结束之后我们就得到元素的小标然后对cur进行跳转即可那么这里打代码如下

pairNode*,

}我们知道一个函数是可以在另外一个函数中使用的我们知道往容器里面插入一个数据的时候一定得先找数据所在的地方所以按道理来说我们应该可以在insert函数里面使用find函数可是这里存在一个问题当前容器是不支持插入相同数据的而find函数在找不存在的容器时会返回空指针所以这里就出现问题我们上面的实现导致find函数用不上那么这里就可以做出一点改进再创建一个parent指针用来记录查找指针的父节点这样当节点存在就返回cur指针如果节点不存在就返回parent指针这样在insert函数里面使用find函数我们就可以知道元素应该插入到哪个位置上如果是判断节点是否存在的话我们依然可以通过pair的第二个元素进行判断那么这里的代码如下

pairNode*,

insert函数需要一个K类型的参数因为插入的数据存在相同值所以该函数的返回类型为bool类型如果出现相同值就返回false如果插入成功就返回true

bool

key)因为插入的树里面可能一个元素都没有所以在函数的开始得用if语句来进行一下判断如果当前对象的root变量等于空的话就new一个Node然后让root指针指向这个节点将节点的第一个关键字复制为key最后将该节点的_n变量加一

bool

}如果不为空的话就表明当前的树有元素那么这个时候就可以创建一个pair类型的变量来接收find函数的返回值如果变量的第二个参数为-1就表示当前的容器中存在相同值然后就直接返回false如果第二个元素大于等于0就开始执行

bool

}ret变量里面记录了元素应该插入的节点那么这个时候就可以创建一个for循环将插入位置往后的元素都向后挪动一个位置这里大家要注意一下挪动关键字的同时还得挪动关键字对应的孩子指针因为数据的挪动不仅仅出现在一个节点在很多节点都会有所以将这个功能放到一个函数里面在叶子节点里面挪动数据不需要连接孩子但是在分支节点里面插入数据是因为下面的节点出现了分裂创建出来了新的节点从而往上面插入了数据那么这个时候我们不仅得插入数据还得连接新创建的子节点和子节点的父节点那么这个函数就得存在三个参数一个表示插入的关键字一个表示关键字插入的节点最后一个就表示关键字对应的子节点那么这里的函数声明如下

void

//node表达当前存在的节点key表示插入的关键字child表示关键字对应的孩子节点然后在函数里面就先通过for循环找到节点要插入的位置在查找的过程中顺便移动元素那么这里我们就从后往先进行查找首先创建一个创建一个变量n记录当前节点的最后一个元素的位置然后创建while在循环里面将元素进行挪动循环执行的条件就是n的值大于等于0在循环里面添加一个if语句进行判断如果当前位置的元素大于key就对n的值减一如果当前元素的值小于key就直接使用break来结束循环

void

//node表达当前存在的节点key表示插入的关键字child表示关键字对应的孩子节点

{int

1];//注意这里的元素多一个--n;}else{break;}}

}循环结束之后我们就知道当前元素应该插入的位置又因为元素已经挪动好了我们直接插入元素就可以插入完元素之后我们还得关注一下参数中的孩子节点因为叶子节点没有孩子所以他传递过来的参数为空指针所以父子节点连接的时候还得进行判断如果孩子节点不为空就让孩子节点指向父节点最后对节点中的n进行那么这里的代码如下

void

//node表达当前存在的节点key表示插入的关键字child表示关键字对应的孩子节点

{int

1];//注意这里的元素多一个--n;}else{break;}}node-_keys[n

key;node-_subs[n

}实现完插入函数之后我们再回到insert函数因为插入一个节点可能会导致当前节点发生分裂从往父节点里面也插入节点所以在完成插入之前先创建insertkey函数所需要的三个变量以方便函数的插入又因为插入节点是一个循环的过程所以接下来我们还得创建一个循环来完成插入如果插入元素之后当前节点不是满的话就直接break如果满了还得做一些操作

bool

M){//当前节点没有满就直接退出break;}else{//当前的节点已经满了得分裂}

}如果相等的话就表明当前节点已经满了这个时候就得创建一个兄弟节点然后将一半的数据赋值给兄弟节点这里的数据包括关键字和孩子指针并且赋值完了之后还得将原始数据进行覆盖

else

parent-_keys[i];bro***r-_subs[j]

parent-_subs[i];//赋值完之后得对原始数据进行重置parent-_keys[i]

K();parent-_subs[i]

但是这么做存在一个问题关键字和孩子指针都赋值给了兄弟节点但是这些孩子节点的父节点却依然指向原来的节点所以在复制的同时还得修改一下孩子节点的父节点的指向并且因为叶子结点的存在孩子节点可能为空所以在改变指向的时候得进行一下判断判断循环结束之后我们还得修改再进行一次赋值因为孩子数组的元素个树比关键字数组多一个所以还得进行一次修改然后修改两个节点内部的计数变量那么这里的代码如下

else

parent-_keys[i];bro***r-_subs[j]

parent-_subs[i];if

nullptr){parent-_subs[i]-_parent

bro***r;}//赋值完之后得对原始数据进行重置parent-_keys[i]

K();parent-_subs[i]

nullptr;j;}//指针数组多一个bro***r-_subs[j]

parent-_subs[i];if

nullptr){parent-_subs[i]-_parent

nullptr;bro***r-_n

兄弟节点搞定之后就来处理父亲节点首先创建变量midkey记录要插入父亲节点的关键字然后将原始数据清除因为往父节点插入数据存在两个情况一个是父节点不存在也就是根节点发生分裂另外一种就是父节点存在这两种情况处理起来是不一样的所以这里得添加一个if语句进行判断对于父节点不存在的节点这里就再创建一个节点将该节点的关键字数组的第一个元素赋值为midkey然后将指针数组的第一个元素指向原来节点将第二个元素指向兄弟节点并将兄弟节点和原来的根节点的父亲指针指向新创建的节点最后修改节点内部计数变量那么这里的代码如下

else

parent-_keys[i];bro***r-_subs[j]

parent-_subs[i];if

nullptr){parent-_subs[i]-_parent

bro***r;}//赋值完之后得对原始数据进行重置parent-_keys[i]

K();parent-_subs[i]

nullptr;j;}//指针数组多一个bro***r-_subs[j]

parent-_subs[i];if

nullptr){parent-_subs[i]-_parent

nullptr;bro***r-_n

parent-_keys[mid];parent-_keys[mid]

K();if

如果不是根节点这里就要进行转换转换成为在父节点里面插入变量midkey那么这里就只用改变parent和child和newKey的值就行那么这里的代码如下

bool

M){//当前节点没有满就直接退出break;}else{//当前的节点已经满了得分裂size_t

mid

parent-_keys[i];bro***r-_subs[j]

parent-_subs[i];if

nullptr){parent-_subs[i]-_parent

bro***r;}//赋值完之后得对原始数据进行重置parent-_keys[i]

K();parent-_subs[i]

nullptr;j;}//指针数组多一个bro***r-_subs[j]

parent-_subs[i];if

nullptr){parent-_subs[i]-_parent

nullptr;bro***r-_n

parent-_keys[mid];parent-_keys[mid]

K();if

_root;break;}else{//通过循环转换成为往父节点里面进行插入child

bro***r;parent

二叉树有中序遍历那么同样的道理B树也有中序遍历中序遍历的顺序是左子树根节点右子树首先用户拿不到根节点的值所所以这里采用嵌套调用的方式来实现遍历

void

}然后在_InOrder函数里面就先判断一下cur是否为空如果为空的话就直接返回然后就创建一个for循环不停的遍历每个节点的孩子循环的第一步就是跳转到对应的孩子然后就打印对应位置的关键字的值等关键字数组遍历完成之后再跳转到最右边的子树那么这里代码如下

void

BTree;BTree.insert(52);BTree.insert(139);BTree.insert(75);BTree.insert(49);BTree.insert(145);BTree.insert(36);BTree.insert(50);BTree.insert(47);BTree.insert(101);BTree.InOrder();return

在项目中一般将M的值设置为1024那么假设每个节点都是满的那么根节点中会存储1023个数据和1024个子树然后在第二层就存在1024个节点每个节点又有1023个关键字和1024个孩子所以第二层存储的节点个数就是1024*1023第二层的孩子指针就是1024*1024那么第三层存储的节点个数就是1024*1024*1023孩子指针的个数就是1024*1024*1024所以第四层存储的关键字个数就是1024*1024*1024*1023将每一层存储的节点个数加起来就是一个非常大的数字10231024*10231024*1024*10231024*1024*1024*1023存储这么对数据但是在查找数据的时候最坏也只用对磁盘进行4次Io上面是最好的情况那么最坏情况就是每个节点都只存储一半的数据这里粗略进行计算第一层节点就只有一个数据和两个孩子第二个层就有两个节点每个节点里面存储512个关键字和孩子所以第三层就有1024个节点每个节点里面存储512个关键字和512个孩子第四层就有1024*512个节点每个节点存储512个关键字所以第四层就存储1024*512*512个关键字所以当一个B树最坏情况装的就是12*5122*512*5122*512*512*512节点可以看到及时最坏情况下b树也能够存储大量的数据那么这就是B-树的性能。

如果我们要删除36那么这里就是直接删除并将40移动到36的位置

-1的话则优先找父亲借然后父亲再兄弟节点节所以这里先把49放到40的位置上

然后再从兄弟那里找一个最小的元素放到父亲节点里面所以图片就变成下面这样

如果再删除49的话同样也是找付父亲借父亲找兄弟借可是这里就存在一个问题兄弟借不到了那么这时父亲就得找他的父亲借所以先把53放到49的位置然后把75放到53的位置但是因为55比75要小那么这个时候就将55和75换一个位置所以图片就变成下面这样

然后父亲的父亲就找父亲的兄弟借也就是将139放到原来75的位置可是这时候父亲的兄弟就变的不符合规则了那么这个时候他就会找他的孩子借第一个孩子借不了就找第二个孩子借所以145来到139的位置148来到145的位置那么这里的图片如下

然后再删除150这个时候就得将150放到145的位置上然后将160提到上面来

然后再删除节点180因为当前节点的元素个数小于m/2-1并且他向父亲和兄弟也借不到元素所以这个时候就得进行合并将180所在的节点删除然后将160放到148所在的节点

再删除节点160没有任何问题

再删除节点145因为当前节点数量不够了并且无法向其他节点借时就得进行合并这里就是将139和55进行合并将101和148进行合并

那么这就是大致的删除规则反正就是很复杂很难这里我们就不实现了大家了解即可。

B树是B树的变形是在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又在B树的基础上做了以下几点改进优化

分支节点的子树指针与关键字个数相同。

分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1])区间之间这就说明B树取消了最左边的那个子树所有叶子节点增加一个链接指针链接在一起所有关键字及其映射数据都在叶子节点出现。

所有的叶子节点增加一个链接指针链接在一起那么这时想要遍历树中的每个元素时就可以直接通过叶子节点中的指针进行遍历不需要像B-树一样从头开始遍历通过上面的图片大家也可以看到分支节点和叶子节点中存在重复的值那么分支节点里面存的值是叶子节点最小值的索引也就是说通过分支节点里面的值我们就可以知道他的子节点中的最小值是多少那么通过这个索引我们在查找元素的时候就很简单假如说查找元素4因为根节点的第一个元素的值为5而4比5还小这就说明当前树中没有5如果我们要查找元素60那么根节点中存在三个值5

65因为60比28要大但是比65要小所以60只可能出现在28的子树里面28指向的分支节点总又存储了三个值分别为28

56因为60比56要大并且后面没有元素了所以就存储在56对应的叶子节点然后遍历叶子结点的内容即可那么这就是B树的内部构造接下来我们来看B树的插入。

B树的每个节点都含有两块内容一个用来存储索引一个用来存储值假设M的值为3插入的第一个元素为53图片就是下面这样

上面的方块用来存储子节点的索引下面的方块用来存储值然后再插入数据139和75图片就变成了下面这样

再插入数据49因为49比53要小所以插入数据的同时还得修改索引的值

并且当前的节点已经填满了所以这个时候就得进行分裂创建一个新的节点并将原来节点的一半分裂出去然后往索引里面添加值那么这里的图片就变成下面这样

然后插入元素145

但是这个时候就没有了根节点所以还得创建一个根节点用来指向两个分支节点

B树是B树的变形在B树的非根和非叶子节点再增加指向兄弟节点的指针

B树跟B树的结构差不多就是在每个分支节点中也添加了一个指针用来指向同层的分支节点然后B*树在分裂的时候与B树有所不同当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。

所以B*树分配新结点的概率比B树要低空间使用率更高。

通过以上介绍大致将B树B树B*树总结如下

B树有序数组平衡多叉树B树有序数组链表平衡多叉树B*树一棵更丰满的空间利用率更高的B树。