南京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)A第7章

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)A 第第7章章 第第7章章 搜索樹(shù)搜索樹(shù)n集合可以采用樹(shù)形結(jié)構(gòu)表示，比如，用二叉搜索樹(shù)、集合可以采用樹(shù)形結(jié)構(gòu)表示，比如，用二叉搜索樹(shù)、二叉平衡樹(shù)、二叉平衡樹(shù)、 B-樹(shù)等表示，通常稱(chēng)這些為搜索樹(shù)。搜索樹(shù)等表示，通常稱(chēng)這些為搜索樹(shù)。搜索樹(shù)有較高的搜索效率，又能有效地插入和刪除元素，因樹(shù)有較高的搜索效率，又能有效地插入和刪除元素，因而更適合表示動(dòng)態(tài)集。而更適合表示動(dòng)態(tài)集。n 本課程討論這三種常見(jiàn)的用于表示動(dòng)態(tài)集的樹(shù)形數(shù)本課程討論這三種常見(jiàn)的用于表示動(dòng)態(tài)集的樹(shù)形數(shù)據(jù)結(jié)構(gòu)：二叉搜索樹(shù)、二叉平衡樹(shù)和據(jù)結(jié)構(gòu)：二叉搜索樹(shù)、二叉平衡樹(shù)和B-樹(shù)。樹(shù)。第第7章章 搜索樹(shù)搜索樹(shù)7.1 二叉搜索樹(shù)二叉搜

2、索樹(shù)二叉搜索樹(shù)也稱(chēng)二叉二叉搜索樹(shù)也稱(chēng)二叉排序樹(shù)，是一種最容排序樹(shù)，是一種最容易實(shí)現(xiàn)的搜索樹(shù)。易實(shí)現(xiàn)的搜索樹(shù)。第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù) 7.1.1 7.1.1 二叉搜索樹(shù)的定義二叉搜索樹(shù)的定義 7.1.2 7.1.2 二叉搜索樹(shù)的搜索二叉搜索樹(shù)的搜索 7.1.3 7.1.3 二叉搜索樹(shù)的插入二叉搜索樹(shù)的插入 7.1.4 7.1.4 二叉搜索樹(shù)的刪除二叉搜索樹(shù)的刪除7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.1 二叉搜索樹(shù)的定義定義定義7.17.1 假定所有結(jié)點(diǎn)的關(guān)鍵字值各不假定所有結(jié)點(diǎn)的關(guān)鍵字值各不相同，二叉搜索樹(shù)或者是一棵空二叉樹(shù)，相同，二叉搜索樹(shù)或者是一棵空二

3、叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：或者是具有下列性質(zhì)的二叉樹(shù)：(1)(1)若左子樹(shù)不空，則左子樹(shù)上所有結(jié)若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)關(guān)鍵字值；點(diǎn)的關(guān)鍵字值均小于根結(jié)點(diǎn)關(guān)鍵字值；(2)(2)若右子樹(shù)不空，則右子樹(shù)上所有結(jié)若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)關(guān)鍵字值；點(diǎn)的關(guān)鍵字值均大于根結(jié)點(diǎn)關(guān)鍵字值；(3)(3)左、右子樹(shù)也分別是二叉搜索樹(shù)。左、右子樹(shù)也分別是二叉搜索樹(shù)。遞歸定義遞歸定義第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù) 7.1.1 7.1.1 二叉搜索樹(shù)的定義二叉搜索樹(shù)的定義 7.1.2 7.1.2 二叉搜索樹(shù)的搜索二叉搜

4、索樹(shù)的搜索 7.1.3 7.1.3 二叉搜索樹(shù)的插入二叉搜索樹(shù)的插入 7.1.4 7.1.4 二叉搜索樹(shù)的刪除二叉搜索樹(shù)的刪除7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.1 二叉搜索樹(shù)的定義性質(zhì)性質(zhì)7.1 若以若以中序遍歷中序遍歷一棵二叉搜索樹(shù)，將得到一一棵二叉搜索樹(shù)，將得到一個(gè)以關(guān)鍵字值個(gè)以關(guān)鍵字值遞增遞增排列的有序序列。排列的有序序列。6354874569762335圖圖7-1 二叉搜索樹(shù)二叉搜索樹(shù)7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.1 二叉搜索樹(shù)的定義程序程序7.1 二叉搜索樹(shù)類(lèi)二叉搜索樹(shù)類(lèi) 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 二叉搜索樹(shù)二叉搜索樹(shù)7.1.2 二叉搜索樹(shù)的搜索1.1.二叉搜索樹(shù)搜索的遞歸算法二叉搜索樹(shù)搜索的遞歸算法2.2.二叉搜索樹(shù)搜索的迭代算法二叉搜索樹(shù)搜索的迭代算法第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二

6、叉搜索樹(shù)二叉搜索樹(shù) 7.1.1 7.1.1 二叉搜索樹(shù)的定義二叉搜索樹(shù)的定義 7.1.2 7.1.2 二叉搜索樹(shù)的搜索二叉搜索樹(shù)的搜索 7.1.3 7.1.3 二叉搜索樹(shù)的插入二叉搜索樹(shù)的插入 7.1.4 7.1.4 二叉搜索樹(shù)的刪除二叉搜索樹(shù)的刪除7.3 B7.3 B樹(shù)樹(shù)7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.2 二叉搜索樹(shù)的搜索(1) (1) 若二叉樹(shù)為空，則搜索失敗。若二叉樹(shù)為空，則搜索失敗。(2) (2) 否則，將否則，將x x與根結(jié)點(diǎn)比較，與根結(jié)點(diǎn)比較，若若x x小于該結(jié)點(diǎn)的值，則以同樣的方法搜索左子樹(shù)，而小于該結(jié)點(diǎn)的值，則以同樣的方法搜索左子樹(shù)，而不必搜索右子樹(shù)；不必搜索右子樹(shù)；若若x

