重学数据结构(六、树和二叉树) (16)

在这里插入图片描述


在这里插入图片描述

接着,把22删除,这种情况的规则:22是非叶子节点,对于非叶子节点的删除,我们需要用后继key(元素)覆盖要删除的key,然后在后继key所在的子支中删除该后继key。对于删除22,需要将后继元素24移到被删除的22所在的节点。

在这里插入图片描述

在这里插入图片描述


此时发现26所在的节点只有一个元素,小于2个(m/2),这个节点不符合要求,这时候的规则(向兄弟节点借元素):如果删除叶子节点,如果删除元素后元素个数少于(m/2),并且它的兄弟节点的元素大于(m/2),也就是说兄弟节点的元素比最少值m/2还多,将先将父节点的元素移到该节点,然后将兄弟节点的元素再移动到父节点。这样就满足要求。

看看操作过程:

在这里插入图片描述


在这里插入图片描述

接着删除28,删除叶子节点,删除后不满足要求,所以,我们需要考虑向兄弟节点借元素,但是,兄弟节点也没有多的节点(2个),借不了,怎么办呢?如果遇到这种情况,首先,还是将先将父节点的元素移到该节点,然后,将当前节点及它的兄弟节点中的key合并,形成一个新的节点。

在这里插入图片描述


移动之后,跟兄弟节点合并。

在这里插入图片描述


8、B+树

B+树是B树的变体,也是一种多路搜索树。

B+树·和B树有一些共同的特性:

根节点至少一个元素

非根节点元素范围:m/2 <= k <= m-1

B+树和B树也有一些不一样的地方:

B+树有两种类型的节点:非叶子结点(也称索引结点)和叶子结点。非叶子节点不存储数据,只存储索引,数据都存储在叶子节点。

非叶子结点中的key都按照从小到大的顺序排列,对于非叶子结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。

父节点存有右孩子的第一个元素的索引。

看一个B+树的示例:

在这里插入图片描述


8.1、查找

B+树的查找右两种方式:

(1)从最小关键字起顺序查找;

(2)从根节点开始,进行随机查找

在查找时,若非叶子节点上的关键字等于给定值,并不终止,而是继续向下直到叶子节点。因此,在B+树中,不管查找成功与否,每次查找都是走了一条从根到叶子节点的路径。其余同B树的查找类似。


8.2、插入

插入操作有一个规则:当节点元素数量大于m-1的时候,按中间元素分裂成左右两部分,中间元素分裂到父节点当做索引存储,但是,本身中间元素还是分裂右边这一部分的。

以一颗5阶B+树的插入过程为例,5阶B+树的节点最少2个元素,最多4个元素。

插入5,10,15,20

在这里插入图片描述

插入25,此时元素数量大于4个了,分裂

在这里插入图片描述

接着插入26,30,继续分裂

在这里插入图片描述

在这里插入图片描述


8.3、删除

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpxzyd.html