第九章-查找-精选版.ppt

一棵 m 阶的B-树，或是空树，或是满足以下条件的 m 叉树： （1）树中每个结点至多有 m 棵子树 （2）若根结点不是叶子结点，则至少有二棵子树。 （3）除根结点外的所有非终端结点至少有?m/2?棵子树 （4）所有结点包含信息（n,A0,K1,A1,…Kn,An)，其中Ki为关键字且有序。Ai为指向子树根结点的指针，Ai所指子树中所有结点的关键字均小于Ki+1,An所指子树中所有结点的关键字均大于Kn （5）所有叶子结点都出现在同一层次上，即所有空的指针出现在同一层上。 3 3 3 2 Data Structure n A0 K1 A1 … … Kn An n+1个分支 1 35 1 18 1 11 1 27 1 39 3 47 53 64 1 99 2 43 78 Data Structure B-树的操作 （1）查找 要查找关键字k的记录，首先从根结点开始，若找到则找所对应的记录，否则沿p所指的子树继续查找，其中： A0 kK1 P = Ai KikKi+1 An kKn 若直到叶子结点还未找到，则查找失败。 Data Structure （2）插入：设要插入关键值为k的记录，指向k所在记录的指针为p。 首先找到k应插入的叶子结点，将k和p插入。然后，判断被插入结点是否满足m叉B-树的定义，即插入后结点的分支数是否大于m（结点的关键字数是否大于m-1)，若不大于，则插入结束；否则，要把该结点分裂成两个。方法是： 申请一个新结点，由指针p’指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也要分裂，则在分裂后再往上插入。 Data Structure 45 24 3 12 37 50 53 90 95 61 70 插入30 ： 例：在下图的B-树中插入结点30和85 30 37 Data Structure 插入85 45 61 85 24 3 12 30 37 50 53 90 95 70 61 85 45 24 3 12 30 37 50 53 90 95 61 70 61 70 85 调整： Data Structure 45 61 85 24 3 12 30 37 50 53 90 95 70 61 85 调整： 45 24 3 12 50 53 95 70 61 85 90 30 37 Data Structure 算法9.5(b)：二叉排序树递归查找算法2 BiTree SearchBST(BiTree T, keyType key,BiTree f,Bitree p) {//在根指针T所指二叉排序树中递归查找Key，若查找成功，则指针P指向该结点，并返回True；否则指针P指向查找路径上访问的最后一个结点并返回False，指针f的初始值为NULL。 if (!T) { p=f; return FALSE; } //查找不成功 else if EQ(key,T-data.key) {p=T; return TRUE}; //查找成功 else if LT(key,T-data.key) SearchBST(T-lchild,key,T,p); //在左子树中继续查找 else SearchBST(T-rchild,key,T,p); //在右子树中继续查找 }//SearchBST Data Structure 算法9.5(c)：二叉排序树非递归查找算法 BiTree SearchBST(BiTree T, keyType key, Bitree p) {p=NULL; whi