7、 x大于該結(jié)點(diǎn)的值，則以同樣的方法搜索右子樹(shù)，而大于該結(jié)點(diǎn)的值，則以同樣的方法搜索右子樹(shù)，而不必搜索左子樹(shù)；不必搜索左子樹(shù)；若若x x等于該結(jié)點(diǎn)的值，則搜索成功終止。等于該結(jié)點(diǎn)的值，則搜索成功終止。1. 二叉搜索樹(shù)搜索的遞歸算法二叉搜索樹(shù)搜索的遞歸算法查找與查找與x的關(guān)鍵字值相同的元素的的關(guān)鍵字值相同的元素的遞歸算法遞歸算法可描述如下：可描述如下：7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.2 二叉搜索樹(shù)的搜索程序程序7.2 二叉搜索樹(shù)搜索的遞歸算法二叉搜索樹(shù)搜索的遞歸算法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 二叉搜索樹(shù)二叉搜索樹(shù)7.1.2 二叉搜索樹(shù)的搜索2. 二叉搜索樹(shù)的迭代算法二叉搜索樹(shù)的迭代算法 二叉搜索樹(shù)的迭代算法二叉搜索樹(shù)的迭代算法使用使用w

9、hile循環(huán)，從根結(jié)點(diǎn)開(kāi)始循環(huán)，從根結(jié)點(diǎn)開(kāi)始搜索，將待查元素搜索，將待查元素x與當(dāng)前元素比較。與當(dāng)前元素比較。 若若x等于該結(jié)點(diǎn)的值，則搜索成功終止；等于該結(jié)點(diǎn)的值，則搜索成功終止； 若若x小于該結(jié)點(diǎn)的值，則繼續(xù)搜索左子樹(shù)；小于該結(jié)點(diǎn)的值，則繼續(xù)搜索左子樹(shù)； 否則繼續(xù)搜索右子樹(shù)。否則繼續(xù)搜索右子樹(shù)。只有搜索到空子樹(shù)時(shí)，才失敗終止。只有搜索到空子樹(shù)時(shí)，才失敗終止。7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.2 二叉搜索樹(shù)的搜索程序程序7.3 二叉搜索樹(shù)搜索的迭代算法二叉搜索樹(shù)搜索的迭代算法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 二叉搜索樹(shù)二叉搜索樹(shù)7.1.3 二叉搜索樹(shù)的插入二叉搜索樹(shù)的插入步驟與單鏈表的插二叉搜索樹(shù)的插入步驟與單鏈表的插入步驟類(lèi)似。入步驟類(lèi)似。(1) 查找插入元素的位置；查找插入元素的位置；(2) 生成新結(jié)點(diǎn)；生成新結(jié)點(diǎn)；(3) 插入新結(jié)點(diǎn)插入新結(jié)點(diǎn)(有可能修改有可能修改root指針指針)第第7

11、7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù) 7.1.1 7.1.1 二叉搜索樹(shù)的定義二叉搜索樹(shù)的定義 7.1.2 7.1.2 二叉搜索樹(shù)的搜索二叉搜索樹(shù)的搜索 7.1.3 7.1.3 二叉搜索樹(shù)的插入二叉搜索樹(shù)的插入 7.1.4 7.1.4 二叉搜索樹(shù)的刪除二叉搜索樹(shù)的刪除7.3 B7.3 B樹(shù)樹(shù)7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.3 二叉搜索樹(shù)的插入 在二叉搜索樹(shù)上插入一個(gè)新元素，首先應(yīng)搜索新元素的在二叉搜索樹(shù)上插入一個(gè)新元素，首先應(yīng)搜索新元素的插入位置，同時(shí)，插入位置，同時(shí)，需要需要在自根結(jié)點(diǎn)向下搜索過(guò)程中，記錄當(dāng)在自根結(jié)點(diǎn)向下搜索過(guò)程中，記錄當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)，設(shè)為前結(jié)點(diǎn)的

12、雙親結(jié)點(diǎn)，設(shè)為q。 如果二叉樹(shù)中有重復(fù)元素，應(yīng)返回如果二叉樹(shù)中有重復(fù)元素，應(yīng)返回Duplicate。 搜索到達(dá)空子樹(shù)時(shí)，構(gòu)造一個(gè)新結(jié)點(diǎn)搜索到達(dá)空子樹(shù)時(shí)，構(gòu)造一個(gè)新結(jié)點(diǎn)p存放新元素存放新元素x，并連接至結(jié)點(diǎn)并連接至結(jié)點(diǎn)q，成為，成為q的孩子（的孩子（p是是q的左孩子還是右孩的左孩子還是右孩子取決于子取決于x與與q關(guān)鍵字值的大小）；如果原二叉搜索樹(shù)是關(guān)鍵字值的大小）；如果原二叉搜索樹(shù)是空樹(shù)，則新結(jié)點(diǎn)空樹(shù)，則新結(jié)點(diǎn)p成為新二叉搜索樹(shù)的根。成為新二叉搜索樹(shù)的根。7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.3 二叉搜索樹(shù)的插入在二叉搜索樹(shù)中插入在二叉搜索樹(shù)中插入4343的執(zhí)行過(guò)程的執(zhí)行過(guò)程: :28213633

13、2543q=pq43p=p7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.3 二叉搜索樹(shù)的插入213633432528 下圖顯示了從空樹(shù)開(kāi)始通過(guò)依次插入元素，下圖顯示了從空樹(shù)開(kāi)始通過(guò)依次插入元素，構(gòu)造一棵二叉搜索樹(shù)的過(guò)程。構(gòu)造一棵二叉搜索樹(shù)的過(guò)程。(a)空樹(shù)空樹(shù)(b)插入插入28(c)插入插入21(d)插入插入25(e)插入插入36(f)插入插入33(g)插入插入437.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.3 二叉搜索樹(shù)的插入程序程序7.4 二叉搜索樹(shù)的插入運(yùn)算二叉搜索樹(shù)的插入運(yùn)算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;查找插入位置查找插入位置生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)插入新結(jié)點(diǎn)插入新結(jié)點(diǎn)7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.4 二叉搜索樹(shù)的刪除 在二叉搜索樹(shù)上刪除一個(gè)結(jié)在二叉搜

15、索樹(shù)上刪除一個(gè)結(jié)點(diǎn)與插入運(yùn)算類(lèi)似，應(yīng)先搜索被刪點(diǎn)與插入運(yùn)算類(lèi)似，應(yīng)先搜索被刪除結(jié)點(diǎn)除結(jié)點(diǎn)p，并記錄，并記錄p的雙親結(jié)點(diǎn)的雙親結(jié)點(diǎn)q。第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù) 7.1.1 7.1.1 二叉搜索樹(shù)的定義二叉搜索樹(shù)的定義 7.1.2 7.1.2 二叉搜索樹(shù)的搜索二叉搜索樹(shù)的搜索 7.1.3 7.1.3 二叉搜索樹(shù)的插入二叉搜索樹(shù)的插入 7.1.4 7.1.4 二叉搜索樹(shù)的刪除二叉搜索樹(shù)的刪除7.3 B7.3 B樹(shù)樹(shù)Hibbard Deletion, 1960 7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.4 二叉搜索樹(shù)的刪除如果不存在指定刪除的元素，應(yīng)返回如果不存在指定

