数据结构 B树

B树和B+树

简介

B树和B+树都是多路查找树，为了解决数据量⼤，树的⾼度⼤增(⼆叉树)⽽产⽣的⼀种数据结构，23树和234树都是⼀种特殊的B树，为了更

好理解B树，故先介绍23树和234树。

23树

定义

2-3树是⼀种多路查找树，2和3的意思是该树包含2结点和3结点两种情况；

2结点包含⼀个元素和两个⼦树左⼦树包含结点的元素值⼩于该结点的元素值，右⼦树包含结点的元素值⼤于该结点的元素值2结点要不有两个⼦树，要不就没有⼦树，不允许只有⼀个⼦树。

3结点包含⼀⼤⼀⼩两个元素和三个⼦树，元素按照左⼩右⼤顺序排列；

左⼦树包含结点的元素值⼩于该结点较⼩的元素值，右⼦树包含结点的元素值⼤于该结点较⼤的元素值，中间⼦树包含的结点的元素值介于这两个元素值之间。3结点要不有三个⼦树，要不就没有⼦树，不允许有⼀个或者两个⼦树。

2-3树所有叶⼦结点都在同⼀层次图例

234树

定义

2-3-4树是⼀种多路查找树，2和3和4的意思是该树包含2结点、3结点和4结点三种情况；

2-3树是⼀种多路查找树，2和3的意思是该树包含2结点和3结点两种情况；

2结点包含⼀个元素和两个⼦树左⼦树包含结点的元素值⼩于该结点的元素值，右⼦树包含结点的元素值⼤于该结点的元素值2结点要不有两个⼦树，要不就没有⼦树，不允许只有⼀个⼦树。

3结点包含⼀⼤⼀⼩两个元素和三个⼦树，元素按照左⼩右⼤顺序排列；

左⼦树包含结点的元素值⼩于该结点较⼩的元素值，右⼦树包含结点的元素值⼤于该结点较⼤的元素值，中间⼦树包含的结点的元素值介于这两个元素值之间。3结点要不有三个⼦树，要不就没有⼦树，不允许有⼀个或者两个⼦树。

4结点包含⼩中⼤三个元素和四个⼦树。

最左⼦树包含的结点的元素值⼩于该结点最⼩的元素值，第⼆个⼦树包含的结点的元素值⼤于最⼩的元素值⼩于中间元素值，第三个⼦树包含的的结点的元素值⼤于中间元素值⼩于最⼤元素值，最右⼦树包含的结点的元素值⼤于该结点最⼤的元素值。4结点要不有四个⼦树，要不就没有⼦树，不允许有⼀个、两个⼦树或三个⼦树。

数据结构复习题：树和二叉树

单选题

1、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为_____。

A,15 B,16 C,17 D,47

2、假定一棵二叉树的结点数为18个，则它的最小高度_____。

A,4B,5 C,6 D,18

3、在一棵二叉树中第五层上的结点数最多为_____。

A,8 B,15 C,16 D,32

4、在一棵具有五层的满二叉树中，结点总数为_____。

A,31 B,32 C,33 D,16

5、已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为_____。

A,1 B,2 C,3 D,4

6、由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_____。

A,23 B,37C,44 D,46

7、在树中除根结点外，其余结点分成m(m≥0)个_____的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。

A,互不相交 B 可以相交 C叶结点可以相交 D树枝结点可以相交

8、下面答案_____是查找二叉树（又称二叉排序树）。

A二叉树中的每个结点的两棵子树的高度差的绝对值不大于１。

B二叉树中的每个结点的两棵子树的高度差等于１。

C二叉树中的每个结点的两棵子树是有序的。

D 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，且小于其右子树（如果存在）所有结点的关键字值。

9、如果结点A有三个兄弟，而且B是A的双亲，则B的出度是_____。

A,3 B,4 C,5 D,1

10、一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从１开始对全部结点编号，编号为n的有右兄弟的条件是_____。

ＩＳＳＮ　１００９—３０４４　Ｃｏｍｐｕｔｅｒ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技术　Ｅ—ｍａｉｈ　ｘｓｊｌ＠ｄｎｚｓ．ｎｅｔ．ｅｎ　ｈｔｔｐ：／／ｗｗｗ．ｄｎｚｓ．ｎｅｔ．ｅｎ　６５６９０９６４　

《数据结构》中Ｂ一树的删除算法的实现　

江克勤，吴海峰，程玉胜　

（安庆师范学院计算机与信息学院，安徽安庆２４６０１１）　

摘要：Ｂ一树是一种平衡的多路查找树，在文件系统中有着很好的应用。该文分析了在Ｂ一树中删除一个关键词的几种情　

