双数组.pptVIP

* * * 数据结构一、二 康维鹏 2010-10-24 5阶B-树示例 【例】下图给出了一棵包含24个英文字母的5阶B-树的存储结构图。  说明：　??? 按照定义，在5阶B-树里，根中的关键字数目可以是1～4，子树数可以是2～5；其它的结点中关键字数目可以是2～4，若该结点不是叶子，则它可以有3～5棵子树。 B-树 一棵m(m≥3)阶的B-树是满足如下性质的m叉树： (1)每个结点至少包含下列数据域：??? (n，P0，Kl，P1，K2，…，Ki，Pi) ??? n为关键字总数??? Ki(1≤i≤n)是关键字，关键字序列递增有序：K1 K2…Ki。??? Pi(0≤i≤n)是孩子指针。对于叶结点，每个Pi为空指针。 keys(P0)K1keys(P1)K2…Kikeys(Pi) (2)所有叶子是在同一层上，叶子的层数为树的高度h。 (3)每个非根结点中所包含的关键字个数j满足： (4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。   /** * @note 这是一个raw type的节点类型 * */ public abstract class BTreeNode { public int keyNum; public BTreeNode[] child; public T[] keyValue; public int nodeLevel; public BTreeNode parent; public BTreeNode() { child=mallocChildArray(2*M+2); keyValue=mallocValueArray(2*M+1); keyNum=0;nodeLevel=1;parent=null; } } B-树的实现 关键值查找 插入关键值 删除关键值 关键值查找 在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。　　对结点内的存放有序关键字序列的向量key[l..keynum] 用顺序查找或折半查找方法查找。 /** * @note 记录查找结果位置信息 * */ public class Position { public BTreeNode currNode=null; public BTreeNode parentNode=null; public int idx=-1;//位置信息 public boolean isfind=false;//查找是否成功 } B-树的实现 插入关键值 ???????? ?????  (1)首先在树中查找K，若找到则直接返回； (2)否则查找操作必失败于某个叶子上，然后将K插入该叶子中。 (2.a)若该叶子结点原来是非满的，则插入K后并未破坏B-树的性质，故插入K后即完成了插入操作； (2.b)若该结点原为满，则K插入后keynum=m，违反B-树性质(3)，故须调整使其维持B-树性质不变。 B-树的删除（1）删除操作的两个步骤???　 第一步骤：在树中查找被删关键字K所在的地点??? 　第二步骤：进行删去K的操作 （2）删去K的操作??? 　B-树是二叉排序树的推广，中序遍历B-树同样可得到关键字的有序序列。任一关键字K的中序前趋(后继)必是K的左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字。??? 　若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)K取代K，然后从叶子中删去K。 从叶子*x开始删去某关键字K的三种情形为：??? 　情形一：若x.keynumMin，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。 B-树的实现 删除关键值 情形二：若x-keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。 若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；*y被移出一个关键字，故其keynum减1，因它原大于Min，故减少1个关键字后keynum仍大于等于Min；而*x中已移入一个关键字，故删K后*x中仍有Min个关键字。涉及移动关键字的三个结点均满足B