我要招人

去企业版

首页 > 试题广场 >

删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键

[单选题]

设有一棵3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是（）。

```
60
```
```
60， 62
```
```
62， 65
```
```
65
```

查看正确选项

爱吃青菜皮卷面的byr

在B-树叶结点上删除一个关键字的方法是：

首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：

（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)（即向上取整），说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。

（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。

调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。

对于本题，n=ceil（3/2）-1 。所以将做节点最大关键字62上移，同时将双亲结点中大于62的关键字（65）下移至删除结点位置。

发表于 2017-02-17 01:46:35 回复(0)

zhaobinw

根据B树删除节点规则，删除后右方的子树为

55：62

47 60 65

发表于 2016-11-26 20:04:02 回复(0)

不做人了

不能少于1个节点，所以要平衡，65下移，62上移，保障有序

发表于 2020-12-05 11:32:31 回复(0)

第999个小菜鸡

需要判断被删除的原关键字个数，若n>=ceil(m/2)，不影响B树的结构，不做改变，如果n=ceil(m/2)-1，那么需要移动双亲结点和左右兄弟节点的关键字，以达到B树的平衡。

发表于 2022-09-15 11:13:35 回复(0)

Cara_Smith

b树是一个一般化的二叉树，我觉得可以理解为广义上的"完全二叉树"吧，就是达到左右平衡的一类树。

发表于 2024-04-16 01:37:45 回复(0)

nanana6

卧槽 20年408真题考场上做了现在又刷到了

发表于 2020-03-10 20:23:49 回复(0)

xxxxxxxxxxxxxxxa

师从DSAA的可能就郁闷了，这和书上的B树不一样啊：

Thereare vari ous definitions of B-trees that change this structure in mostly minor ways, but this definition is one of the popular forms.We will also insist (for now) that the number of keys in a leaf is also between m/2 and m.

然后就需要再看看别的B树定义了。

发表于 2018-05-07 20:31:27 回复(0)

梦境迷离

向上分裂...

发表于 2018-02-17 14:22:11 回复(0)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

8条回答 496收藏 4014浏览

删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键

问题信息

热门推荐

相关试题