《数据结构》中B—树的删除算法的实现

江克勤　吴海峰　程玉胜

摘要：B-树是一种平衡的多路查找树，在文件系统中有着很好的应用。该文分析了在B-树中删除一个关键词的几种情形，给出了B-树删除算法的具体实现，有助于对《数据结构》课程中B-树操作的更好理解。

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

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）16-3778-04

Abstract：B-trees are balanced search trees designed to work well on file systems. In this paper， the detailed implementation of a deleting algorithm is discussed for a few situations of deleting the key in B-trees， which contributes to a better understanding of B-trees in a data structure course.

Key words：Search tree； Subtree； Leaf node； Deleting algorithm； Merge node

1 概述

B-树是《数据结构》课程中动态查找表的重要内容[1]，其中在B-树上删除一个关键词是教学过程中的一个难点。大多数的《数据结构》教材中只给出了删除关键词的情况分析，并辅以简单的示例，都没有给出对应的B-树删除算法。对于一些稍复杂的关键词删除问题，我们往往不能得到准确删除后的B-树。该文在给出B-树的定义后，对在B-树中删除一个关键词的几种情形进行分析，并给出B-树删除算法的具体程序实现，有助于大家更好地理解《数据结构》课程中B-树的删除过程。

2 B-树的定义及其查找过程

2.1 B-树的定义

B-树是由R. Bayer和E.M. McCreight于1972年提出的一种平衡的多路查找树[2]，它比较适合在磁盘等直接存取设备上组织动态的查找表，它是一种组织和维护外存文件系统非常有效的数据结构。

B-树中所有结点的最大子树个数称为该B-树的阶，通常用m表示，从查找效率考虑，一般要求m≥3。一棵m阶B-树或者是一棵空树，或者是满足下列特性的m叉树[3]：

1）树中每个结点至多有m棵子树（即至多有m-1个关键词）；

2）若根结点不是叶子结点，则其至少有两棵子树；

3）除根结点之外的其它结点至少有[m2]棵子树（至少有[m2-1]个关键词）；……