南京邮电大学数据结构A第7章

1、数据结构数据结构A 第第7章章 第第7章章 搜索树搜索树n集合可以采用树形结构表示，比如，用二叉搜索树、集合可以采用树形结构表示，比如，用二叉搜索树、二叉平衡树、二叉平衡树、 B-树等表示，通常称这些为搜索树。搜索树等表示，通常称这些为搜索树。搜索树有较高的搜索效率，又能有效地插入和删除元素，因树有较高的搜索效率，又能有效地插入和删除元素，因而更适合表示动态集。而更适合表示动态集。n 本课程讨论这三种常见的用于表示动态集的树形数本课程讨论这三种常见的用于表示动态集的树形数据结构：二叉搜索树、二叉平衡树和据结构：二叉搜索树、二叉平衡树和B-树。树。第第7章章 搜索树搜索树7.1 二叉搜索树二叉搜

2、索树二叉搜索树也称二叉二叉搜索树也称二叉排序树，是一种最容排序树，是一种最容易实现的搜索树。易实现的搜索树。第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树 7.1.1 7.1.1 二叉搜索树的定义二叉搜索树的定义 7.1.2 7.1.2 二叉搜索树的搜索二叉搜索树的搜索 7.1.3 7.1.3 二叉搜索树的插入二叉搜索树的插入 7.1.4 7.1.4 二叉搜索树的删除二叉搜索树的删除7.1 二叉搜索树二叉搜索树7.1.1 二叉搜索树的定义定义定义7.17.1 假定所有结点的关键字值各不假定所有结点的关键字值各不相同，二叉搜索树或者是一棵空二叉树，相同，二叉搜索树或者是一棵空二

3、叉树，或者是具有下列性质的二叉树：或者是具有下列性质的二叉树：(1)(1)若左子树不空，则左子树上所有结若左子树不空，则左子树上所有结点的关键字值均小于根结点关键字值；点的关键字值均小于根结点关键字值；(2)(2)若右子树不空，则右子树上所有结若右子树不空，则右子树上所有结点的关键字值均大于根结点关键字值；点的关键字值均大于根结点关键字值；(3)(3)左、右子树也分别是二叉搜索树。左、右子树也分别是二叉搜索树。递归定义递归定义第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树 7.1.1 7.1.1 二叉搜索树的定义二叉搜索树的定义 7.1.2 7.1.2 二叉搜索树的搜索二叉搜

4、索树的搜索 7.1.3 7.1.3 二叉搜索树的插入二叉搜索树的插入 7.1.4 7.1.4 二叉搜索树的删除二叉搜索树的删除7.1 二叉搜索树二叉搜索树7.1.1 二叉搜索树的定义性质性质7.1 若以若以中序遍历中序遍历一棵二叉搜索树，将得到一一棵二叉搜索树，将得到一个以关键字值个以关键字值递增递增排列的有序序列。排列的有序序列。6354874569762335图图7-1 二叉搜索树二叉搜索树7.1 二叉搜索树二叉搜索树7.1.1 二叉搜索树的定义程序程序7.1 二叉搜索树类二叉搜索树类 template class BSTree:public DynamicSet public: BSTr

5、ee() root=NULL; ResultCode Search(T & x) const; ResultCode Insert(T & x); ResultCode Remove(T & x); protected: BTNode* root; private: ResultCode Search(BTNode *p, T & x)const; ;7.1 二叉搜索树二叉搜索树7.1.2 二叉搜索树的搜索1.1.二叉搜索树搜索的递归算法二叉搜索树搜索的递归算法2.2.二叉搜索树搜索的迭代算法二叉搜索树搜索的迭代算法第第7 7章章 搜索树搜索树7.1 7.1 二

6、叉搜索树二叉搜索树 7.1.1 7.1.1 二叉搜索树的定义二叉搜索树的定义 7.1.2 7.1.2 二叉搜索树的搜索二叉搜索树的搜索 7.1.3 7.1.3 二叉搜索树的插入二叉搜索树的插入 7.1.4 7.1.4 二叉搜索树的删除二叉搜索树的删除7.3 B7.3 B树树7.1 二叉搜索树二叉搜索树7.1.2 二叉搜索树的搜索(1) (1) 若二叉树为空，则搜索失败。若二叉树为空，则搜索失败。(2) (2) 否则，将否则，将x x与根结点比较，与根结点比较，若若x x小于该结点的值，则以同样的方法搜索左子树，而小于该结点的值，则以同样的方法搜索左子树，而不必搜索右子树；不必搜索右子树；若若x