16、刪除的元素，應(yīng)返回NotPresent。否則，刪除結(jié)點(diǎn)否則，刪除結(jié)點(diǎn)p的操作由下列幾步組成：的操作由下列幾步組成：(1) 若若結(jié)點(diǎn)結(jié)點(diǎn)p有兩棵非空子樹(shù)有兩棵非空子樹(shù)，需搜索結(jié)點(diǎn)，需搜索結(jié)點(diǎn)p的中序遍歷次序下的中序遍歷次序下的直接后繼結(jié)點(diǎn)，設(shè)為的直接后繼結(jié)點(diǎn)，設(shè)為s。將。將s中的值復(fù)制到中的值復(fù)制到p中，刪除中，刪除s結(jié)點(diǎn)。結(jié)點(diǎn)。如果如果s結(jié)點(diǎn)是結(jié)點(diǎn)是p的直接后繼，則的直接后繼，則s必定沒(méi)有左孩子（右孩子）。必定沒(méi)有左孩子（右孩子）。此時(shí)，問(wèn)題就簡(jiǎn)化為此時(shí)，問(wèn)題就簡(jiǎn)化為“被刪除的結(jié)點(diǎn)最多只有一棵非空子樹(shù)被刪除的結(jié)點(diǎn)最多只有一棵非空子樹(shù)”的情形。的情形。(2)若若結(jié)點(diǎn)結(jié)點(diǎn)p只有一棵非空子樹(shù)或只有一

17、棵非空子樹(shù)或p是葉子是葉子，以結(jié)點(diǎn)，以結(jié)點(diǎn)p的唯一孩子的唯一孩子（設(shè)為結(jié)點(diǎn)（設(shè)為結(jié)點(diǎn)c）或空子樹(shù)（）或空子樹(shù)（c=NULL）取代）取代p。(3)若若被刪除的結(jié)點(diǎn)被刪除的結(jié)點(diǎn)p是根結(jié)點(diǎn)是根結(jié)點(diǎn)，則刪除后，結(jié)點(diǎn)，則刪除后，結(jié)點(diǎn)c成為新的根；成為新的根；否則，若否則，若p是其雙親是其雙親q的左孩子，則結(jié)點(diǎn)的左孩子，則結(jié)點(diǎn)c也應(yīng)該成為也應(yīng)該成為q的左孩的左孩子，不然子，不然c成為成為q的右孩子。最后釋放結(jié)點(diǎn)的右孩子。最后釋放結(jié)點(diǎn)p所占的空間。所占的空間。7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.4 二叉搜索樹(shù)的刪除2833刪除刪除2128213633432523353423刪除刪除2328213633432

18、5353421刪除刪除2825364335342833二叉搜索樹(shù)二叉搜索樹(shù)上刪除元素上刪除元素7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.4 二叉搜索樹(shù)的刪除2928 下圖結(jié)合程序，演示刪除一個(gè)有左右下圖結(jié)合程序，演示刪除一個(gè)有左右孩子結(jié)點(diǎn)的過(guò)程。孩子結(jié)點(diǎn)的過(guò)程。282536433230例如刪除例如刪除2834prsq=x=29q7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.4 二叉搜索樹(shù)的刪除程序程序7.5 二叉搜索樹(shù)的刪除運(yùn)算二叉搜索樹(shù)的刪除運(yùn)算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; 搜索要?jiǎng)h除的結(jié)點(diǎn)搜索要?jiǎng)h除的結(jié)點(diǎn)28213633432523353421 qp7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.1.4 二叉搜索樹(shù)的刪除 if (p-lChild & p-rChild) s = p-rChild; r = p; while (s-lChild) /結(jié)點(diǎn)結(jié)點(diǎn)s是是p的中序后繼，的中序后繼， r = s; s = s-lChild;

20、 / r是是s的雙親的雙親 p-element = s-element; /將將s的值復(fù)制到的值復(fù)制到p中，中， p=s; q=r; /準(zhǔn)備刪除準(zhǔn)備刪除p，指針，指針q指示指示p的雙親的雙親 if (p-lChild) c = p-lChild; else c = p-rChild; /準(zhǔn)備以結(jié)點(diǎn)準(zhǔn)備以結(jié)點(diǎn)c取代結(jié)點(diǎn)取代結(jié)點(diǎn)p if(p = root) root = c; /以結(jié)點(diǎn)以結(jié)點(diǎn)c取代結(jié)點(diǎn)取代結(jié)點(diǎn)p else if (p = q-lChild) q-lChild = c; else q-rChild = c; delete p; return Success;轉(zhuǎn)化為被刪轉(zhuǎn)化為被刪除的結(jié)

21、點(diǎn)除的結(jié)點(diǎn) p 最多只有一最多只有一個(gè)孩子個(gè)孩子2821363343252335347.1 二叉搜索樹(shù)二叉搜索樹(shù)二叉搜索樹(shù)搜索算法二叉搜索樹(shù)搜索算法分析分析最好情況和一般情況：最好情況和一般情況：O(logO(log2 2n)n)最壞情況：?jiǎn)沃?shù)，最壞情況：?jiǎn)沃?shù)，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 二叉搜索樹(shù)二叉搜索樹(shù) 平均情況下，二叉搜索樹(shù)的搜索、插入和平均情況下，二叉搜索樹(shù)的搜索、插入和刪除操作的漸近時(shí)間復(fù)雜度均為刪除操作的漸近時(shí)間復(fù)雜度均為O(logO(log2 2n)n)。由關(guān)鍵字序列由關(guān)鍵字序列 3 3，1 1，2 2，5 5，4 4構(gòu)造而得的二叉排序樹(shù)構(gòu)造而得的二叉排序樹(shù)由關(guān)鍵字序列由關(guān)鍵字序列 1 1，2 2，3 3，4 4，5 5構(gòu)造而得的二叉排序樹(shù)，構(gòu)造而得的二叉排序樹(shù)，ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3

