B树及其基本操作
标签: 数据结构
学习人数: 5754


全屏播放
赞赏支持

B树的基本概念及性质

1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。

一棵m阶B树或为空树,或为满足下列特性的m叉树:

1.若根结点不是终端节点,则至少有两棵子树,最多有m棵子树。
2.除根结点外的所有非叶结点至少有⌈m/2⌉棵子树,最多有m棵子树。
3.所有的非叶结点都出现在同一层次上,并且不带信息(可视为失败结点)。
4.所有非叶结点的结构如下:

在这里插入图片描述

a)、Pi-1所指子树中所有结点的关键字均小于Ki
b)、Pi所指子树中所有结点的关键字均大于Ki

 

B树的基本操作

B树的查找

B树的查找算法如下:

①、在B树中找结点(磁盘上进行),当查找到叶结点时,查找失败。
②、在结点内的多关键字有序表中查找关键字(内存中进行):

a)、先在有序表中进行查找,若找到则查找成功。
b)、否则,根据找到的指针信息到所指的子树,执行①。

对于含有n个关键字的B树的查找,磁...

登录查看完整内容


课后作业

课后习题

 

【2018年真题】高度为5的3阶B树含有的关键字个数至少是()
A.15    B. 31    C. 62    D. 242

参考答案:B

 

【2014年真题】在一棵具有 15 个关键字的 4 阶 B 树中,含关键字的结点个数最多是()
A.5 
B.6 
C.10 
D.15

参考答案:D
答案解析:关键字数量不变,要求结点数量最多,那么即每个结点中含关键字的数量最少。根 据 4 阶 B 树的定义,根结点最少含 1 个关键字,非根结点中最少含é4/2ù-1=1 个关键字,所 以每个结点中,关键字数量最少都为 1 个,即每个结点都有 2 个分支,类似与排序二叉树, 而 15 个结点正好可以构造一个 4 层的 4 阶 B 树,使得叶子结点全在第四层,符合 B 树定义,因此选 D。 

 

【2013年真题】在一株高度为 2 的 5 阶 B 树中,所含关键字的个数最少是()
A.5             B. 7         C. 8         D. 14

参考答案:A
答案解析:一棵高度为 2 的 5 阶 B 树,根结点只有到达 5 个关键字的时候才能产生分裂,成为高度为 2 的 B 树。 

 

【2012年真题】已知一棵 3 阶 B-树,如下图所示。删除关键字 78 得到一棵新 B-树,其最右叶结点中的关键字是()。 
A.60 
B.60, 62 
C.62, 65 
D.65 

参考答案:D
答案解析:考查 B-树的删除操作。 
对于上图所示的 3 阶 B-树,被删关键字 78 所在结点在删除前的关键字个数=1=é3/2ù-1,且其左兄弟结点的关键字个数=2≥é3/2ù,属于“兄弟够借”的情况,则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中,同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中,这样就达到了新的平衡,如下图所示。 

 

【2009年真题】下列叙述中,不符合 m 阶 B 树定义要求的是()。 
A.根节点最多有 m 棵子树 
B.所有叶结点都在同一层上 
C.各结点内关键字均升序或降序排列 
D.叶结点之间通过指针链接

参考答案:D
答案解析:考查 m 阶 B-树的定义。 
A、B 和 C 都是 B-树的特点,而选项 D 则是 B+树的特点。注意区别 B-树和 B+树各自的特点。 


登录后发布评论

暂无评论,来抢沙发