7、 x大于该结点的值，则以同样的方法搜索右子树，而大于该结点的值，则以同样的方法搜索右子树，而不必搜索左子树；不必搜索左子树；若若x x等于该结点的值，则搜索成功终止。等于该结点的值，则搜索成功终止。1. 二叉搜索树搜索的递归算法二叉搜索树搜索的递归算法查找与查找与x的关键字值相同的元素的的关键字值相同的元素的递归算法递归算法可描述如下：可描述如下：7.1 二叉搜索树二叉搜索树7.1.2 二叉搜索树的搜索程序程序7.2 二叉搜索树搜索的递归算法二叉搜索树搜索的递归算法template ResultCode BSTree:Search(T & x) const return Search(

8、root,x);template ResultCode BSTree:Search(BTNode *p, T & x) const if (!p) return NotPresent; else if (xelement) return Search(p-lChild,x); else if(xp-element) return Search(p-rChild,x); else x=p-element;return Success; 7.1 二叉搜索树二叉搜索树7.1.2 二叉搜索树的搜索2. 二叉搜索树的迭代算法二叉搜索树的迭代算法 二叉搜索树的迭代算法二叉搜索树的迭代算法使用使用w

9、hile循环，从根结点开始循环，从根结点开始搜索，将待查元素搜索，将待查元素x与当前元素比较。与当前元素比较。 若若x等于该结点的值，则搜索成功终止；等于该结点的值，则搜索成功终止； 若若x小于该结点的值，则继续搜索左子树；小于该结点的值，则继续搜索左子树； 否则继续搜索右子树。否则继续搜索右子树。只有搜索到空子树时，才失败终止。只有搜索到空子树时，才失败终止。7.1 二叉搜索树二叉搜索树7.1.2 二叉搜索树的搜索程序程序7.3 二叉搜索树搜索的迭代算法二叉搜索树搜索的迭代算法template ResultCode BSTree:Search(T & x) const BTNode

10、*p=root; while (p) if ( x element) p=p-lChild; else if (x p-element) p=p-rChild; else x=p-element; return Success; return NotPresent; 63548745697623357.1 二叉搜索树二叉搜索树7.1.3 二叉搜索树的插入二叉搜索树的插入步骤与单链表的插二叉搜索树的插入步骤与单链表的插入步骤类似。入步骤类似。(1) 查找插入元素的位置；查找插入元素的位置；(2) 生成新结点；生成新结点；(3) 插入新结点插入新结点(有可能修改有可能修改root指针指针)第第7

11、7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树 7.1.1 7.1.1 二叉搜索树的定义二叉搜索树的定义 7.1.2 7.1.2 二叉搜索树的搜索二叉搜索树的搜索 7.1.3 7.1.3 二叉搜索树的插入二叉搜索树的插入 7.1.4 7.1.4 二叉搜索树的删除二叉搜索树的删除7.3 B7.3 B树树7.1 二叉搜索树二叉搜索树7.1.3 二叉搜索树的插入 在二叉搜索树上插入一个新元素，首先应搜索新元素的在二叉搜索树上插入一个新元素，首先应搜索新元素的插入位置，同时，插入位置，同时，需要需要在自根结点向下搜索过程中，记录当在自根结点向下搜索过程中，记录当前结点的双亲结点，设为前结点的

12、双亲结点，设为q。 如果二叉树中有重复元素，应返回如果二叉树中有重复元素，应返回Duplicate。 搜索到达空子树时，构造一个新结点搜索到达空子树时，构造一个新结点p存放新元素存放新元素x，并连接至结点并连接至结点q，成为，成为q的孩子（的孩子（p是是q的左孩子还是右孩的左孩子还是右孩子取决于子取决于x与与q关键字值的大小）；如果原二叉搜索树是关键字值的大小）；如果原二叉搜索树是空树，则新结点空树，则新结点p成为新二叉搜索树的根。成为新二叉搜索树的根。7.1 二叉搜索树二叉搜索树7.1.3 二叉搜索树的插入在二叉搜索树中插入在二叉搜索树中插入4343的执行过程的执行过程: :28213633

13、2543q=pq43p=p7.1 二叉搜索树二叉搜索树7.1.3 二叉搜索树的插入213633432528 下图显示了从空树开始通过依次插入元素，下图显示了从空树开始通过依次插入元素，构造一棵二叉搜索树的过程。构造一棵二叉搜索树的过程。(a)空树空树(b)插入插入28(c)插入插入21(d)插入插入25(e)插入插入36(f)插入插入33(g)插入插入437.1 二叉搜索树二叉搜索树7.1.3 二叉搜索树的插入程序程序7.4 二叉搜索树的插入运算二叉搜索树的插入运算template ResultCode BSTree:Insert(T& x) BTNode *p=root, *q=NU