23、）/ 5 = 2.2(a)(b)21345354127.2 二叉平衡樹(shù)二叉平衡樹(shù)二叉平衡樹(shù)（二叉平衡樹(shù)（Self-Balancing Binary Self-Balancing Binary Search TreeSearch Tree），又稱(chēng)），又稱(chēng)AVLAVL樹(shù)，是一種二叉排樹(shù)，是一種二叉排序樹(shù)，其中每一個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的序樹(shù)，其中每一個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度差至多等于高度差至多等于1 1。h hL L-h-hR R =1=17.2 二叉平衡樹(shù)二叉平衡樹(shù)G.M. G.M. A Adelson-delson-V Velskii & E.M. elskii & E.M

24、. L Landis(andis(俄羅斯，俄羅斯，1962)1962)7.2 二叉平衡樹(shù)二叉平衡樹(shù)定義定義7.2 二叉平衡樹(shù)又稱(chēng)二叉平衡樹(shù)又稱(chēng)AVLAVL樹(shù)，它或者是一棵空二樹(shù)，它或者是一棵空二叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：(1)(1)其根的左、右子樹(shù)高度之差的絕對(duì)值不超過(guò)其根的左、右子樹(shù)高度之差的絕對(duì)值不超過(guò)1 1；(2)(2)其根的左、右子樹(shù)都是二叉平衡樹(shù)。其根的左、右子樹(shù)都是二叉平衡樹(shù)。n 平衡因子（平衡因子（BFBF）: : 結(jié)點(diǎn)結(jié)點(diǎn)左左子樹(shù)的高度減去子樹(shù)的高度減去右右子樹(shù)子樹(shù)的高度。的高度。7.2 二叉平衡樹(shù)二叉平衡樹(shù)(1)(1)(2)(2)(3

25、)(3)(4)(4)0 01 10 0-1-10 0BF=2BF=27.2 二叉平衡樹(shù)二叉平衡樹(shù)n 最小不平衡子樹(shù)最小不平衡子樹(shù)：距離插入結(jié)點(diǎn)最近的且平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹(shù)。n 當(dāng)插入新結(jié)點(diǎn)37時(shí)37370 0-1-11 10 00 02 2最小不平衡子樹(shù)最小不平衡子樹(shù)7.2 二叉平衡樹(shù)二叉平衡樹(shù)AVL樹(shù)實(shí)現(xiàn)原理 n實(shí)例：實(shí)例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，88二叉排序樹(shù)二叉排序樹(shù)AVLAVL樹(shù)樹(shù)7.2 二叉平衡樹(shù)二叉平衡樹(shù)AVL樹(shù)實(shí)現(xiàn)原理 n實(shí)例：實(shí)例：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右旋右旋僅對(duì)最小不平衡最小不平衡子樹(shù)子樹(shù)進(jìn)行旋轉(zhuǎn)NEXTNEXT：插入：插入4 47.2 二叉平衡樹(shù)二叉平衡樹(shù)AVL樹(shù)實(shí)現(xiàn)原理 n實(shí)例：實(shí)例：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 二叉平衡樹(shù)二叉平衡樹(shù)AVL樹(shù)實(shí)現(xiàn)原理 n

27、實(shí)例：實(shí)例：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 二叉平衡樹(shù)二叉平衡樹(shù)AVL樹(shù)實(shí)現(xiàn)原理 n實(shí)例：實(shí)例：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 二叉平衡樹(shù)二叉平衡樹(shù)AVL樹(shù)實(shí)現(xiàn)原理 n實(shí)例：實(shí)例：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 二叉平衡樹(shù)二叉平衡樹(shù)n實(shí)例：實(shí)例：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 二叉平衡樹(shù)二叉平衡樹(shù)n實(shí)例：實(shí)例：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 二叉平衡樹(shù)二叉平衡樹(shù)n實(shí)例：實(shí)例：33，2 2，1 1，4 4，5 5，6 6，7 7，1010，9 9，881.1. 確定最小不平衡子樹(shù)確定最小不平衡子樹(shù)T T；2.2. 適當(dāng)旋轉(zhuǎn)，形成適當(dāng)旋轉(zhuǎn)，形成AVLAVL樹(shù)；樹(shù)；7.2 二叉平衡樹(shù)二叉平衡樹(shù)n 二叉平衡樹(shù)的插入，其關(guān)鍵在于不平衡時(shí)的調(diào)整二叉平衡樹(shù)的插入，其關(guān)鍵在于不平衡時(shí)的調(diào)整n 調(diào)整方案主要包含兩類(lèi)：調(diào)整方案主要包含兩類(lèi)： 單旋轉(zhuǎn)調(diào)整單旋轉(zhuǎn)調(diào)整 雙旋轉(zhuǎn)調(diào)整雙旋轉(zhuǎn)調(diào)整7.2 二叉平衡樹(shù)二叉平衡樹(shù)插入插入N N前是平衡二叉樹(shù)前是平衡二叉樹(shù)插入插入N N后平衡性打破后平衡性打破插入

30、插入N N調(diào)整后恢復(fù)平衡性調(diào)整后恢復(fù)平衡性右旋右旋第第1 1類(lèi)類(lèi)單旋轉(zhuǎn)調(diào)整單旋轉(zhuǎn)調(diào)整左旋左旋類(lèi)似類(lèi)似7.2 二叉平衡樹(shù)二叉平衡樹(shù)插入插入N N前是平衡二叉樹(shù)前是平衡二叉樹(shù)插入插入N N后平衡性打破后平衡性打破插入插入N N保證根結(jié)點(diǎn)和其左孩子保證根結(jié)點(diǎn)和其左孩子BFBF符號(hào)相同符號(hào)相同第第2 2類(lèi)類(lèi)雙旋轉(zhuǎn)調(diào)整雙旋轉(zhuǎn)調(diào)整左旋左旋右旋右旋7.3 B-樹(shù)樹(shù) n內(nèi)搜索內(nèi)搜索：當(dāng)集合足夠小，可以駐：當(dāng)集合足夠小，可以駐留在內(nèi)存中時(shí)，相應(yīng)的搜索方法稱(chēng)留在內(nèi)存中時(shí)，相應(yīng)的搜索方法稱(chēng)為內(nèi)搜索。為內(nèi)搜索。n外搜索外搜索：如果文件很大，以至于：如果文件很大，以至于計(jì)算機(jī)內(nèi)存容不下時(shí)，它們必須存計(jì)算機(jī)內(nèi)存容不下時(shí)，