形，给出了Ｂ一树删除算法的具体实现，有助于对《数据结构》课程中Ｂ一树操作的更好理解。　

关键词：查找树；子树；叶子结点；删除算法；合并结点　

中图分类号：ＴＰ３１１　文献标识码：Ａ　文章编号：１００９—３０４４（２０１４）ｌ６—３７７８－０４　

Ｔｈｅ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｔｈｅ　Ｄｅｌｅｔｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ａｂｏｕｔ　Ｂ－。ｔｒｅｅｓ　ｉｎ　ａ　Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅ　Ｃｏｕｒｓｅ　

ＪＩＡＮＧ　Ｋｅ—ｑｉｎ．ｗｕ　Ｈａｉ—ｆｅｎｇ．ＣＨＥＮＧ　Ｙｕ—ｓｈｅｎｇ　

（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，Ａｎｑｉｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ａｎｑｉｎｇ　２４６０１１，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｂ—ｔｒｅｅｓ　ａｒｅ　ｂａｌａｎｃｅｄ　ｓｅａｒｃｈ　ｔｒｅｅｓ　ｄｅｓｉｇｎｅｄ　ｔＯ　ｗｏｒｋ　ｗｅｌｌ　ｏｎ　ｆｉｌｅ　ｓｙｓｔｅｍｓ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈｅ　ｄｅｔａｉｌｅｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ａ　ｄｅｌｅｔｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｄｉｓｃｕｓｓｅｄ　ｆｏｒ　ａ　ｆｅｗ　ｓｉｔｕａｔｉｏｎｓ　ｏｆ　ｄｅｌｅｔｉｎｇ　ｔｈｅ　ｋｅｙ　ｉｎ　Ｂ—ｔｒｅｅｓ，ｗｈｉｃｈ　ｃｏｎｔｒｉｂｕｔｅｓ　ｔｏ　ａ　ｂｅｔｔｅｒ　ｕｎｄｅｒｓｔａｎｄｉｎｇ　ｏｆ　

平衡⼆叉树，B树，B+树的概念及区别

1.平衡⼆叉树

由来：平衡⼆叉树是基于⼆分法的策略提⾼数据的查找速度的⼆叉树的数据结构

特点：1.⼆叉树：意思是每个节点最多只能有两个⼦节点

2.平衡：因为平衡⼆叉树的查询性能与树的⾼度成正⽐，所以为了降低树的⾼度，会去尽量的设计从⽽保证两端数据的⼤致平衡，这种设计

⼀般是会采⽤⼀种算法机制，常见的有AVL，treap，红⿊树等等。这样设计下的数的查询速度接近于⼆分查找法。

最常见的算法规则是左边的⼦节点⼩于⽗节点，⽗节点⼩于右⼦节点

总结平衡⼆叉树特点：

（1）⾮叶⼦节点最多拥有两个⼦节点；

（2）⾮叶⼦节值⼤于左边⼦节点、⼩于右边⼦节点；

（3）树的左右两边的层级数相差不会⼤于1;

（4）没有值相等重复的节点; ⼆叉树的优点：

⼆叉排序树是⼀种⽐较有⽤的折衷⽅案。

数组的搜索⽐较⽅便，可以直接⽤下标，但删除或者插⼊某些元素就⽐较⿇烦。

链表与之相反，删除和插⼊元素很快，但查找很慢。

⼆叉排序树就既有链表的好处，也有数组的好处。

在处理⼤批量的动态的数据是⽐较有⽤。

⽂件系统和数据库系统⼀般都采⽤树（特别是B树）的数据结构数据，主要为排序和检索的效率。⼆叉树是⼀种最基本最典型的排序树，⽤

于教学和研究树的特性，本⾝很少在实际中进⾏应⽤，因为缺点太明显了（看看教科书怎么说的）。就像冒泡排序⼀样，虽然因为效率问题

并不实⽤，单不失⼀种教学例⼦的好⼿段。

平衡⼆叉树都有哪些应⽤场景

⼆叉树⽀持动态的插⼊和查找，保证操作在O(height)时间，这就是完成了哈希表不便完成的⼯作，动态性。但是⼆叉树有可能出现worst-case，如果输⼊序列已经排序，则时间复杂度为O(N)

平衡⼆叉树/红⿊树就是为了将查找的时间复杂度保证在O(logN)范围内。

所以如果输⼊结合确定，所需要的就是查询，则可以考虑使⽤哈希表，如果输⼊集合不确定，则考虑使⽤平衡⼆叉树/红⿊树，保证达到最⼤

效率

平衡⼆叉树主要优点集中在快速查找。SGI/STL的set/map底层都是⽤红⿊树（平衡⼆叉树的⼀种）实现