14、LL; while (p) q=p; if ( x element ) p=p-lChild; else if ( x p-element) p=p-rChild; else x=p-element; return Duplicate; p=new BTNode(x); if ( !root ) root=p; else if ( x element ) q-lChild=p; else q-rChild=p; return Success;查找插入位置查找插入位置生成新结点生成新结点插入新结点插入新结点7.1 二叉搜索树二叉搜索树7.1.4 二叉搜索树的删除 在二叉搜索树上删除一个结在二叉搜

15、索树上删除一个结点与插入运算类似，应先搜索被删点与插入运算类似，应先搜索被删除结点除结点p，并记录，并记录p的双亲结点的双亲结点q。第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树 7.1.1 7.1.1 二叉搜索树的定义二叉搜索树的定义 7.1.2 7.1.2 二叉搜索树的搜索二叉搜索树的搜索 7.1.3 7.1.3 二叉搜索树的插入二叉搜索树的插入 7.1.4 7.1.4 二叉搜索树的删除二叉搜索树的删除7.3 B7.3 B树树Hibbard Deletion, 1960 7.1 二叉搜索树二叉搜索树7.1.4 二叉搜索树的删除如果不存在指定删除的元素，应返回如果不存在指定

16、删除的元素，应返回NotPresent。否则，删除结点否则，删除结点p的操作由下列几步组成：的操作由下列几步组成：(1) 若若结点结点p有两棵非空子树有两棵非空子树，需搜索结点，需搜索结点p的中序遍历次序下的中序遍历次序下的直接后继结点，设为的直接后继结点，设为s。将。将s中的值复制到中的值复制到p中，删除中，删除s结点。结点。如果如果s结点是结点是p的直接后继，则的直接后继，则s必定没有左孩子（右孩子）。必定没有左孩子（右孩子）。此时，问题就简化为此时，问题就简化为“被删除的结点最多只有一棵非空子树被删除的结点最多只有一棵非空子树”的情形。的情形。(2)若若结点结点p只有一棵非空子树或只有一

17、棵非空子树或p是叶子是叶子，以结点，以结点p的唯一孩子的唯一孩子（设为结点（设为结点c）或空子树（）或空子树（c=NULL）取代）取代p。(3)若若被删除的结点被删除的结点p是根结点是根结点，则删除后，结点，则删除后，结点c成为新的根；成为新的根；否则，若否则，若p是其双亲是其双亲q的左孩子，则结点的左孩子，则结点c也应该成为也应该成为q的左孩的左孩子，不然子，不然c成为成为q的右孩子。最后释放结点的右孩子。最后释放结点p所占的空间。所占的空间。7.1 二叉搜索树二叉搜索树7.1.4 二叉搜索树的删除2833删除删除2128213633432523353423删除删除2328213633432

18、5353421删除删除2825364335342833二叉搜索树二叉搜索树上删除元素上删除元素7.1 二叉搜索树二叉搜索树7.1.4 二叉搜索树的删除2928 下图结合程序，演示删除一个有左右下图结合程序，演示删除一个有左右孩子结点的过程。孩子结点的过程。282536433230例如删除例如删除2834prsq=x=29q7.1 二叉搜索树二叉搜索树7.1.4 二叉搜索树的删除程序程序7.5 二叉搜索树的删除运算二叉搜索树的删除运算template ResultCode BSTree:Remove(T& x) BTNode *c,*s,*r,*p=root,*q=NULL; while

19、 (p & p-element!=x) q=p; /q为为p的双亲的双亲 if (xelement) p=p-lChild; else p=p-rChild; if(!p) return NotPresent; x=p-element; 搜索要删除的结点搜索要删除的结点28213633432523353421 qp7.1 二叉搜索树二叉搜索树7.1.4 二叉搜索树的删除 if (p-lChild & p-rChild) s = p-rChild; r = p; while (s-lChild) /结点结点s是是p的中序后继，的中序后继， r = s; s = s-lChild;

20、 / r是是s的双亲的双亲 p-element = s-element; /将将s的值复制到的值复制到p中，中， p=s; q=r; /准备删除准备删除p，指针，指针q指示指示p的双亲的双亲 if (p-lChild) c = p-lChild; else c = p-rChild; /准备以结点准备以结点c取代结点取代结点p if(p = root) root = c; /以结点以结点c取代结点取代结点p else if (p = q-lChild) q-lChild = c; else q-rChild = c; delete p; return Success;转化为被删转化为被删除的结