31、它們必須存放在外存中。在外存中搜索給定關(guān)放在外存中。在外存中搜索給定關(guān)鍵字值的元素的方法稱(chēng)為外搜索。鍵字值的元素的方法稱(chēng)為外搜索。內(nèi)存中集合用二叉平衡樹(shù)表示。外內(nèi)存中集合用二叉平衡樹(shù)表示。外存中，集合可以用存中，集合可以用B-B-樹(shù)來(lái)表示。樹(shù)來(lái)表示。第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.3 B7.3 B樹(shù)樹(shù) 7.3.1 m7.3.1 m叉搜索樹(shù)叉搜索樹(shù) 7.3.2 B-7.3.2 B-樹(shù)的定義樹(shù)的定義 7.3.3 B-7.3.3 B-樹(shù)的高度樹(shù)的高度 7.3.4 B-7.3.4 B-樹(shù)的搜索樹(shù)的搜索 7.3.5 B-7.3.5 B-樹(shù)的插入樹(shù)的插入 7.3.6 B

32、-7.3.6 B-樹(shù)的刪除樹(shù)的刪除7.3 B-樹(shù)樹(shù)7.3.1 m叉搜索樹(shù) 典型的磁盤(pán)存取時(shí)間是典型的磁盤(pán)存取時(shí)間是1ms 10ms，而典型的內(nèi)存存取時(shí)間是，而典型的內(nèi)存存取時(shí)間是10ns100ns。內(nèi)存的存取速度比磁。內(nèi)存的存取速度比磁盤(pán)快盤(pán)快1萬(wàn)至百萬(wàn)倍。萬(wàn)至百萬(wàn)倍。設(shè)法減少磁盤(pán)存取操作的次數(shù)是外設(shè)法減少磁盤(pán)存取操作的次數(shù)是外搜索算法設(shè)計(jì)應(yīng)充分考慮的問(wèn)題。搜索算法設(shè)計(jì)應(yīng)充分考慮的問(wèn)題。第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.3 B7.3 B樹(shù)樹(shù) 7.3.1 m7.3.1 m叉搜索樹(shù)叉搜索樹(shù) 7.3.2 B-7.3.2 B-樹(shù)的定義樹(shù)的定義 7.3.3 B-7.3.

33、3 B-樹(shù)的高度樹(shù)的高度 7.3.4 B-7.3.4 B-樹(shù)的搜索樹(shù)的搜索 7.3.5 B-7.3.5 B-樹(shù)的插入樹(shù)的插入 7.3.6 B-7.3.6 B-樹(shù)的刪除樹(shù)的刪除7.3 B-樹(shù)樹(shù)7.3.1 m叉搜索樹(shù) 定義定義7.3 m叉搜索樹(shù)或者是一棵空叉搜索樹(shù)或者是一棵空m叉搜索樹(shù)，或者是一棵叉搜索樹(shù)，或者是一棵滿(mǎn)足下列特性的樹(shù)。滿(mǎn)足下列特性的樹(shù)。 根結(jié)點(diǎn)最多有根結(jié)點(diǎn)最多有m棵子樹(shù)，并具有如下結(jié)構(gòu)：棵子樹(shù)，并具有如下結(jié)構(gòu)： n，P0，（，（K1，P1），（），（K2，P2），），（，（Kn，Pn） 其中，其中，Pi是指向子樹(shù)的指針，是指向子樹(shù)的指針，0i n m， Ki是關(guān)鍵字值，是關(guān)鍵字值，

34、1 i nm。 KiKi+1 , 1 in 子樹(shù)子樹(shù)Pi上的所有關(guān)鍵字值都大于上的所有關(guān)鍵字值都大于Ki，小于，小于Ki+1, 0i35，則沿著，則沿著35右邊的子樹(shù)向下搜索，并再?gòu)挠疫叺淖訕?shù)向下搜索，并再?gòu)?3和和78中間的子樹(shù)上找到中間的子樹(shù)上找到53, 搜索成功。搜索成功。 搜索搜索54，搜索失敗。，搜索失敗。5354搜索成功！搜索成功！搜索失??！搜索失??！7.3 B-樹(shù)樹(shù)7.3.1 m叉搜索樹(shù) 3. m叉搜索樹(shù)的性質(zhì)叉搜索樹(shù)的性質(zhì) 設(shè)一棵設(shè)一棵m叉搜索樹(shù)的高度為叉搜索樹(shù)的高度為h，則該樹(shù)上最多的，則該樹(shù)上最多的結(jié)點(diǎn)結(jié)點(diǎn)數(shù)數(shù)目（不包括失敗結(jié)點(diǎn)）為：目（不包括失敗結(jié)點(diǎn)）為： m叉搜索樹(shù)中，

35、每個(gè)叉搜索樹(shù)中，每個(gè)結(jié)點(diǎn)結(jié)點(diǎn)最多有最多有m-1個(gè)個(gè)元素元素，因此，因此m叉叉搜索樹(shù)中最多有搜索樹(shù)中最多有mh-1個(gè)元素。個(gè)元素。101111hihhimmmmm7.3 B-樹(shù)樹(shù)7.3.1 m叉搜索樹(shù) 3. m叉搜索樹(shù)的性質(zhì)叉搜索樹(shù)的性質(zhì) 設(shè)設(shè)N是高度為是高度為h的的m叉搜索樹(shù)中元素的個(gè)數(shù)，叉搜索樹(shù)中元素的個(gè)數(shù)，1hmN從而推出：從而推出：) 1(logNhm一棵一棵m叉搜索樹(shù)的高度在叉搜索樹(shù)的高度在logm(N+1)到到N之間。之間。7.3 B-樹(shù)樹(shù)7.3.2 B-樹(shù)的定義定義定義7.4 一棵一棵m階階B-樹(shù)是一棵樹(shù)是一棵m叉搜叉搜索樹(shù)，它或者是空索樹(shù)，它或者是空B-樹(shù)，或者是滿(mǎn)樹(shù)，或者是滿(mǎn)足

36、下列特性的樹(shù)：足下列特性的樹(shù)： 根結(jié)點(diǎn)至少有兩個(gè)孩子。根結(jié)點(diǎn)至少有兩個(gè)孩子。 除根結(jié)點(diǎn)和失敗結(jié)點(diǎn)外的所有結(jié)除根結(jié)點(diǎn)和失敗結(jié)點(diǎn)外的所有結(jié)點(diǎn)點(diǎn)至少至少有有 m/2 個(gè)孩子。個(gè)孩子。 所有失敗結(jié)點(diǎn)均在同一層上。所有失敗結(jié)點(diǎn)均在同一層上。Bayer-McCreight, 1972第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.3 B7.3 B樹(shù)樹(shù) 7.3.1 m7.3.1 m叉搜索樹(shù)叉搜索樹(shù) 7.3.2 B-7.3.2 B-樹(shù)的定義樹(shù)的定義 7.3.3 B-7.3.3 B-樹(shù)的高度樹(shù)的高度 7.3.4 B-7.3.4 B-樹(shù)的搜索樹(shù)的搜索 7.3.5 B-7.3.5 B-樹(shù)的插入樹(shù)

37、的插入 7.3.6 B-7.3.6 B-樹(shù)的刪除樹(shù)的刪除7.3 B-樹(shù)樹(shù)7.3.2 B-樹(shù)的高度從定義中可以得到，一棵從定義中可以得到，一棵4階階B-樹(shù)中樹(shù)中(1)一個(gè)結(jié)點(diǎn)最多有一個(gè)結(jié)點(diǎn)最多有4個(gè)孩子個(gè)孩子(2)除根結(jié)點(diǎn)和失敗結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)最少有除根結(jié)點(diǎn)和失敗結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)最少有 4/2 =2個(gè)孩子，個(gè)孩子， 根結(jié)點(diǎn)最少有根結(jié)點(diǎn)最少有2個(gè)孩子個(gè)孩子(3) 所有失敗結(jié)點(diǎn)均在同一層上所有失敗結(jié)點(diǎn)均在同一層上3518112743 783947 53 64994階階B-樹(shù)樹(shù) 7.3 B-樹(shù)樹(shù)7.3.3 B-樹(shù)的高度性質(zhì)性質(zhì)7.27.2 設(shè)設(shè)B-B-樹(shù)失敗結(jié)點(diǎn)的總數(shù)是樹(shù)失敗結(jié)點(diǎn)的總數(shù)是s s，一棵，一棵

