《数据结构A》第07章.ppt

《《数据结构A》第07章.ppt》由会员分享，可在线阅读，更多相关《《数据结构A》第07章.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构 Data Structures in C+南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 第第7 7章章 动态集和搜索树动态集和搜索树 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.1二叉搜索树二叉搜索树7.2二叉平衡树二叉平衡树7.3B-树树南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.1 7.1 二叉搜索树二叉搜索树南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.1.1二叉搜索树的定

2、义二叉搜索树的定义定定义义7.1设设结结点点由由关关键键字字值值表表征征，假假定定所所有有结结点点的的关关键键字字值值各各不不相相同同，二二叉叉搜搜索索树树或或者者是是一一棵棵空空二二叉叉树树，或或者者是是具具有有下下列列性性质质的的二叉树：二叉树：（1）若若左左子子树树不不空空，则则左左子子树树上上所所有有结结点点的的关键字值均小于根结点的关键字值；关键字值均小于根结点的关键字值；（2）若若右右子子树树不不空空，则则右右子子树树上上所所有有结结点点的的关键字值均大于根结点的关键字值；关键字值均大于根结点的关键字值；（3）左、右子树也分别是二叉搜索树。）左、右子树也分别是二叉搜索树。南京邮电大

3、学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 性性质质7.17.1 若若以以中中序序遍遍历历一一棵棵二二叉叉搜搜索索树树，将将得到一个以关键字值递增排列的有序序列。得到一个以关键字值递增排列的有序序列。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 二叉搜索树类二叉搜索树类二叉搜索树类二叉搜索树类 templatetemplateclassclassBSTreeBSTree:public:publicDynamicSetDynamicSet public:public:BSTree()root=NULL;Resul

4、tCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);protected:BTNode*root;private:private:ResultCodeSearch(BTNode*p,T&x)const;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.1.2二叉搜索树的搜索二叉搜索树的搜索 二叉搜索树搜索递归算法二叉搜索树搜索递归算法templateResultCodeBSTree:Search(T&x)constreturnSearch(root,x);南京邮电大学计算

5、机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 templateResultCodeBSTree:Search(BTNode*p,T&x)constif(!p)returnNotPresent;elseif(xelement)returnSearch(p-lChild,x);elseif(xp-element)returnSearch(p-rChild,x);elsex=p-element;returnSuccess;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 二叉搜索树搜索迭代算法二叉搜索树搜索迭代算法templat

6、eResultCodeBSTree:Search(T&x)constBTNode*p=root;while(p)if(xelement)p=p-lChild;elseif(xp-element)p=p-rChild;elsex=p-element;returnSuccess;returnNotPresent;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.1.3二叉搜索树的插入二叉搜索树的插入templateResultCodeBSTree:Insert(T&x)BTNode*p=root,*q=NULL;while(p)q=p;if(xelem

7、ent)p=p-lChild;elseif(xp-element)p=p-rChild;elsex=p-element;returnDuplicate;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 p=newp=newBTNodeBTNode(x);(x);if(!root!root)root=p;elseif(xelement)q-lChild=p;elseq-rChild=p;returnSuccess;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南

8、陈慧南 2006 2006年年9 9月月 7.1.4二叉搜索树的删除二叉搜索树的删除若结点若结点*p有两棵非空子树有两棵非空子树需需搜搜索索*p的的中中序序遍遍历历次次序序下下的的直直接接后后继继（或或直直接接前前驱驱）结结点点，设设为为*s，将将*s的的值值复复制制到到*p中中，称称为为替替代代，因因为为*s最最多多只只有有一一棵棵非非空空子子树树，这这样样一一来来，问问题题转转化化为为“被被删删除除的的结结点点最最多多只只有有一一棵棵非非空空子子树树”的的情形。情形。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 若结点若结点*p p 只有一棵非

9、空子树或只有一棵非空子树或*p p是叶子是叶子 以以*p p的的惟惟一一孩孩子子（设设为为*c c）或或空空子子树树（c cNULLNULL）取代取代*p p，链接至链接至*p p的双亲结点的双亲结点*q q。若若被被删删除除的的结结点点*p p是是根根结结点点，则则删删除除后后，结结点点*c c成成为为新新的的根根；若若*p p是是其其双双亲亲*q q的的左左孩孩子子，则则*c c也也应应成成为为*q q的的左左孩孩子子，否否则则*c c成成为为*q q的的右孩子。最后释放结点右孩子。最后释放结点*p p所占用的空间。所占用的空间。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2