21、点除的结点 p 最多只有一最多只有一个孩子个孩子2821363343252335347.1 二叉搜索树二叉搜索树二叉搜索树搜索算法二叉搜索树搜索算法分析分析最好情况和一般情况：最好情况和一般情况：O(logO(log2 2n)n)最坏情况：单支树，最坏情况：单支树，O(n)O(n)输入：输入：28,21,36,25,33,35,43.28,21,36,25,33,35,43. 输入：输入：28,21,25,33,43,36,35.28,21,25,33,43,36,35.输入：输入：21,25,28,33,35,36,43.21,25,28,33,35,36,43.28282121252536

22、3633334343353528282121252533333535434336362121252528284343.7.1 二叉搜索树二叉搜索树 平均情况下，二叉搜索树的搜索、插入和平均情况下，二叉搜索树的搜索、插入和删除操作的渐近时间复杂度均为删除操作的渐近时间复杂度均为O(logO(log2 2n)n)。由关键字序列由关键字序列 3 3，1 1，2 2，5 5，4 4构造而得的二叉排序树构造而得的二叉排序树由关键字序列由关键字序列 1 1，2 2，3 3，4 4，5 5构造而得的二叉排序树，构造而得的二叉排序树，ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3

23、）/ 5 = 2.2(a)(b)21345354127.2 二叉平衡树二叉平衡树二叉平衡树（二叉平衡树（Self-Balancing Binary Self-Balancing Binary Search TreeSearch Tree），又称），又称AVLAVL树，是一种二叉排树，是一种二叉排序树，其中每一个节点的左子树和右子树的序树，其中每一个节点的左子树和右子树的高度差至多等于高度差至多等于1 1。h hL L-h-hR R =1=17.2 二叉平衡树二叉平衡树G.M. G.M. A Adelson-delson-V Velskii & E.M. elskii & E.M

24、. L Landis(andis(俄罗斯，俄罗斯，1962)1962)7.2 二叉平衡树二叉平衡树定义定义7.2 二叉平衡树又称二叉平衡树又称AVLAVL树，它或者是一棵空二树，它或者是一棵空二叉树，或者是具有下列性质的二叉树：叉树，或者是具有下列性质的二叉树：(1)(1)其根的左、右子树高度之差的绝对值不超过其根的左、右子树高度之差的绝对值不超过1 1；(2)(2)其根的左、右子树都是二叉平衡树。其根的左、右子树都是二叉平衡树。n 平衡因子（平衡因子（BFBF）: : 结点结点左左子树的高度减去子树的高度减去右右子树子树的高度。的高度。7.2 二叉平衡树二叉平衡树(1)(1)(2)(2)(3

25、)(3)(4)(4)0 01 10 0-1-10 0BF=2BF=27.2 二叉平衡树二叉平衡树n 最小不平衡子树最小不平衡子树：距离插入结点最近的且平衡因子的绝对值大于1的结点为根的子树。n 当插入新结点37时37370 0-1-11 10 00 02 2最小不平衡子树最小不平衡子树7.2 二叉平衡树二叉平衡树AVL树实现原理 n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，88二叉排序树二叉排序树AVLAVL树树7.2 二叉平衡树二叉平衡树AVL树实现原理 n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，883 3

26、插入插入3 3插入插入2 23 303 32 2102 21 11022 21 1003 30插入插入1 1右旋右旋仅对最小不平衡最小不平衡子树子树进行旋转NEXTNEXT：插入：插入4 47.2 二叉平衡树二叉平衡树AVL树实现原理 n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，88插入插入4 4插入插入5 5左旋左旋4 402 21 1- -103 3- -13 34 4-1-12 21 1- -20-2-25 504 40 02 21 1- -100 05 503 3NEXTNEXT：插入：插入6 67.2 二叉平衡树二叉平衡树AVL树实现原理 n

27、实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，88插入插入6 6左旋左旋2 24 4-1-11 1- -20-1-15 503 30 06 66 64 42 20 00-1-15 501 13 300NEXTNEXT：插入：插入7 77.2 二叉平衡树二叉平衡树AVL树实现原理 n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，88插入插入7 7左旋左旋6 64 42 2-1-10-2-25 5- -11 13 3007 706 64 42 20 000 001 13 3007 705 5NEXTNEXT：插入：插入10

28、107.2 二叉平衡树二叉平衡树AVL树实现原理 n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，88插入插入10106 64 42 2-1-10-1-1-1-11 13 3007 705 510100-1-1000NEXTNEXT：插入：插入9 97.2 二叉平衡树二叉平衡树n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，88插入插入9 91 1 右旋右旋2 2 左旋左旋NEXTNEXT：插入：插入8 87.2 二叉平衡树二叉平衡树n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，

