《数据结构》中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]个关键词）；

4）每个结点的结构为：（n， A0， K1， A1， K2， A2， … ， Kn， An）其中，n为该结点中关键词的个数，除根结点外，其它所有结点的n满足[m2-1≤n≤m-1]；Ki（1≤i≤n）为该结点的关键词且满足Ki

5）所有的叶子结点都出现在同一层上，即B-树是所有结点的平衡因子均等于0的多路查找树。

下面图1所示为一棵3阶的B-树。

2.2 B-树的存储及查找

假设B-树的结点类型定义如下：

#define m 3 // B-树的阶，暂设为3

typedef int KeyType； // KeyType为关键词的类型

typedef struct BTNode {

int keynum； // 结点中关键词个数，即结点的大小

struct BTNode *parent； // 指向双亲结点

KeyType key[m+1]； // key[1..keynum]存放关键词，key[0]未用

struct BTNode *ptr[m+1]； // 子树指针数组ptr[0..keynum]

}BTNode，*BTree； // B-树结点和B-树的类型

typedef struct {

BTNode *pt； // 指向找到的结点

int i； // 1..m，在结点中的关键词序号

int tag； // 查找成功时为1，否则为0

}Result； // B-树的查找结果类型

由B-树的定义可知，在B-树上进行查找的过程和二叉排序树的查找类似，它是一个顺着指针查找结点和在结点的关键词中进行查找不断交叉进行的过程。若在一棵B-树上查找指定的关键词x，则先将x与根1）结点中的key[i]进行比较：

2）若x=key[i]，查找成功；

3）若x

4）若key[i]

5）若k>key[n]，则沿着指针ptr[n]所指的子树继续查找。

对应的查找算法可参见文献[3]，文献[1，4]中有关于查找的一些例子。

3 B-树的删除算法及其实现

本节结合示例和算法详细讨论在B-树上删除关键词x的过程。

首先在B-树上查找待删关键词x所在的结点，如果查找失败，那么表明x不在该B-树中，无关键词可删除；如果查找成功，关键词x在B-树的结点p中，但p不是叶子结点，那么可用某叶子结点中的一个关键词替代结点p中的x，假设x为p中的第i个关键词（即x=p→key[i]），则替换x可以选用子树p→ptr[i]中关键词最小的，或选用子树p→ptr[i-1]中关键词最大的，这两个关键词都位于B-树的叶子结点中，这样删除非叶子结点中的关键词可以转化为删除叶子结点中的替代关键词。该文采用子树p→ptr[i]中最小关键词作为替代关键词，例如，要删除图1中的关键词30，它位于根结点，选用其右子树中最左下的叶子结点f中的关键词45替换30，再删除叶子结点f中的替代关键词。

通过修改文献[3]中的查找算法SearchBTree，在查找成功时返回替代关键词的位置信息。

if （found） // 查找成功，返回删除x的位置信息

{ r.i = i； r.pt = p； r.tag = 1；

if （p→ptr[i-1]） // 若p为非叶子结点，则由其后继叶子结点q作为替代结点

{ for （q = p→ptr[i]； q→ptr[0]； q = q→ptr[0]）；

p→key[i] = q→key[1]； r.pt = q； r.i = 1； }

}

下面只需讨论删除叶子结点p中的关键词的情形，分四种情况[5]：

1）p是根结点，如果删除之后，根结点还剩至少一个关键词，那么把根结点写盘，删除任务完成；如果删除之后，根结点中无关键词，那么该B-树成为空树。

2）删除之后p至少有[m2-1]个关键词，则把结点p写盘，删除任务完成。

3）删除之后p有[m2-2]个关键词，且离p最近的兄弟结点至少有[m2]个关键词。先检查p的左兄弟，若其关键词数目至少为[m2]，则我们调用函数MoveRight（ ），将左兄弟中的最大关键词上移至双亲结点，并将双亲结点中大于且紧靠该上移关键词的关键词下移至被删关键词所在结点；若p无左兄弟，则检查其右兄弟，调用函数MoveLeft（ ），将右兄弟中的最小关键词上移至双亲结点，并将双亲结点中小于且紧靠该上移关键词的关键词下移至被删关键词所在结点。例如，从图1中删除关键词30，结果如图2所示。