10、006 2006年年9 9月月 删除删除28南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 templateResultCodeBSTree:Remove(T&x)BTNode*c,*s,*r,*p=root,*q=NULL;while(p&p-element!=x)/搜索搜索q=p;if(xelement)p=p-lChild;elsep=p-rChild;if(!p)returnNotPresent;x=p-element;南京邮电大学计算机学院南京邮电大

11、学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 if(p-lChild&p-rChild)/替代替代s=p-rChild;r=p;while(s-lChild)r=s;s=s-lChild;p-element=s-element;p=s;q=r;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 if(p-lChild)c=p-lChild;/删除结点删除结点elsec=p-rChild;if(p=root)root=c;elseif(p=q-lChild)q-lChild=c;elseq-rChild=c;deletep;returnSuc

12、cess;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.1.5平均情况时间分析平均情况时间分析二叉搜索树搜索的平均时间为二叉搜索树搜索的平均时间为O(log2n)。最坏情况搜索时间为最坏情况搜索时间为O(n)。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 假设在一个有假设在一个有n(n 1)个关键字的序列，有个关键字的序列，有i个关键字小于第一个关键字，个关键字小于第一个关键字，n-i-1个关键个关键字大于第一个关键字。由此序列构成的二字大于第一个关键字。由此序列构成的二叉搜索树，其左子树上有叉搜索

13、树，其左子树上有i个结点，而右子个结点，而右子树上有树上有n-i-1个结点。个结点。设设p pi i(n)(n)是在一棵有是在一棵有n n结点，其左子树上有结点，其左子树上有i i个结点，而右子树上有个结点，而右子树上有n-i-1n-i-1个结点的二叉个结点的二叉搜索树上以等概率进行搜索，成功搜索一搜索树上以等概率进行搜索，成功搜索一个关键字的平均比较次数。个关键字的平均比较次数。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 设设p(n)p(n)是在一棵有是在一棵有n n个结点的二叉搜索树上个结点的二叉搜索树上成功搜索一个关键字的平均比较次数成功搜

14、索一个关键字的平均比较次数。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 可用归纳法证明：可用归纳法证明：随机情况下，二叉搜索随机情况下，二叉搜索树树操作的平均操作的平均时间为时间为O(logO(log2 2n)n)。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.2二叉平衡树二叉平衡树南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.2.1二叉平衡树的定义二叉平衡树的定义定义定义定义定义7.27.2 二叉平衡树又称二叉平衡树又称二叉平衡树又称二叉平衡树又

15、称AVLAVL树树树树它它或或者者是是一一棵棵空空二二叉叉树树，或或者者是是具具有有下下列列性性质质的的二二叉树：叉树：（1）其根的左、右子树高度之差的绝对值不超过）其根的左、右子树高度之差的绝对值不超过1；（2）其根的左、右子树都是二叉平衡树。）其根的左、右子树都是二叉平衡树。结结点点的的平平衡衡因因子子定定义义为为该该结结点点的的左左子子树树的的高高度度减减去去右子树的高度。右子树的高度。AVLAVL二二二二叉叉叉叉搜搜搜搜索索索索树树树树既既是是二二叉叉搜搜索索树树又又是是AVL树树。在在下下面面的的讨讨论论中中，二二叉叉平平衡衡树树（AVL树树）是是指指AVL二二叉叉搜索树。搜索树。南

16、京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 9.2.2二叉平衡树类二叉平衡树类templatestructAVLNodeAVLNode(constT&x)element=x;lChild=rChild=NULL;bFbF=0;=0;Telement;intbFintbF;AVLNode*lChild,*rChild;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 templatetemplateclassclass

17、AVLTreeAVLTree:public:publicDynamicSetDynamicSet public:public:AVLTree()root=NULL;ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 private:private:AVLNode*root;ResultCodeInsert(AVLNode*&p,T&x,bool&unBalanced);voidLRotation(AVLNode*&

18、s,bool&unBalanced);voidRRotation(AVLNode*&s,bool&unBalanced);南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.2.3 二叉平衡树的平衡旋转二叉平衡树的平衡旋转 分别插入：分别插入：2525，3535，1414，4444南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 插插插插入入入入2525：从从根根到到25的的路路径径上上，所所有有结结点点的的平平衡衡因因子子均均为为0。插插入入新新元元素素25后后，这这棵棵树树仍仍然然是是二二叉叉平平衡树，但