29、88插入插入8 81 1 右旋右旋2 2 左旋左旋7.2 二叉平衡树二叉平衡树n实例：实例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，881.1. 确定最小不平衡子树确定最小不平衡子树T T；2.2. 适当旋转，形成适当旋转，形成AVLAVL树；树；7.2 二叉平衡树二叉平衡树n 二叉平衡树的插入，其关键在于不平衡时的调整二叉平衡树的插入，其关键在于不平衡时的调整n 调整方案主要包含两类：调整方案主要包含两类： 单旋转调整单旋转调整 双旋转调整双旋转调整7.2 二叉平衡树二叉平衡树插入插入N N前是平衡二叉树前是平衡二叉树插入插入N N后平衡性打破后平衡性打破插入

30、插入N N调整后恢复平衡性调整后恢复平衡性右旋右旋第第1 1类类单旋转调整单旋转调整左旋左旋类似类似7.2 二叉平衡树二叉平衡树插入插入N N前是平衡二叉树前是平衡二叉树插入插入N N后平衡性打破后平衡性打破插入插入N N保证根结点和其左孩子保证根结点和其左孩子BFBF符号相同符号相同第第2 2类类双旋转调整双旋转调整左旋左旋右旋右旋7.3 B-树树 n内搜索内搜索：当集合足够小，可以驻：当集合足够小，可以驻留在内存中时，相应的搜索方法称留在内存中时，相应的搜索方法称为内搜索。为内搜索。n外搜索外搜索：如果文件很大，以至于：如果文件很大，以至于计算机内存容不下时，它们必须存计算机内存容不下时，

31、它们必须存放在外存中。在外存中搜索给定关放在外存中。在外存中搜索给定关键字值的元素的方法称为外搜索。键字值的元素的方法称为外搜索。内存中集合用二叉平衡树表示。外内存中集合用二叉平衡树表示。外存中，集合可以用存中，集合可以用B-B-树来表示。树来表示。第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树7.3 B7.3 B树树 7.3.1 m7.3.1 m叉搜索树叉搜索树 7.3.2 B-7.3.2 B-树的定义树的定义 7.3.3 B-7.3.3 B-树的高度树的高度 7.3.4 B-7.3.4 B-树的搜索树的搜索 7.3.5 B-7.3.5 B-树的插入树的插入 7.3.6 B

32、-7.3.6 B-树的删除树的删除7.3 B-树树7.3.1 m叉搜索树 典型的磁盘存取时间是典型的磁盘存取时间是1ms 10ms，而典型的内存存取时间是，而典型的内存存取时间是10ns100ns。内存的存取速度比磁。内存的存取速度比磁盘快盘快1万至百万倍。万至百万倍。设法减少磁盘存取操作的次数是外设法减少磁盘存取操作的次数是外搜索算法设计应充分考虑的问题。搜索算法设计应充分考虑的问题。第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树7.3 B7.3 B树树 7.3.1 m7.3.1 m叉搜索树叉搜索树 7.3.2 B-7.3.2 B-树的定义树的定义 7.3.3 B-7.3.

33、3 B-树的高度树的高度 7.3.4 B-7.3.4 B-树的搜索树的搜索 7.3.5 B-7.3.5 B-树的插入树的插入 7.3.6 B-7.3.6 B-树的删除树的删除7.3 B-树树7.3.1 m叉搜索树 定义定义7.3 m叉搜索树或者是一棵空叉搜索树或者是一棵空m叉搜索树，或者是一棵叉搜索树，或者是一棵满足下列特性的树。满足下列特性的树。 根结点最多有根结点最多有m棵子树，并具有如下结构：棵子树，并具有如下结构： n，P0，（，（K1，P1），（），（K2，P2），），（，（Kn，Pn） 其中，其中，Pi是指向子树的指针，是指向子树的指针，0i n m， Ki是关键字值，是关键字值，

34、1 i nm。 KiKi+1 , 1 in 子树子树Pi上的所有关键字值都大于上的所有关键字值都大于Ki，小于，小于Ki+1, 0i35，则沿着，则沿着35右边的子树向下搜索，并再从右边的子树向下搜索，并再从43和和78中间的子树上找到中间的子树上找到53, 搜索成功。搜索成功。 搜索搜索54，搜索失败。，搜索失败。5354搜索成功！搜索成功！搜索失败！搜索失败！7.3 B-树树7.3.1 m叉搜索树 3. m叉搜索树的性质叉搜索树的性质 设一棵设一棵m叉搜索树的高度为叉搜索树的高度为h，则该树上最多的，则该树上最多的结点结点数数目（不包括失败结点）为：目（不包括失败结点）为： m叉搜索树中，

