第10章查找概要.ppt

3. B-树的删除 B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的关键字个数≥?m/2?-1,将涉及到结点的“合并”问题。在B-树上删除关键字k的过程分两步完成： (1) 利用前述的B-树的查找算法找出该关键字所在的结点。 (2) 在结点上删除关键字k分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关键字。 int InsertBST(BSTNode *p,KeyType k) /*在以*p为根结点的BST中插入一个关键字为k的结点。插入成功返回1,否则返回0*/ { if (p==NULL) /*原树为空, 新插入的记录为根结点*/ { p=(BSTNode *)malloc(sizeof(BSTNode)); p-key=k;p-lchild=p-rchild=NULL; return 1; } else if (k==p-key) /*存在相同关键字的结点,返回0*/ return 0; else if (kp-key) return InsertBST(p-lchild,k);/*插入到左子树中*/ else return InsertBST(p-rchild,k); /*插入到右子树中*/ } 二叉排序树的生成,是从一个空树开始,每插入一个关键字,就调用一次插入算法将它插入到当前已生成的二叉排序树中。从关键字数组A[0..n-1]生成二叉排序树的算法CreatBST()如下： BSTNode *CreatBST(KeyType A[],int n) /*返回树根指针*/ { BSTNode *bt=NULL; /*初始时bt为空树*/ int i=0; while (in) { InsertBST(bt,A[i]); /*将A[i]插入二叉排序树T中*/ i++; } return bt; /*返回建立的二叉排序树的根指针*/ } 例10.2 已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。 解：生成的二叉排序树如右图所示。 3. 二叉排序树的删除 删除操作必须首先进行查找,假设在查找过程结束时,已经保存了待删除结点及其双亲结点的地址。指针变量p指向待删除的结点,指针变量q指向待删除结点p的双亲结点。删除过程如下： (1) 若待删除的结点是叶子结点,直接删去该结点。如图(a)所示,直接删除结点9。这是最简单的删除结点的情况。 (2) 若待删除的结点只有左子树而无右子树。根据二叉排序树的特点,可以直接将其左子树的根结点放在被删结点的位置。如图(b)所示,*p作为*q的右子树根结点,要删除*p结点,只需将*p的左子树(其根结点为3)作为*q结点的右子树。 (3) 若待删除的结点只有右子树而无左子树。与(2)情况类似,可以直接将其右子树的根结点放在被删结点的位置。如图(c)所示,*p作为*q的左子树根结点,要删除*p结点,只需将*p的右子树(其根结点为8)作为*q结点的右子树。 (4) 若待删除的结点同时有左子树和右子树。根据二叉排序树的特点,可以从其左子树中选择关键字最大的结点或从其右子树中选择关键字最小的结点放在被删去结点的位置上。假如选取左子树上关键字最大的结点,那么该结点一定是左子树的最右下结点。如图(d)所示,若要删除*p(其关键字为5)结点,找到其左子树最右下结点4,它的双亲结点为2,用它代替*p结点,并将其原来的左子树(其根结点为3)作为原来的双亲结点2的右子树。 删除二叉排序树结点的算法DeleteBST()如下(指针变量p指向待删除的结点,指针变量q指向待删除结点*p的双亲结点)： void Delete1(BSTNode *p,BSTNode *r) /*当被删*p结点有左右子树时的删除过程*/ { BSTNode *q; if (r-rchild!=NULL) Delete1(p,r-rchild); /*递归找最右下结点*/ else /*找到了最右下结点*r*/ {