38、B-B-樹(shù)包含的元素樹(shù)包含的元素總數(shù)總數(shù)N N，則有，則有: N = s : N = s 1 1證明：證明： 每個(gè)非失敗結(jié)點(diǎn)中的包含的元素?cái)?shù)目比它所包含的指針每個(gè)非失敗結(jié)點(diǎn)中的包含的元素?cái)?shù)目比它所包含的指針數(shù)少數(shù)少1。設(shè)非失敗結(jié)點(diǎn)總數(shù)為。設(shè)非失敗結(jié)點(diǎn)總數(shù)為n，則，則B-樹(shù)的元素總數(shù)樹(shù)的元素總數(shù)N等于所等于所有非失敗結(jié)點(diǎn)包含的指針總數(shù)有非失敗結(jié)點(diǎn)包含的指針總數(shù)t減去減去n，即，即N=t-n， 而指針總數(shù)而指針總數(shù)t等于除根結(jié)點(diǎn)以外，失敗結(jié)點(diǎn)數(shù)和非失敗等于除根結(jié)點(diǎn)以外，失敗結(jié)點(diǎn)數(shù)和非失敗結(jié)點(diǎn)數(shù)的總和，即結(jié)點(diǎn)數(shù)的總和，即t = n+s-1。 所以有所以有 n+s-1 = N + n ，整理得，整理得

39、N=s-1。7.3 B-樹(shù)樹(shù)7.3.3 B-樹(shù)的高度定理定理7.2 N個(gè)元素的個(gè)元素的m階階B-樹(shù)的高度樹(shù)的高度h有有)21(log12/Nhm 證明：證明： 設(shè)設(shè)m階階B-樹(shù)有樹(shù)有N個(gè)元素，則失敗結(jié)點(diǎn)的個(gè)數(shù)為個(gè)元素，則失敗結(jié)點(diǎn)的個(gè)數(shù)為N+1。 B-樹(shù)第樹(shù)第1層為根結(jié)點(diǎn)。根結(jié)點(diǎn)至少有層為根結(jié)點(diǎn)。根結(jié)點(diǎn)至少有2個(gè)孩子，所以第個(gè)孩子，所以第2層至少有層至少有2個(gè)結(jié)點(diǎn)。除根以外，每個(gè)非失敗結(jié)點(diǎn)至少有個(gè)結(jié)點(diǎn)。除根以外，每個(gè)非失敗結(jié)點(diǎn)至少有 m/2 個(gè)孩子。個(gè)孩子。，依此類(lèi)推，第，依此類(lèi)推，第h+1層至少有層至少有2( m/2 )h-1 個(gè)結(jié)個(gè)結(jié)點(diǎn)。而第點(diǎn)。而第h+1層是失敗結(jié)點(diǎn)。層是失敗結(jié)點(diǎn)。 所以有

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

41、的樹(shù)搜索需執(zhí)行的磁盤(pán)訪問(wèn)次數(shù)最多是磁盤(pán)訪問(wèn)次數(shù)最多是 1+log m/2 (N+1)/2) B-樹(shù)的每個(gè)結(jié)點(diǎn)可以看成一個(gè)有樹(shù)的每個(gè)結(jié)點(diǎn)可以看成一個(gè)有序表，在一個(gè)序表，在一個(gè)B-樹(shù)結(jié)點(diǎn)中搜索時(shí)在內(nèi)樹(shù)結(jié)點(diǎn)中搜索時(shí)在內(nèi)存中的搜索，因此可以采用順序搜索存中的搜索，因此可以采用順序搜索和二分搜索等內(nèi)搜索算法進(jìn)行。和二分搜索等內(nèi)搜索算法進(jìn)行。7.3 B-樹(shù)樹(shù)7.3.5 B-樹(shù)的插入第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.3 B7.3 B樹(shù)樹(shù) 7.3.1 m7.3.1 m叉搜索樹(shù)叉搜索樹(shù) 7.3.2 B-7.3.2 B-樹(shù)的定義樹(shù)的定義 7.3.3 B-7.3.3 B-樹(shù)的高度樹(shù)

42、的高度 7.3.4 B-7.3.4 B-樹(shù)的搜索樹(shù)的搜索 7.3.5 B-7.3.5 B-樹(shù)的插入樹(shù)的插入 7.3.6 B-7.3.6 B-樹(shù)的刪除樹(shù)的刪除 將一個(gè)元素插入將一個(gè)元素插入B-樹(shù)：樹(shù)：n 首先，搜索首先，搜索B-樹(shù)中是否包含相同關(guān)樹(shù)中是否包含相同關(guān)鍵字值的元素，若存在，則插入失敗。鍵字值的元素，若存在，則插入失敗。n 否則，搜索必定終止在失敗結(jié)點(diǎn)處，否則，搜索必定終止在失敗結(jié)點(diǎn)處，此時(shí)，將新元素插在該失敗結(jié)點(diǎn)的上此時(shí)，將新元素插在該失敗結(jié)點(diǎn)的上一層的葉子結(jié)點(diǎn)中。一層的葉子結(jié)點(diǎn)中。n 如果插入后，該葉子結(jié)點(diǎn)中包含的如果插入后，該葉子結(jié)點(diǎn)中包含的元素個(gè)數(shù)不超過(guò)元素個(gè)數(shù)不超過(guò)m-1，則