35、每个叉搜索树中，每个结点结点最多有最多有m-1个个元素元素，因此，因此m叉叉搜索树中最多有搜索树中最多有mh-1个元素。个元素。101111hihhimmmmm7.3 B-树树7.3.1 m叉搜索树 3. m叉搜索树的性质叉搜索树的性质 设设N是高度为是高度为h的的m叉搜索树中元素的个数，叉搜索树中元素的个数，1hmN从而推出：从而推出：) 1(logNhm一棵一棵m叉搜索树的高度在叉搜索树的高度在logm(N+1)到到N之间。之间。7.3 B-树树7.3.2 B-树的定义定义定义7.4 一棵一棵m阶阶B-树是一棵树是一棵m叉搜叉搜索树，它或者是空索树，它或者是空B-树，或者是满树，或者是满足

36、下列特性的树：足下列特性的树： 根结点至少有两个孩子。根结点至少有两个孩子。 除根结点和失败结点外的所有结除根结点和失败结点外的所有结点点至少至少有有 m/2 个孩子。个孩子。 所有失败结点均在同一层上。所有失败结点均在同一层上。Bayer-McCreight, 1972第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树7.3 B7.3 B树树 7.3.1 m7.3.1 m叉搜索树叉搜索树 7.3.2 B-7.3.2 B-树的定义树的定义 7.3.3 B-7.3.3 B-树的高度树的高度 7.3.4 B-7.3.4 B-树的搜索树的搜索 7.3.5 B-7.3.5 B-树的插入树

37、的插入 7.3.6 B-7.3.6 B-树的删除树的删除7.3 B-树树7.3.2 B-树的高度从定义中可以得到，一棵从定义中可以得到，一棵4阶阶B-树中树中(1)一个结点最多有一个结点最多有4个孩子个孩子(2)除根结点和失败结点外每个结点最少有除根结点和失败结点外每个结点最少有 4/2 =2个孩子，个孩子， 根结点最少有根结点最少有2个孩子个孩子(3) 所有失败结点均在同一层上所有失败结点均在同一层上3518112743 783947 53 64994阶阶B-树树 7.3 B-树树7.3.3 B-树的高度性质性质7.27.2 设设B-B-树失败结点的总数是树失败结点的总数是s s，一棵，一棵

38、B-B-树包含的元素树包含的元素总数总数N N，则有，则有: N = s : N = s 1 1证明：证明： 每个非失败结点中的包含的元素数目比它所包含的指针每个非失败结点中的包含的元素数目比它所包含的指针数少数少1。设非失败结点总数为。设非失败结点总数为n，则，则B-树的元素总数树的元素总数N等于所等于所有非失败结点包含的指针总数有非失败结点包含的指针总数t减去减去n，即，即N=t-n， 而指针总数而指针总数t等于除根结点以外，失败结点数和非失败等于除根结点以外，失败结点数和非失败结点数的总和，即结点数的总和，即t = n+s-1。 所以有所以有 n+s-1 = N + n ，整理得，整理得

39、N=s-1。7.3 B-树树7.3.3 B-树的高度定理定理7.2 N个元素的个元素的m阶阶B-树的高度树的高度h有有)21(log12/Nhm 证明：证明： 设设m阶阶B-树有树有N个元素，则失败结点的个数为个元素，则失败结点的个数为N+1。 B-树第树第1层为根结点。根结点至少有层为根结点。根结点至少有2个孩子，所以第个孩子，所以第2层至少有层至少有2个结点。除根以外，每个非失败结点至少有个结点。除根以外，每个非失败结点至少有 m/2 个孩子。个孩子。，依此类推，第，依此类推，第h+1层至少有层至少有2( m/2 )h-1 个结个结点。而第点。而第h+1层是失败结点。层是失败结点。 所以有

40、所以有1)2/(21hmN 整理后即可得到定理整理后即可得到定理7.2。7.3 B-树树7.3.4 B-树的搜索第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树7.3 B7.3 B树树 7.3.1 m7.3.1 m叉搜索树叉搜索树 7.3.2 B-7.3.2 B-树的定义树的定义 7.3.3 B-7.3.3 B-树的高度树的高度 7.3.4 B-7.3.4 B-树的搜索树的搜索 7.3.5 B-7.3.5 B-树的插入树的插入 7.3.6 B-7.3.6 B-树的删除树的删除 B-树的搜索算法与树的搜索算法与m叉搜索树的叉搜索树的搜索算法相同。但搜索算法相同。但B-树搜索需执行

41、的树搜索需执行的磁盘访问次数最多是磁盘访问次数最多是 1+log m/2 (N+1)/2) B-树的每个结点可以看成一个有树的每个结点可以看成一个有序表，在一个序表，在一个B-树结点中搜索时在内树结点中搜索时在内存中的搜索，因此可以采用顺序搜索存中的搜索，因此可以采用顺序搜索和二分搜索等内搜索算法进行。和二分搜索等内搜索算法进行。7.3 B-树树7.3.5 B-树的插入第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树7.3 B7.3 B树树 7.3.1 m7.3.1 m叉搜索树叉搜索树 7.3.2 B-7.3.2 B-树的定义树的定义 7.3.3 B-7.3.3 B-树的高度树