19、整棵树高度加衡树，但整棵树高度加1。插插插插入入入入3535：从从根根到到35的的路路径径上上，36的的平平衡衡因因子子不不为为0，新新元元素素35被被插插在在36的的较较矮矮的的子子树树上上。插插入入后后，该树仍然是二叉平衡树。该树仍然是二叉平衡树。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 插插插插入入入入1414：从从根根到到14的的路路径径上上，12的的平平衡衡因因子子不不为为0，新新元元素素14被被插插在在12的的较较高高的的子子树树上上，即即14被被插插在在12的的右右子树的左子树上，插入后，该树不再是二叉平衡树。子树的左子树上，插入

20、后，该树不再是二叉平衡树。插插插插入入入入4444：从从根根到到44的的路路径径上上，43和和56的的平平衡衡因因子子都都不不为为0，其其中中56是是离离44最最近近的的，平平衡衡因因子子值值不不为为零零的的结结点点。新新元元素素44被被插插在在56的的较较高高的的那那棵棵子子树树上上，即即44被被插插在在56的的左左子子树树的的左左子子树树上上。插插入入后后，该该树树不不再再是是二二叉叉平平衡树。衡树。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 假定新结点假定新结点*q插在结点插在结点*s的左子树上的情况的左子树上的情况（1）新新结结点点*q已

21、已按按二二叉叉搜搜索索树树方方式式插插入入树树中；中；（2）结结点点*s是是新新结结点点*q的的具具有有非非零零平平衡衡因因子值子值(插入前的值插入前的值)的最近的祖先；的最近的祖先；（3）结点）结点*q插在结点插在结点*s的左子树上；的左子树上；（4）从从结结点点*s到到新新结结点点*q的的路路径径上上所所有有结结点（不含点（不含*s）的平衡因子值均已作修正。的平衡因子值均已作修正。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 情况一情况一 若插入前，从根结点到新结点若插入前，从根结点到新结点q q的插入位置的插入位置的路径上，所有结点的平衡因子

22、值均为的路径上，所有结点的平衡因子值均为0 0，插入，插入q q后，只需将根结点的平衡因子改为后，只需将根结点的平衡因子改为1 1，并且，并且AVLAVL树树的高度加的高度加1 1，插入操作完成。，插入操作完成。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 情况二情况二 若新结点若新结点q q插在结点插在结点s s较矮的子树上（较矮的子树上（s s的的平衡因子平衡因子bFbF为为-1-1，并假定，并假定q q插在插在s s的左子树上），的左子树上），则插入后只需令则插入后只需令s s的平衡因子的平衡因子bFbF为为0 0，插入算法，插入算法终止。终

23、止。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 情况三情况三:插在较高的子树上（插在较高的子树上（s-bF=+1）LL-旋转（旋转（r-bF=+1）南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 LR-LR-旋转（旋转（r-r-bFbF=-1=-1）南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 switch(u-u-bFbF)case1:s-bF=-1;r-bF=0;break;case0:s-bF=r-bF=0;break;case-1:s-bF=0;r-

24、bF=1;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 templatevoidAVLTree:LRotation(AVLNode*&s,bool&unBalanced)/左旋转函数左旋转函数左旋转函数左旋转函数AVLNode*u,*r=s-lChild;if(r-bF=1)/LL/LL/LL/LL 旋转旋转旋转旋转s-lChild=r-rChild;r-rChild=s;s-bF=0;s=r;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 else/LR/LR旋转旋转旋转旋转u=r-rChild;r-r

25、Child=u-lChild;u-lChild=r;s-lChild=u-rChild;u-rChild=s;switch(u-bF)case1:s-bF=-1;r-bF=0;break;case0:s-bF=r-bF=0;break;case-1:s-bF=0;r-bF=1;s=u;/s指示新子树的根指示新子树的根s-bF=0;/结点结点s的平衡因子为的平衡因子为0unBalanced=false;/结束重新平衡操作结束重新平衡操作南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.2.4 二叉平衡树的插入二叉平衡树的插入 南京邮电大学计算机学院南