43、插入成功，則插入成功，否則，需進(jìn)行結(jié)點(diǎn)分裂。否則，需進(jìn)行結(jié)點(diǎn)分裂。7.3 B-樹(shù)樹(shù)7.3.5 B-樹(shù)的插入例例1 在圖在圖7.23的的4階階B-樹(shù)中插入新的元素樹(shù)中插入新的元素59。3518112743 783947 53 6499圖圖7-23 4階階B-樹(shù)樹(shù) 7.3 B-樹(shù)樹(shù)7.3.5 B-樹(shù)的插入例例1 在圖在圖7.23的的4階階B-樹(shù)中插入新的元素樹(shù)中插入新的元素59。步驟步驟1：搜索新元素：搜索新元素 在在B-樹(shù)中搜索元素樹(shù)中搜索元素59（搜索失敗處是圖中紅色的失敗結(jié)點(diǎn)）（搜索失敗處是圖中紅色的失敗結(jié)點(diǎn)） q是失敗結(jié)點(diǎn)的上一層葉子結(jié)點(diǎn)，是失敗結(jié)點(diǎn)的上一層葉子結(jié)點(diǎn)，r是是q的雙親結(jié)點(diǎn)。的

44、雙親結(jié)點(diǎn)。3518112743 783947 53 649959rq7.3 B-樹(shù)樹(shù)7.3.5 B-樹(shù)的插入例例1 在圖在圖7.23的的4階階B-樹(shù)中插入新的元素樹(shù)中插入新的元素59。3518112743 7839 47 53 6499rq步驟步驟2：將新元素和一個(gè)空指針插入到：將新元素和一個(gè)空指針插入到q中中 q中插入新元素和失敗結(jié)點(diǎn)后，如果中插入新元素和失敗結(jié)點(diǎn)后，如果q沒(méi)有溢出，即沒(méi)有溢出，即結(jié)點(diǎn)中包含的元素個(gè)數(shù)未超過(guò)結(jié)點(diǎn)中包含的元素個(gè)數(shù)未超過(guò)m-1（指針數(shù)沒(méi)有超過(guò)（指針數(shù)沒(méi)有超過(guò)m），），則插入運(yùn)算結(jié)束，否則進(jìn)行步驟則插入運(yùn)算結(jié)束，否則進(jìn)行步驟3分裂操作。分裂操作。5935181127

45、43 783947 53 6499rq597.3 B-樹(shù)樹(shù)7.3.5 B-樹(shù)的插入例例1 在圖在圖7.23的的4階階B-樹(shù)中插入新的元素樹(shù)中插入新的元素59。步驟步驟3：分裂：分裂 分裂發(fā)生在分裂發(fā)生在q中第中第 m/2 個(gè)元素的位置，個(gè)元素的位置，結(jié)點(diǎn)結(jié)點(diǎn)q被一分為三，被一分為三， 即即q、k m/2 和和q。 q中保存前中保存前 m/2 個(gè)元素，個(gè)元素，q中保存后中保存后 m/2 個(gè)個(gè)元素。多出的元素。多出的k m/2 和和q 一起插入其到雙親結(jié)點(diǎn)一起插入其到雙親結(jié)點(diǎn)r中。中。3518112743 783999r 47 64q59q4759 64q53537.3 B-樹(shù)樹(shù)7.3.5 B-樹(shù)

46、的插入例例2 ：在：在3階階B-樹(shù)中插入樹(shù)中插入新元素新元素537.3 B-樹(shù)樹(shù)7.3.5 B-樹(shù)的插入B樹(shù)插入新元素的方法。樹(shù)插入新元素的方法。(1) 在在B-樹(shù)中搜索給定關(guān)鍵字值的元素，如果搜索成功，插入運(yùn)算失敗樹(shù)中搜索給定關(guān)鍵字值的元素，如果搜索成功，插入運(yùn)算失敗終止，否則將新元素和一個(gè)空指針插入搜索失敗處的葉子結(jié)點(diǎn)中。終止，否則將新元素和一個(gè)空指針插入搜索失敗處的葉子結(jié)點(diǎn)中。 (2) 若插入新元素（和一個(gè)指針）后，結(jié)點(diǎn)若插入新元素（和一個(gè)指針）后，結(jié)點(diǎn)q未溢出，即結(jié)點(diǎn)中包含的未溢出，即結(jié)點(diǎn)中包含的元素個(gè)數(shù)未超過(guò)元素個(gè)數(shù)未超過(guò)m-1（指針數(shù)未超過(guò)（指針數(shù)未超過(guò)m），則插入運(yùn)算成功終止。）

47、，則插入運(yùn)算成功終止。(3) 若插入新元素（和一個(gè)指針）后，結(jié)點(diǎn)若插入新元素（和一個(gè)指針）后，結(jié)點(diǎn)q已溢出，則必須進(jìn)行結(jié)點(diǎn)已溢出，則必須進(jìn)行結(jié)點(diǎn)的分裂操作，將結(jié)點(diǎn)一分為三。分裂發(fā)生在位置的分裂操作，將結(jié)點(diǎn)一分為三。分裂發(fā)生在位置 m/2 處。將處。將 m/2 處處的元素和新結(jié)點(diǎn)插入雙親結(jié)點(diǎn)中。雙親結(jié)點(diǎn)中新增加了一個(gè)元素和一的元素和新結(jié)點(diǎn)插入雙親結(jié)點(diǎn)中。雙親結(jié)點(diǎn)中新增加了一個(gè)元素和一個(gè)指針，因此，必須檢查次雙親結(jié)點(diǎn)的溢出問(wèn)題。這同樣可按個(gè)指針，因此，必須檢查次雙親結(jié)點(diǎn)的溢出問(wèn)題。這同樣可按(2)和和(3)的原則，繼續(xù)檢查和處理該雙親結(jié)點(diǎn)。的原則，繼續(xù)檢查和處理該雙親結(jié)點(diǎn)。(4) 如果按照原則如果