42、的高度 7.3.4 B-7.3.4 B-树的搜索树的搜索 7.3.5 B-7.3.5 B-树的插入树的插入 7.3.6 B-7.3.6 B-树的删除树的删除 将一个元素插入将一个元素插入B-树：树：n 首先，搜索首先，搜索B-树中是否包含相同关树中是否包含相同关键字值的元素，若存在，则插入失败。键字值的元素，若存在，则插入失败。n 否则，搜索必定终止在失败结点处，否则，搜索必定终止在失败结点处，此时，将新元素插在该失败结点的上此时，将新元素插在该失败结点的上一层的叶子结点中。一层的叶子结点中。n 如果插入后，该叶子结点中包含的如果插入后，该叶子结点中包含的元素个数不超过元素个数不超过m-1，则

43、插入成功，则插入成功，否则，需进行结点分裂。否则，需进行结点分裂。7.3 B-树树7.3.5 B-树的插入例例1 在图在图7.23的的4阶阶B-树中插入新的元素树中插入新的元素59。3518112743 783947 53 6499图图7-23 4阶阶B-树树 7.3 B-树树7.3.5 B-树的插入例例1 在图在图7.23的的4阶阶B-树中插入新的元素树中插入新的元素59。步骤步骤1：搜索新元素：搜索新元素 在在B-树中搜索元素树中搜索元素59（搜索失败处是图中红色的失败结点）（搜索失败处是图中红色的失败结点） q是失败结点的上一层叶子结点，是失败结点的上一层叶子结点，r是是q的双亲结点。的

44、双亲结点。3518112743 783947 53 649959rq7.3 B-树树7.3.5 B-树的插入例例1 在图在图7.23的的4阶阶B-树中插入新的元素树中插入新的元素59。3518112743 7839 47 53 6499rq步骤步骤2：将新元素和一个空指针插入到：将新元素和一个空指针插入到q中中 q中插入新元素和失败结点后，如果中插入新元素和失败结点后，如果q没有溢出，即没有溢出，即结点中包含的元素个数未超过结点中包含的元素个数未超过m-1（指针数没有超过（指针数没有超过m），），则插入运算结束，否则进行步骤则插入运算结束，否则进行步骤3分裂操作。分裂操作。5935181127

45、43 783947 53 6499rq597.3 B-树树7.3.5 B-树的插入例例1 在图在图7.23的的4阶阶B-树中插入新的元素树中插入新的元素59。步骤步骤3：分裂：分裂 分裂发生在分裂发生在q中第中第 m/2 个元素的位置，个元素的位置，结点结点q被一分为三，被一分为三， 即即q、k m/2 和和q。 q中保存前中保存前 m/2 个元素，个元素，q中保存后中保存后 m/2 个个元素。多出的元素。多出的k m/2 和和q 一起插入其到双亲结点一起插入其到双亲结点r中。中。3518112743 783999r 47 64q59q4759 64q53537.3 B-树树7.3.5 B-树

46、的插入例例2 ：在：在3阶阶B-树中插入树中插入新元素新元素537.3 B-树树7.3.5 B-树的插入B树插入新元素的方法。树插入新元素的方法。(1) 在在B-树中搜索给定关键字值的元素，如果搜索成功，插入运算失败树中搜索给定关键字值的元素，如果搜索成功，插入运算失败终止，否则将新元素和一个空指针插入搜索失败处的叶子结点中。终止，否则将新元素和一个空指针插入搜索失败处的叶子结点中。 (2) 若插入新元素（和一个指针）后，结点若插入新元素（和一个指针）后，结点q未溢出，即结点中包含的未溢出，即结点中包含的元素个数未超过元素个数未超过m-1（指针数未超过（指针数未超过m），则插入运算成功终止。）

47、，则插入运算成功终止。(3) 若插入新元素（和一个指针）后，结点若插入新元素（和一个指针）后，结点q已溢出，则必须进行结点已溢出，则必须进行结点的分裂操作，将结点一分为三。分裂发生在位置的分裂操作，将结点一分为三。分裂发生在位置 m/2 处。将处。将 m/2 处处的元素和新结点插入双亲结点中。双亲结点中新增加了一个元素和一的元素和新结点插入双亲结点中。双亲结点中新增加了一个元素和一个指针，因此，必须检查次双亲结点的溢出问题。这同样可按个指针，因此，必须检查次双亲结点的溢出问题。这同样可按(2)和和(3)的原则，继续检查和处理该双亲结点。的原则，继续检查和处理该双亲结点。(4) 如果按照原则如果

