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

由于m阶B－树中的每个内部结点的关键字个数都在[ m/2 -1, m-1 ]之间，所以，如果在关键字插入后该叶结点中的关键字个数未超过上述范围的上界m-1，则可以直接插入；否则结点需要进行“”。结点“”可以这样来做：设结点 *p中已经有m-1个关键字，当再插入一个关键字后结点中的状态为：m,p0,K1,p1,K2,p2,…,Km,pm , 其中 Ki ＜ Ki+1, 1≤i＜m。这时必须把结点*p成两个结点 *p和 *q，它们包括的信息分别为：结点 *p： m/2 -1, p0, K1, p1, …, K m/2 -1, p m/2 -1结点 *q： m- m/2 , p m/2 , K m/2 +1, p m/2 +1, …, Km, pm位于中间的关键字K m/2 与指向新结点 *q的指针形成一个二元组 K m/2 , q ，并插入到这两个结点的双亲结点中去 见图9-25 。由于将 K m/2 , q 插入到双亲结点时，双亲结点可能原来也已经含有m-1个关键字，若是这样的话，则也需要对双亲结点进行操作。最坏的情况是，从入的叶结点到根的路径上各结点均为满额结点 即含有m-1个关键字 ，此时，插入过程中的操作一直向上传播到根。

当根结点时，由于根再没有双亲，所以需建立一个新的根结点，此时树长高一层。例9.14 将关键字序列 78, 21, 14, 11, 97, 85, 74, 63, 45, 42, 57, 20, 19, 16, 52, 30, 25 逐个插入到一棵初始为空的5阶B－树中。图9-26给出了这棵5阶B－树的生长过程。从B－树的生长过程可以看出两点：其一，当一个结点时所产生的两个结点基本是半满的，这就为以后的插入预备了较多的空间，特别是当m较大时，往这些半满的结点中插入新的关键字不会很快引起新的。其二，结点时向上层插入的关键字总是结点的中间位置上的关键字，而未必是正要插入的关键字。因此，无论按何种顺序插入关键字序列，树都是平衡的。对于高度为h的B－树，插入一个关键字时，在自顶向下查找叶结点的过程中需要读盘h次。最坏情况下，从入关键字所在的叶结点到根的路径上的所有结点自底向上地都要。非根结点需要向磁盘回写两个出的新结点，根结点需要向磁盘回写三个出的新结点。如果所用的内存空间足够大，使得在向下查找时读入的结点在插入后向上时不必再从磁盘读入，那么，完成一次插入操作所需要的读写磁盘的次数 向下查找插入位置的读盘次数 + 非根结点所做的写盘次数 + 根结点所做的写盘次数 h + 2 h-1 + 3 3h + 1。

⒋ B－树的删除如果想要在B－树上删除一个关键字，首先需要找到这个关键字所在的结点，从中删去这个关键字。若该结点不是叶结点 B－树中最下面一层上的内部结点,下同 ，且被删关键字为Ki 1≤i≤j ，则在删去该关键字之后，可以用该结点的pi所指子树中的最小关键字 或pi-1所指子树中的最大关键字 K来替代被删关键字Ki，然后在K所在的叶结点中删除K。现在的问题是如何在叶结点中删除关键字。在叶结点中删除关键字可分以下三种情况来分别处理：⑴ 若被删关键字所在的叶结点同时又是根结点且删除前该结点中的关键字个数j ≥2或被删关键字所在的叶结点不是根结点且删除前该结点中的关键字个数j ≥ m/2 ，则可直接删去该关键字并将修改后的结点写回磁盘，删除完成 参见图9-27 。⑵ 被删关键字所在的叶结点删除前的关键字个数j m/2 -1，若这时与该结点相邻的左 或右 兄弟的关键字个数j ≥ m/2 ，则可以按以下步骤调整该结点、左 或右 兄弟结点以及双亲结点，已达到新的平衡。ⅰ）将其双亲结点中小于 或大于 该被删关键字的所有关键字中的最大 或最小 的一个关键字Kf 下移到被删关键字所在的结点中；ⅱ）将左 或右 兄弟结点中的最大 或最小 的一个关键字Ks上移到双亲结点中Kf 的位置；ⅲ）将左 或右 兄弟结点的最右 或最左 子树指针删除，并将结点中的关键字个数减1。

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