48、按照原則(3)，根結(jié)點(diǎn)，根結(jié)點(diǎn)q產(chǎn)生分裂，根結(jié)點(diǎn)沒(méi)有雙親，那么分裂產(chǎn)生分裂，根結(jié)點(diǎn)沒(méi)有雙親，那么分裂產(chǎn)生的產(chǎn)生的K m/2 作為新的根作為新的根結(jié)點(diǎn)結(jié)點(diǎn)，q和和q分別作為新的根結(jié)點(diǎn)的左右子樹(shù)，分別作為新的根結(jié)點(diǎn)的左右子樹(shù)，B-樹(shù)高度增加樹(shù)高度增加1。7.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除B-B-樹(shù)刪除中樹(shù)刪除中3 3個(gè)重要的操作：個(gè)重要的操作：(1)(1)替代替代(2)(2)刪除元素和空指針刪除元素和空指針 (3)(3)借或者并借或者并第第7 7章章 搜索樹(shù)搜索樹(shù)7.1 7.1 二叉搜索樹(shù)二叉搜索樹(shù)7.3 B7.3 B樹(shù)樹(shù) 7.3.1 m7.3.1 m叉搜索樹(shù)叉搜索樹(shù) 7.3.2 B-7.3

49、.2 B-樹(shù)的定義樹(shù)的定義 7.3.3 B-7.3.3 B-樹(shù)的高度樹(shù)的高度 7.3.4 B-7.3.4 B-樹(shù)的搜索樹(shù)的搜索 7.3.5 B-7.3.5 B-樹(shù)的插入樹(shù)的插入 7.3.6 B-7.3.6 B-樹(shù)的刪除樹(shù)的刪除7.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除(1) 替代替代 從從B-樹(shù)上刪除一個(gè)指定元素的操作同插入一樣，是從樹(shù)上刪除一個(gè)指定元素的操作同插入一樣，是從葉子結(jié)點(diǎn)開(kāi)始。如果被刪除的元素不在葉子結(jié)點(diǎn)中，那么葉子結(jié)點(diǎn)開(kāi)始。如果被刪除的元素不在葉子結(jié)點(diǎn)中，那么由它右子樹(shù)上的最小元素取代之，即由大于被刪除元素的由它右子樹(shù)上的最小元素取代之，即由大于被刪除元素的最小元素取代之。這種最小

50、元素取代之。這種“替代替代”使得刪除操作成為從使得刪除操作成為從B-樹(shù)樹(shù)的葉子結(jié)點(diǎn)中刪除一個(gè)元素。的葉子結(jié)點(diǎn)中刪除一個(gè)元素。3518112743 7847 53 6499圖圖7-23 4階階B-樹(shù)樹(shù) 例如：刪除例如：刪除35353939r7.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除(2) 刪除元素和空指針刪除元素和空指針 替代以后從替代以后從r結(jié)點(diǎn)中刪除結(jié)點(diǎn)中刪除39和一個(gè)空指針。刪除后和一個(gè)空指針。刪除后r結(jié)結(jié)點(diǎn)中的元素個(gè)數(shù)不足點(diǎn)中的元素個(gè)數(shù)不足B-樹(shù)規(guī)定的下限（即至少樹(shù)規(guī)定的下限（即至少 m/2 -1個(gè)元個(gè)元素），從而發(fā)生下溢。素），從而發(fā)生下溢。3918112743 7847 53 6499

51、圖圖7-23 4階階B-樹(shù)樹(shù) r397.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除(3) 借借 發(fā)生下溢后，解決這一問(wèn)題的做法首先檢查其左、發(fā)生下溢后，解決這一問(wèn)題的做法首先檢查其左、右兩側(cè)的兄弟結(jié)點(diǎn)中的元素個(gè)數(shù)，若左側(cè)兄弟有多余的右兩側(cè)的兄弟結(jié)點(diǎn)中的元素個(gè)數(shù)，若左側(cè)兄弟有多余的元素，則從左側(cè)兄弟元素，則從左側(cè)兄弟“借借”一個(gè)元素；否則，若右側(cè)兄一個(gè)元素；否則，若右側(cè)兄弟有多余的元素，則向右側(cè)兄弟弟有多余的元素，則向右側(cè)兄弟“借借”一個(gè)元素。一個(gè)元素。39181127 78 53 6499圖圖7-23 4階階B-樹(shù)樹(shù) r43477.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除(3) 借借 發(fā)生下溢后，解決這

52、一問(wèn)題的做法首先檢查其左、發(fā)生下溢后，解決這一問(wèn)題的做法首先檢查其左、右兩側(cè)的兄弟結(jié)點(diǎn)中的元素個(gè)數(shù)，若左側(cè)兄弟有多余的右兩側(cè)的兄弟結(jié)點(diǎn)中的元素個(gè)數(shù)，若左側(cè)兄弟有多余的元素，則從左側(cè)兄弟元素，則從左側(cè)兄弟“借借”一個(gè)元素；否則，若右側(cè)兄一個(gè)元素；否則，若右側(cè)兄弟有多余的元素，則向右側(cè)兄弟弟有多余的元素，則向右側(cè)兄弟“借借”一個(gè)元素。一個(gè)元素。39181127 78 53 6499圖圖7-23 4階階B-樹(shù)樹(shù) r4347再完整看一遍！再完整看一遍！7.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除錯(cuò)誤的錯(cuò)誤的“借借”法一：法一： 直接將兄弟結(jié)點(diǎn)中的元素借過(guò)來(lái)；直接將兄弟結(jié)點(diǎn)中的元素借過(guò)來(lái)；39181127

53、78 53 6499r43477.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除錯(cuò)誤的錯(cuò)誤的“借借”法二：法二： 傳遞地借元素；傳遞地借元素；39181127 86 99r43803969787.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除39181147 7853 6499圖圖7-23 4階階B-樹(shù)樹(shù) 43s(4) 或者并或者并 如果一個(gè)如果一個(gè)B-樹(shù)結(jié)點(diǎn)發(fā)生下溢時(shí)，其左、右兩側(cè)兄弟都樹(shù)結(jié)點(diǎn)發(fā)生下溢時(shí)，其左、右兩側(cè)兄弟都恰好只有恰好只有 m/2 -1個(gè)元素，那么只能個(gè)元素，那么只能 “并并” 。27sut例如：刪除例如：刪除27277.3 B-樹(shù)樹(shù)7.3.6 B-樹(shù)的刪除3947 7853 6499圖圖7-23 4階階B-樹(shù)樹(shù) 43(4)