48、按照原则(3)，根结点，根结点q产生分裂，根结点没有双亲，那么分裂产生分裂，根结点没有双亲，那么分裂产生的产生的K m/2 作为新的根作为新的根结点结点，q和和q分别作为新的根结点的左右子树，分别作为新的根结点的左右子树，B-树高度增加树高度增加1。7.3 B-树树7.3.6 B-树的删除B-B-树删除中树删除中3 3个重要的操作：个重要的操作：(1)(1)替代替代(2)(2)删除元素和空指针删除元素和空指针 (3)(3)借或者并借或者并第第7 7章章 搜索树搜索树7.1 7.1 二叉搜索树二叉搜索树7.3 B7.3 B树树 7.3.1 m7.3.1 m叉搜索树叉搜索树 7.3.2 B-7.3

49、.2 B-树的定义树的定义 7.3.3 B-7.3.3 B-树的高度树的高度 7.3.4 B-7.3.4 B-树的搜索树的搜索 7.3.5 B-7.3.5 B-树的插入树的插入 7.3.6 B-7.3.6 B-树的删除树的删除7.3 B-树树7.3.6 B-树的删除(1) 替代替代 从从B-树上删除一个指定元素的操作同插入一样，是从树上删除一个指定元素的操作同插入一样，是从叶子结点开始。如果被删除的元素不在叶子结点中，那么叶子结点开始。如果被删除的元素不在叶子结点中，那么由它右子树上的最小元素取代之，即由大于被删除元素的由它右子树上的最小元素取代之，即由大于被删除元素的最小元素取代之。这种最小

50、元素取代之。这种“替代替代”使得删除操作成为从使得删除操作成为从B-树树的叶子结点中删除一个元素。的叶子结点中删除一个元素。3518112743 7847 53 6499图图7-23 4阶阶B-树树 例如：删除例如：删除35353939r7.3 B-树树7.3.6 B-树的删除(2) 删除元素和空指针删除元素和空指针 替代以后从替代以后从r结点中删除结点中删除39和一个空指针。删除后和一个空指针。删除后r结结点中的元素个数不足点中的元素个数不足B-树规定的下限（即至少树规定的下限（即至少 m/2 -1个元个元素），从而发生下溢。素），从而发生下溢。3918112743 7847 53 6499

51、图图7-23 4阶阶B-树树 r397.3 B-树树7.3.6 B-树的删除(3) 借借 发生下溢后，解决这一问题的做法首先检查其左、发生下溢后，解决这一问题的做法首先检查其左、右两侧的兄弟结点中的元素个数，若左侧兄弟有多余的右两侧的兄弟结点中的元素个数，若左侧兄弟有多余的元素，则从左侧兄弟元素，则从左侧兄弟“借借”一个元素；否则，若右侧兄一个元素；否则，若右侧兄弟有多余的元素，则向右侧兄弟弟有多余的元素，则向右侧兄弟“借借”一个元素。一个元素。39181127 78 53 6499图图7-23 4阶阶B-树树 r43477.3 B-树树7.3.6 B-树的删除(3) 借借 发生下溢后，解决这

52、一问题的做法首先检查其左、发生下溢后，解决这一问题的做法首先检查其左、右两侧的兄弟结点中的元素个数，若左侧兄弟有多余的右两侧的兄弟结点中的元素个数，若左侧兄弟有多余的元素，则从左侧兄弟元素，则从左侧兄弟“借借”一个元素；否则，若右侧兄一个元素；否则，若右侧兄弟有多余的元素，则向右侧兄弟弟有多余的元素，则向右侧兄弟“借借”一个元素。一个元素。39181127 78 53 6499图图7-23 4阶阶B-树树 r4347再完整看一遍！再完整看一遍！7.3 B-树树7.3.6 B-树的删除错误的错误的“借借”法一：法一： 直接将兄弟结点中的元素借过来；直接将兄弟结点中的元素借过来；39181127

53、78 53 6499r43477.3 B-树树7.3.6 B-树的删除错误的错误的“借借”法二：法二： 传递地借元素；传递地借元素；39181127 86 99r43803969787.3 B-树树7.3.6 B-树的删除39181147 7853 6499图图7-23 4阶阶B-树树 43s(4) 或者并或者并 如果一个如果一个B-树结点发生下溢时，其左、右两侧兄弟都树结点发生下溢时，其左、右两侧兄弟都恰好只有恰好只有 m/2 -1个元素，那么只能个元素，那么只能 “并并” 。27sut例如：删除例如：删除27277.3 B-树树7.3.6 B-树的删除3947 7853 6499图图7-23 4阶阶B-树树 43(4)