26、京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 二叉平衡树的插入二叉平衡树的插入templateResultCodeAVLTree:Insert(AVLNode*&p,T&x,bool&unBalanced)ResultCoderesult=Success;if(p=NULL)/插入新结点插入新结点p=newAVLNode(x);unBalanced=true;else南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 if(xelement)/（续）续）result=Insert(p-lChild,x,unBalanced);if(

27、unBalanced)switch(p-bF)case-1:p-bF=0;unBalanced=false;break;case0:p-bF=1;break;case1:LRotation(p,unBalanced);elseif(x=p-element)/有重复元素有重复元素unBalanced=false;x=p-element;result=Duplicate;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 else/（续）续）result=Insert(p-rChild,x,unBalanced);if(unBalanced)switch(p

28、-bF)case1:p-bF=0;unBalanced=false;break;case0:p-bF=-1;break;case-1:RRotation(p,unBalanced);returnresult;南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.2.6二叉平衡树的高度二叉平衡树的高度定理定理具有具有n个结点的个结点的AVL树的高度树的高度h满足：满足：log2(n+1)h 1.4404log2(n+2)-0.328 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.3B-树树南京邮电大学计算

29、机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.3.1m叉搜索树叉搜索树定定义义7.3m叉叉搜搜索索树树或或者者是是一一棵棵空空树树，或或者者是是一一棵棵满足下列特性的树：满足下列特性的树：(1)根结点最多有根结点最多有m棵子树，并具有如下结构：棵子树，并具有如下结构：n,P0,（K1,P1）,（K2,P2）,（Kn,Pn）其其中中，Pi是是指指向向子子树树的的指指针针，0 i nm，Ki是是元元素素的关键字值，的关键字值，1 i nm；(2)KiKi+1,1 in；南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 (3

30、)子子树树Pi上上所所有有关关键键字字值值都都大大于于Ki，小小于于Ki+1,0in；(4)子子树树P0上上所所有有关关键键字字值值都都小小于于K1，子子树树Pn上上的的所有关键字值都大于所有关键字值都大于Kn；(5)子树子树Pi，0 i n也是也是m叉搜索树。叉搜索树。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.3.2B-树的定义树的定义定定定定义义义义7.4

31、7.4 一一棵棵m阶阶B-树树是是一一棵棵m叉叉搜搜索索树树，它它或或者者是是空树，或者是满足下列特性的树：空树，或者是满足下列特性的树：（1）根结点至少有两个孩子；）根结点至少有两个孩子；（2）除除根根结结点点和和失失败败结结点点外外的的所所有有结结点点至至少少有有 m/2 个孩子；个孩子；（3）所有失败结点均在同一层上。）所有失败结点均在同一层上。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.3.3B-树的高度树的高度性性性性质质质质7.27.2设设

32、B-树树失失败败结结点点的的总总数数是是s，那那么么，一一棵棵B-树树的的元元素素总总数数N是是B-树树的的失失败败结结点点的的总总数数减减，即即N=s-1。设设n是非失败结点数，是非失败结点数，t是指针总数是指针总数t=N+nt=N+ns+n-1s+n-1定理定理定理定理7.27.2有有N个元素的个元素的m阶阶B-树的高度是树的高度是因：因：N+1 2*（m/2）h-1南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.3.4 B-树的搜索树的搜索 磁盘访问的次数最多是磁盘访问的次数最多是1log m/2(N+1)/2)南京邮电大学计算机学院南京邮

33、电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.3.5 B-树的插入树的插入B-树插入新元素的方法树插入新元素的方法（1）在在B树树中中搜搜索索给给定定关关键键字字值值的的元元素素，如如果果搜搜索索成成功功，表表示示有有重重复复元元素素，插插入入运运算算失失败败终终止止，否否则则将将新新元元素素和和一一个个空空指指针针插插入入搜搜索索失失败败处处的的叶叶结点中。结点中。（2）若若插插入入新新元元素素（和和一一个个指指针针）后后，结结点点*q未未溢溢出出，即即结结点点中中包包含含的的元元素素个个数数未未超超过过m-1（指指针针数未超过数未超过m），），则插入运算成功终止。则插

34、入运算成功终止。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 （3）若若插插入入新新元元素素（和和一一个个指指针针后后），结结点点*q已已溢溢出出，则则必必须须进进行行结结点点的的分分裂裂操操作作，将将结结点点一一分分为为三三。分分裂裂发发生生在在位位置置 m/2 处处。关关键键字字值值K m/2 之之前前的的元元素素保保留留在在原原来来的的结结点点中中，在在它它之之后后的的元元素素存存放放在在新新创创建建的的结结点点（设设地地址址为为q）中中，而而关关键键字字值值为为K m/2 的的元元素素和和地地址址q将将插插入入结结点点*q的的双双亲亲结结点