4）删除之后p有[m2-2]个关键词，且离p最近的兄弟结点恰有[m2-1]个关键词。若p有左兄弟，且其左兄弟结点地址由双亲结点中指针q→ptr[i-1]所指，则调用函数Merge（ ）把p中剩余的关键词和指针，加上双亲结点中的关键词q→key[i]一起，合并到q→ptr[i-1]所指的左兄弟结点中（若没有左兄弟，则合并至右兄弟结点中）。例如，从图2中删除50，结果如图3所示。如果该合并操作使得双亲结点中的关键词数目小于[m2-1]，则依次类推作相应处理。例如，从图3中删除关键词25，结果如图4所示。

4 结论

在B-树上删除一个关键词是《数据结构》课程教学中的一个难点，该文分析了删除的几种情形，给出了B-树删除算法的具体程序实现，可以帮助大家更准确地解决B-树中一些复杂的关键词删除问题。本程序在VC++6.0中调试通过，其中创建一棵m阶B-树是通过修改的查找算法SearchBTree和文献[1]中的插入算法InsertBTree实现的，用括号表示法显示B-树的输出，图5是该完整程序的运行结果。

参考文献：

[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京： 清华大学出版社， 2007.

[2] Bayer R， Mccreight E M. Organization and maintenance of large ordered indexes[J]. Acta Informatica， 1972，1（3）：173-189.

[3] 李春葆，尹为民，李蓉蓉，等. 数据结构教程[M].3版.北京： 清华大学出版社， 2009.

[4] Cormen T H， Leiserson C E， RIVEST R L， et al. Introduction to Algorithms[M]. 3rd ed. Massachusetts： The MIT Press， 2009： 484-504.

[5] Horowitz E，等. 朱仲涛译. 数据结构基础（C语言版）[M]. 2nd ed. 北京： 清华大学出版社， 2009.endprint

通过修改文献[3]中的查找算法SearchBTree，在查找成功时返回替代关键词的位置信息。

if （found） // 查找成功，返回删除x的位置信息

{ r.i = i； r.pt = p； r.tag = 1；

if （p→ptr[i-1]） // 若p为非叶子结点，则由其后继叶子结点q作为替代结点

{ for （q = p→ptr[i]； q→ptr[0]； q = q→ptr[0]）；

p→key[i] = q→key[1]； r.pt = q； r.i = 1； }

}

下面只需讨论删除叶子结点p中的关键词的情形，分四种情况[5]：

1）p是根结点，如果删除之后，根结点还剩至少一个关键词，那么把根结点写盘，删除任务完成；如果删除之后，根结点中无关键词，那么该B-树成为空树。

2）删除之后p至少有[m2-1]个关键词，则把结点p写盘，删除任务完成。

3）删除之后p有[m2-2]个关键词，且离p最近的兄弟结点至少有[m2]个关键词。先检查p的左兄弟，若其关键词数目至少为[m2]，则我们调用函数MoveRight（ ），将左兄弟中的最大关键词上移至双亲结点，并将双亲结点中大于且紧靠该上移关键词的关键词下移至被删关键词所在结点；若p无左兄弟，则检查其右兄弟，调用函数MoveLeft（ ），将右兄弟中的最小关键词上移至双亲结点，并将双亲结点中小于且紧靠该上移关键词的关键词下移至被删关键词所在结点。例如，从图1中删除关键词30，结果如图2所示。

4）删除之后p有[m2-2]个关键词，且离p最近的兄弟结点恰有[m2-1]个关键词。若p有左兄弟，且其左兄弟结点地址由双亲结点中指针q→ptr[i-1]所指，则调用函数Merge（ ）把p中剩余的关键词和指针，加上双亲结点中的关键词q→key[i]一起，合并到q→ptr[i-1]所指的左兄弟结点中（若没有左兄弟，则合并至右兄弟结点中）。例如，从图2中删除50，结果如图3所示。如果该合并操作使得双亲结点中的关键词数目小于[m2-1]，则依次类推作相应处理。例如，从图3中删除关键词25，结果如图4所示。

4 结论

在B-树上删除一个关键词是《数据结构》课程教学中的一个难点，该文分析了删除的几种情形，给出了B-树删除算法的具体程序实现，可以帮助大家更准确地解决B-树中一些复杂的关键词删除问题。本程序在VC++6.0中调试通过，其中创建一棵m阶B-树是通过修改的查找算法SearchBTree和文献[1]中的插入算法InsertBTree实现的，用括号表示法显示B-树的输出，图5是该完整程序的运行结果。

参考文献：

[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京： 清华大学出版社， 2007.

[2] Bayer R， Mccreight E M. Organization and maintenance of large ordered indexes[J]. Acta Informatica， 1972，1（3）：173-189.

[3] 李春葆，尹为民，李蓉蓉，等. 数据结构教程[M].3版.北京： 清华大学出版社， 2009.

[4] Cormen T H， Leiserson C E， RIVEST R L， et al. Introduction to Algorithms[M]. 3rd ed. Massachusetts： The MIT Press， 2009： 484-504.

[5] Horowitz E，等. 朱仲涛译. 数据结构基础（C语言版）[M]. 2nd ed. 北京： 清华大学出版社， 2009.endprint

通过修改文献[3]中的查找算法SearchBTree，在查找成功时返回替代关键词的位置信息。

if （found） // 查找成功，返回删除x的位置信息

{ r.i = i； r.pt = p； r.tag = 1；

if （p→ptr[i-1]） // 若p为非叶子结点，则由其后继叶子结点q作为替代结点

{ for （q = p→ptr[i]； q→ptr[0]； q = q→ptr[0]）；

p→key[i] = q→key[1]； r.pt = q； r.i = 1； }

}

下面只需讨论删除叶子结点p中的关键词的情形，分四种情况[5]：

1）p是根结点，如果删除之后，根结点还剩至少一个关键词，那么把根结点写盘，删除任务完成；如果删除之后，根结点中无关键词，那么该B-树成为空树。

2）删除之后p至少有[m2-1]个关键词，则把结点p写盘，删除任务完成。

3）删除之后p有[m2-2]个关键词，且离p最近的兄弟结点至少有[m2]个关键词。先检查p的左兄弟，若其关键词数目至少为[m2]，则我们调用函数MoveRight（ ），将左兄弟中的最大关键词上移至双亲结点，并将双亲结点中大于且紧靠该上移关键词的关键词下移至被删关键词所在结点；若p无左兄弟，则检查其右兄弟，调用函数MoveLeft（ ），将右兄弟中的最小关键词上移至双亲结点，并将双亲结点中小于且紧靠该上移关键词的关键词下移至被删关键词所在结点。例如，从图1中删除关键词30，结果如图2所示。

4）删除之后p有[m2-2]个关键词，且离p最近的兄弟结点恰有[m2-1]个关键词。若p有左兄弟，且其左兄弟结点地址由双亲结点中指针q→ptr[i-1]所指，则调用函数Merge（ ）把p中剩余的关键词和指针，加上双亲结点中的关键词q→key[i]一起，合并到q→ptr[i-1]所指的左兄弟结点中（若没有左兄弟，则合并至右兄弟结点中）。例如，从图2中删除50，结果如图3所示。如果该合并操作使得双亲结点中的关键词数目小于[m2-1]，则依次类推作相应处理。例如，从图3中删除关键词25，结果如图4所示。

4 结论

在B-树上删除一个关键词是《数据结构》课程教学中的一个难点，该文分析了删除的几种情形，给出了B-树删除算法的具体程序实现，可以帮助大家更准确地解决B-树中一些复杂的关键词删除问题。本程序在VC++6.0中调试通过，其中创建一棵m阶B-树是通过修改的查找算法SearchBTree和文献[1]中的插入算法InsertBTree实现的，用括号表示法显示B-树的输出，图5是该完整程序的运行结果。

参考文献：

[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京： 清华大学出版社， 2007.

[2] Bayer R， Mccreight E M. Organization and maintenance of large ordered indexes[J]. Acta Informatica， 1972，1（3）：173-189.

[3] 李春葆，尹为民，李蓉蓉，等. 数据结构教程[M].3版.北京： 清华大学出版社， 2009.

[4] Cormen T H， Leiserson C E， RIVEST R L， et al. Introduction to Algorithms[M]. 3rd ed. Massachusetts： The MIT Press， 2009： 484-504.

[5] Horowitz E，等. 朱仲涛译. 数据结构基础（C语言版）[M]. 2nd ed. 北京： 清华大学出版社， 2009.endprint