二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(16)

例如，在图9-28 a 所示的3阶B-树中删除关键字63，由于关键字63所在的叶结点中的关键字的个数为1 m/2 -1 ，而此时与它相邻的左右兄弟结点的关键字的个数都等于 m/2 2，因此，删除关键字63后，可以考虑从它的双亲结点中下移关键字57，再从它的左兄弟结点中上移最大关键字52，结果如图9-28 b 所示。当然也可以从它所在的叶结点中删除关键字63后，从它的双亲结点中下移关键字78，再从它的右兄弟结点中上移最小关键字85，结果如图9-28 c 所示。⑶ 被删关键字所在的叶结点 *p删除前的关键字个数j m/2 -1，若这时与该结点相邻的左、右兄弟的关键字个数均为 m/2 - 1，则必须按以下步骤将该结点与它的左 或右 兄弟结点进行合并。ⅰ）将其双亲结点中小于 或大于 该被删关键字的所有关键字中的最大 或最小 的一个关键字Kf 下移到被删关键字所在的结点 *p中，将 *p与 *p的左 或右 兄弟结点合并；ⅱ）修改结点 *p和其双亲结点的关键字个数；ⅲ）由于在合并结点的过程中，双亲结点中的关键字减少了一个，因此，若这时结点*p的双亲结点为根结点且结点中的关键字个数减到0，则该双亲结点应从树上删去，合并后保留的结点 *p成为新的根结点；若双亲结点 *f不是根结点且关键字个数减到 m/2 - 2，则结点 *f又要与它自己的兄弟结点合并。

重复上述的合并过程，最坏情况下这种结点的合并处理要自下而上直到根结点。例如，在图9-29 a 所示的3阶B-树中删除关键字63，由于关键字63所在的叶结点中的关键字的个数为1 m/2 -1 ，而此时与它相邻的左右兄弟结点的关键字的个数也都等于 m/2 - 1 1，因此，删除关键字63后，可以考虑从它的双亲结点中下移关键字57，再把它和左兄弟结点合并为一个结点，结果如图9-29 b 所示。当然也可以在它所位于的叶结点中删除关键字63后，从它的双亲结点中下移关键字78，再把它和右兄弟结点合并为一个结点，结果如图9-29 c 所示。例9.15 图9-30给出了在一棵5阶B-树中依次删除关键字11, 97, 45, 63, 78, 42的过程。四、B + 树B + 树是可以在其叶结点上存储信息的树，它是B-树的一种变形，在实现文件索引结构方面比B-树应用得更广泛。一棵m阶B + 树可以定义为：⑴ 树中每个非叶结点至多有m棵子树。⑵ 根结点至少有2棵子树，除根结点外的每个非叶结点至少有 m/2 棵子树；有j棵子树的非叶结点含有j -1个关键字，且按由小到大的顺序排列；⑶ 所有的叶结点都处于同一层上，包含了全部关键字及指向相应记录的指针，且叶结点本身按关键字由小到大的顺序链接。

⑷ 每个叶结点中的子树棵数nj可以多于m，也可以少于m，视关键字字节数及记录地址指针字节数而定。若设叶结点最多可容纳m1个关键字，则指向记录的地址指针也有m1个，因此，结点中的子树棵数nj的取值范围应为： m1/2 ≤ nj ≤ m1。若根结点同时又是叶结点，则结点格式同叶结点。⑸ 所有的非叶结点可以看成是索引部分，结点中关键字Ki与指向子树的指针pi构成一个对子树 即下一层索引块 的索引项 Ki, pi ，其中关键字Ki ≤pi指向的子树中最小的关键字。特别地，子树指针p0所指子树中的所有关键字均小于K1。结点格式同B 树。例9.16 图9-31给出了在一棵5阶B + 树。所有非叶结点的子树棵数j均满足：3≤ j≤ 5，所有的关键字都出现在叶结点中，且在叶结点中关键字均有序地排列。这里假设叶结点最多可容纳m1 4个关键字，则每个叶结点可容纳的关键字的个数nj均满足：2 ≤nj ≤ 4。上面各层结点中的关键字都小于或等于右子树上最小的关键字。一般在B + 树上有两个起控制作用的头指针：一个指向B + 树的根结点，一个指向关键字最小的叶结点。这样就可以对B + 树进行两种查找操作：一种是沿叶结点组成的链表进行顺序查找。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-16.html