35、点中中。这这意意味味着着在在该该双双亲亲结结点点中中新新增增了了一一个个元元素素和和一一个个指指针针，因因此此，必必须须检检查查此此双双亲亲结结点点的的溢溢出出问问题题。这这同同样样可可按按（2）和和（3）的原则，继续检查和处理该双亲结点。的原则，继续检查和处理该双亲结点。（4）如如果果按按照照（3）的的原原则则，根根结结点点*q产产生生分分裂裂，根根结结点点没没有有双双亲亲，那那么么分分裂裂产产生生的的两两个个结结点点的的指指针针q和和q以以及及关关键键字字为为K m/2 的的元元素素应应组组成成一一个个新新的的根根结结点点，B-树树增增高高一一。只只要要从从根根结结点点到到新新元元素素插插

36、入入结结点点的的路路径径上上至少有一个结点未满，至少有一个结点未满，B-树不会长高。树不会长高。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 插入插入59南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 插入插入53南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 7.3.6B-树的删除树的删除从从B-树删除元素的方法树删除元素的方法（1）首首先先搜搜索索被被删删除除的的元元素素，如如果果不不存存在在被被删删除除的的元元素素，则则删删除除运运算算失失败败终终止止。如

37、如果果搜搜索索成成功功，且且被被删删除除的的元元素素在在叶叶子子结结点点中中，则则从从该该叶叶子子结结点点中中删删除除该该元元素素；如如果果被被删删除除的的元元素素不不在在叶叶子子结结点点中中，那那么么由由它它的的右右侧侧子子树树上上的的最最小小元元素素取取代代之之（必必定定在在叶叶结结点点中中），然然后后从从叶叶子子结结点点中中删删除除该该替替代代元元素。素。（2）如如果果删删除除元元素素后后，当当前前结结点点中中包包含含至至少少 m/2m/2 -1 1个元素，删除运算成功结束。个元素，删除运算成功结束。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月

38、月 （3）如如果果删删除除元元素素后后，当当前前结结点点中中包包含含不不足足 m/2m/2 -1 1个个元元素素，则则称称发发生生下下溢溢。处处理理的的方方法法首首先先是是借借元元素素：如如果果其其左左侧侧兄兄弟弟包包含含多多余余 m/2-1个个元元素素，则则可可以以向向其其左左兄兄弟弟“借借”一一个个元元素素；否否则则如如果果其其右右侧兄弟有多余元素，则向其右侧兄弟借。侧兄弟有多余元素，则向其右侧兄弟借。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 （4）如如果果删删除除元元素素后后，当当前前结结点点产产生生下下溢溢，且且左左、右右两两侧侧兄兄弟

39、弟结结点点都都只只有有 m/2-1个个元元素素，则则只只能能进进行行“连连接接”。若若当当前前结结点点有有左左侧侧兄兄弟弟，则则将将该该结结点点与与其其左左侧侧兄兄弟弟连连成成一一个个结结点点，否否则则与与右右侧侧兄兄弟弟连连接接。连连接接是是将将两两个个结结点点中中的的元元素素，连连同同它它们们的的双双亲亲结结点点中中用用来来分分割割它它们们的的元元素素组组合合成成一一个个结结点点，另另一一个个结结点点将将撤撤消消。这这意意味味着着从从其其双双亲亲结结点点中中删删除除分分割割元元素素和和一一个个指指向向被被撤撤销销的的结结点点的的指指针针，这这可可能能导导致致双双亲亲结结点点的的下下溢溢，所

40、所以以需需继继续续检检查查其其双双亲亲结结点点。应应按按“（2），（3），（4）”所所述述方方法法处处理理从从双双亲亲结结点中删除元素的问题。点中删除元素的问题。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 （5）如如果果由由于于连连接接操操作作，导导致致根根结结点点中中的的一一个个元元素素被被删删除除，并并且且该该根根结结点点只只包包含含一一个个元元素素，则则其其中中的的元元素素被被删删除除后后，根根结结点点成成为为不不含含任任何何元元素素的的空空结结点点，那那么么两两结结点点连连接接后后被被保保留留的的那那个个结结点点将将成成为为B-树树新新的

41、的根根结结点点，这这时时，B-树树变变矮矮。如如果果B-树树本本来来是是只只有有一一个个根根结结点点，且且该该根根结结点点只只包包含含一一个个元元素素，那那么么当当这惟一的元素被删除后这惟一的元素被删除后B-树便成为空树。树便成为空树。南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 删除删除35南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月 删除删除27南京邮电大学计算机学院南京邮电大学计算机学院陈慧南陈慧南 2006 2006年年9 9月月