數(shù)據(jù)結(jié)構(gòu)第九章

數(shù)據(jù)結(jié)構(gòu)第九章1第一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三主要討論的問(wèn)題：靜態(tài)查找;動(dòng)態(tài)查找;哈希查找..幾個(gè)基本概念.查找表:由同一類型的數(shù)據(jù)元素構(gòu)成的集合..靜態(tài)查找表:若只在查找表中搜索某一特定的數(shù)據(jù)元素是否存在,這類搜索過(guò)程稱之為靜態(tài)查找..動(dòng)態(tài)查找表:若在查找表中搜索時(shí)插入了不存在的數(shù)據(jù)元素或刪除了已存在的數(shù)據(jù)元素,這類搜索過(guò)程稱之為動(dòng)態(tài)查找表.第二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.關(guān)鍵字:是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值,它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素..查找:根據(jù)給定的某個(gè)值,在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素..查找成功:若表中存在這樣的記錄,稱查找是成功的..查找不成功:若表中不存在關(guān)鍵字等于給定值的記錄,稱查找不成功.3第三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三§9.1靜態(tài)查找表.順序表的查找的定義--又稱線性查找,主要用于在線性結(jié)構(gòu)中進(jìn)行搜索..順序查找的思想--從表的一端開始,用給定值k與表中各個(gè)結(jié)點(diǎn)的鍵值逐個(gè)比較.1)查找成功---找出相等k值；2)查找失敗---已到達(dá)表的另一端(可在此設(shè)置一個(gè)監(jiān)視哨，作為下標(biāo)越界的條件),即表中所有結(jié)點(diǎn)的鍵值都不等于k.4第四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.監(jiān)視哨的作用:作為越界(即已查完)的檢測(cè)條件,省去在循環(huán)中每次均要判定是否越界,從而節(jié)省比較的時(shí)間..順序查找算法：intsxcz(JDr[],intn,intk){inti=n;/*從表尾開始向前查找*/r[0].key=k;/*設(shè)置監(jiān)視哨*/while(r[i].key!=k)i--;return(i);}5第五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.平均查找長(zhǎng)度(在等概率的前提下)（n+1）/2.--平均查找長(zhǎng)度ASL..如何衡量順序查找的性能？.順序查找的特點(diǎn)：1)算法簡(jiǎn)單,對(duì)線性表的邏輯次序無(wú)要求(即不必按關(guān)鍵字值不增或不減的次序排列)；2)存儲(chǔ)結(jié)構(gòu)可采用順序或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均可,但其平均查找長(zhǎng)度較大((n+1)/2).6第六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.思想:先確定待查找記錄所在的范圍,然后逐步縮小范圍,直到找到或確認(rèn)找不到該記錄為止..二分查找.適用條件:必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行..算法實(shí)現(xiàn)7第七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.思想:先確定待查找記錄所在的范圍,然后逐步縮小范圍,直到找到或確認(rèn)找不到該記錄為止..二分查找.適用條件:必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行..算法實(shí)現(xiàn).設(shè)表長(zhǎng)為n,low,high和mid分別指向待查元素所在區(qū)間的上界,下界和中點(diǎn),k為給定值..初始時(shí),令low=1,high=n,mid=(low+high)/2（只舍不入）.讓k與mid指向的記錄比較1)若k==r[mid].key,查找成功(k等于中間項(xiàng)的值)2)若k<r[mid].key,則high=mid-1(k小于中間值,在表的前半部分查找)3)若k>r[mid].key,則low=mid+1(k大于中間值,在表的后半部分查找).重復(fù)上述操作,直至low>high時(shí),查找失敗.8第八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三例:在查找表(08,14,23,37,46,55,68,79,91)查找23和79的過(guò)程..二分查找的示例.二分查找的算法描述折半查找的c語(yǔ)言算法程序：intSearch_Bin(SSTableST[],intn,intkey){intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(ST[mid].key==key)return(mid);/*查找成功*/elseif(key<ST[mid].key)high=mid-1;/*在前半?yún)^(qū)間繼續(xù)查找*/elselow=mid+1;/*在后半?yún)^(qū)間繼續(xù)查找*/}return(0);/*查找不成功*/}9第九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.設(shè)有一有序表(-1,0,1,3,4,6,8,10,12),以二分查找來(lái)構(gòu)造出它的二叉判定樹..從有序表構(gòu)造出二叉查找樹(二叉判定樹)10第十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.若設(shè)n=2h-1,則描述二分查找的二叉查找樹是高度為h-1的滿二叉樹.2h=n+1,h=log2(n+1)..第1層結(jié)點(diǎn)有1個(gè),搜索第1層結(jié)點(diǎn)要比較1次;第2層結(jié)點(diǎn)有2個(gè),搜索第2層結(jié)點(diǎn)要比較2次;…,第i(0

i

h)層結(jié)點(diǎn)有2i個(gè),搜索第i層結(jié)點(diǎn)要比較i+1次,….假定每個(gè)結(jié)點(diǎn)的搜索概率相等,即pi

=1/n,則搜索成功的平均搜索長(zhǎng)度為:.二分查找的性能分析11第十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.可以用歸納法證明.于是,可得.特點(diǎn):比順序查找方法效率高.最壞的情況下,需要比較log2n+1次,即時(shí)間復(fù)雜度為O(log2n).12第十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.分塊查找(索引順序查找).是順序查找的一種改進(jìn)方法,就是把被查找的表分成若干塊,每塊中記錄的存放順序是無(wú)序的,但塊與塊之間必須按關(guān)鍵字有序.即第一塊中任一記錄的關(guān)鍵字都小于第二塊中任一記錄的關(guān)鍵字,而第二塊中任一記錄的關(guān)鍵字都小于第三塊中任一記錄的關(guān)鍵字,依此類推..思想:該法要為被查找的表建立一個(gè)索引表,索引表中的一項(xiàng)對(duì)應(yīng)于表中的一塊,索引表中含有這一塊中的最大關(guān)鍵字和指向塊內(nèi)第一個(gè)記錄位置的指針,索引表中各項(xiàng)關(guān)鍵字有序.13第十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三索引表20538916111812852051362229538960726676塊中的最大關(guān)鍵字塊內(nèi)第一個(gè)記錄位置的指針?lè)謮K查找分兩步進(jìn)行:先查索引表(索引表表長(zhǎng)較短用順序查找,較長(zhǎng)可用折半查找)確定紀(jì)錄在哪一塊.然后在相應(yīng)的塊中查找.例,查找12,由索引表的第一項(xiàng)知,紀(jì)錄要么在第一塊中,要么不存在,由此取到第一塊中第一個(gè)紀(jì)錄位置.接著在第一塊中進(jìn)行順序查找.分塊查找效率高于順序查找,但低于折半查找.14第十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三§9.2動(dòng)態(tài)查找表.回憶:動(dòng)態(tài)查找表的特點(diǎn)..二叉排序樹(二叉搜索樹)

二叉排序樹或者是一棵空樹,或者是具有下列性質(zhì)的二叉樹:

每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同.

左子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼.

右子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼.

左子樹和右子樹也是二叉排序樹.的定義15第十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.幾個(gè)二叉排序樹的例子.由此,可得到二叉排序樹的作用:查找.二叉排序樹上的查找---在二叉搜索樹上進(jìn)行搜索,是一個(gè)從根結(jié)點(diǎn)開始,沿某一個(gè)分支逐層向下進(jìn)行比較判等的過(guò)程..二叉排序樹上的查找可以是一個(gè)遞歸過(guò)程,也可以是一個(gè)迭代過(guò)程.16第十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.二叉排序樹是的搜索示例.88插入到哪個(gè)地方?.每次結(jié)點(diǎn)的插入,都要從根結(jié)點(diǎn)出發(fā)搜索插入位置,然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入.17第十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.二叉排序樹上的插入---為了向二叉搜索樹中插入一個(gè)新元素,必須先檢查這個(gè)元素是否在樹中已經(jīng)存在..在插入之前,先使用搜索算法在樹中檢查要插入元素有還是沒有.搜索成功:樹中已有這個(gè)元素,不再插入.

搜索不成功:樹中原來(lái)沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn),把新元素加到搜索操作停止的地方.例:輸入數(shù)據(jù)序列{53,78,65,17,87,09,81,45,23},寫出建立二叉排序樹的過(guò)程.18第十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.為了引入二叉排序樹上的刪除,先簡(jiǎn)單討論下面這個(gè)問(wèn)題..同樣3個(gè)數(shù)據(jù){1,2,3},輸入順序不同,建立起來(lái)的二叉搜索樹的形態(tài)也不同.這直接影響到二叉搜索樹的搜索性能.如果輸入序列選得不好,會(huì)建立起一棵單支樹,使得二叉搜索樹的高度達(dá)到最大,這樣必然會(huì)降低搜索性能.123111132223323直觀上的結(jié)論,二叉排序樹的高度不能太高.19第十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.二叉排序樹上的刪除---在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí),必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來(lái),同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去..為保證在執(zhí)行刪除后,樹的搜索性能不至于降低,還需要防止重新鏈接后樹的高度增加.1)刪除葉結(jié)點(diǎn),只需將其雙親結(jié)點(diǎn)指向它的指針清零,再釋放它即可.2)被刪結(jié)點(diǎn)缺右子樹,可以拿它的左子女結(jié)點(diǎn)頂替它的位置,再釋放它.3)被刪結(jié)點(diǎn)缺左子樹,可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它.20第二十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三4)被刪結(jié)點(diǎn)左,右子樹都存在,可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中,再來(lái)處理這個(gè)結(jié)點(diǎn)的刪除問(wèn)題.21第二十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.二叉排序樹上的查找性能分析.二叉排序樹上的查找與折半查找類似..但,折半查找長(zhǎng)度為n的表的判定樹惟一..顯然,n個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長(zhǎng)度與樹的二叉樹的形態(tài)有關(guān).想想,最好情況與最壞情況各是什么樣?.結(jié)論:在隨機(jī)情況下,二叉排序樹的平均查找長(zhǎng)度是對(duì)數(shù)級(jí).但這種情況出現(xiàn)的概率小于50%..結(jié)論:在構(gòu)建二叉排序樹的過(guò)程中要進(jìn)行”平衡化”處理.22第二十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.平衡二叉樹(AVL樹).AVL樹的定義.一棵AVL樹或者是空樹,或者是具有下列性質(zhì)的二叉搜索樹:它的左子樹和右子樹都是AVL樹,且左子樹和右子樹的高度之差的絕對(duì)值不超過(guò)1.(a)(b)23第二十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.結(jié)點(diǎn)的平衡因子.每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字,給出該結(jié)點(diǎn)右(左)子樹的高度減去左(右)子樹的高度所得的高度差.這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balance..如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1,則這棵二叉搜索樹就失去了平衡,不再是AVL樹.任何一個(gè)結(jié)點(diǎn)的平衡因子有幾個(gè)取值?.一棵AVL樹的高度保持在什么級(jí)別?.高度可保持在O(log2n).24第二十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.平衡化處理.平衡化旋轉(zhuǎn)有兩類：

單旋轉(zhuǎn)(左旋和右旋)雙旋轉(zhuǎn)(左平衡和右平衡).每插入一個(gè)新結(jié)點(diǎn)時(shí),AVL樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變.因此,在插入一個(gè)新結(jié)點(diǎn)后,需要從插入位置沿通向根的路徑回溯,檢查各結(jié)點(diǎn)的平衡因子(左,右子樹的高度差).如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡,停止回溯.25第二十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.從發(fā)生不平衡的結(jié)點(diǎn)起,沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn).如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化.單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn),其中一個(gè)是另一個(gè)的鏡像,其方向與不平衡的形狀相關(guān).如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化.雙旋轉(zhuǎn)分為先左后右和先右后左兩類.右單旋轉(zhuǎn)左單旋轉(zhuǎn)左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)26第二十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.AVL樹的插入例:輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15},寫出插入和調(diào)整過(guò)程.0-1-201161631630701左右雙旋731600731101-2右單旋371690001371126916110112227第二十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三181803163-101602右左雙旋739000182611-1732616119-1左單旋97161400171126269111128第二十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三1518231816-2左右雙旋73000117149-1161501112626141-29例:以{30,35,39,15,10,28,16,29,17}為例建AVL樹.29第二十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.動(dòng)態(tài)的m路搜索樹.二叉搜索樹適合于組織在內(nèi)存中的較小的索引(或目錄),對(duì)于存放在外存中的較大的文件系統(tǒng),用二叉搜索樹來(lái)組織索引不太合適..在文件檢索系統(tǒng)中大量使用的是用B-(B)樹或B+樹做文件索引..當(dāng)數(shù)據(jù)對(duì)象數(shù)目特別大,索引表本身也很大,在內(nèi)存中放不下,需要分批多次讀取外存才能把索引表搜索一遍.30第三十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.在此情況下,可以建立索引的索引,稱為二級(jí)索引.二級(jí)索引可以常駐內(nèi)存,二級(jí)索引中一個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)索引塊,登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲(chǔ)地址..如果二級(jí)索引在內(nèi)存中也放不下,需要分為許多塊多次從外存讀入.可以建立二級(jí)索引的索引，叫做三級(jí)索引.這時(shí),訪問(wèn)外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對(duì)象..必要的話,還可以有4級(jí)索引,5極索引,….多級(jí)索引結(jié)構(gòu)形成一種m叉樹.31第三十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.樹中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊,它最多存放m個(gè)索引項(xiàng),每個(gè)索引項(xiàng)分別給出各子樹結(jié)點(diǎn)(低一級(jí)索引塊)的最大關(guān)鍵碼和結(jié)點(diǎn)地址..樹的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的對(duì)象的關(guān)鍵碼和存放地址.這種m叉樹用來(lái)作為多級(jí)索引,就是m路搜索樹..m路搜索樹可能是靜態(tài)索引結(jié)構(gòu),即結(jié)構(gòu)在初始創(chuàng)建,數(shù)據(jù)裝入時(shí)就已經(jīng)定型,在整個(gè)運(yùn)行期間,樹的結(jié)構(gòu)不發(fā)生變化..m路搜索樹還可能是動(dòng)態(tài)索引結(jié)構(gòu),即在整個(gè)系統(tǒng)運(yùn)行期間,樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整,以保持最佳的搜索效率.32第三十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三多級(jí)索引結(jié)構(gòu)形成m路搜索樹33第三十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.動(dòng)態(tài)的m路搜索樹.一般定義為:.一棵m路搜索樹,它或者是一棵空樹,或者是滿足如下性質(zhì)的樹：根最多有m棵子樹,并具有如下的結(jié)構(gòu)：n,P0,(K1,P1),(K2,P2),……,(Kn,Pn)其中，Pi是指向子樹的指針,0i

n<m;Ki是關(guān)鍵碼,1

i

n<m.Ki<Ki+1,1

i<n..在子樹Pi中所有的關(guān)鍵碼都小于

Ki+1，且大于

Ki,0<i<n..在子樹Pn中所有的關(guān)鍵碼都大于Kn..在子樹P0中的所有關(guān)鍵碼都小于

K1..子樹Pi也是m路搜索樹,0

i

n.34第三十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.一棵3路搜索樹的示例.AVL樹是m=?路搜索樹?35第三十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.B-樹.一棵m階B_樹是一棵m路搜索樹,它或者是空樹,或者是滿足下列性質(zhì)的樹:.根結(jié)點(diǎn)至少有2個(gè)子女..除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)(不包括失敗結(jié)點(diǎn))至少有m/2個(gè)子女..所有的失敗結(jié)點(diǎn)都位于同一層..事實(shí)上,在B-樹的每個(gè)結(jié)點(diǎn)中還包含有一組指針D[m],指向?qū)嶋H對(duì)象的存放地址.K[i]與D[i](1in<m)形成一個(gè)索引項(xiàng)(K[i],D[i]).通過(guò)K[i]可找到某個(gè)對(duì)象的存儲(chǔ)地址D[i].36第三十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.非B-樹與B-樹的示例圖非B-樹B-樹.B-樹上的搜索37第三十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.B-樹的搜索過(guò)程是一個(gè)在結(jié)點(diǎn)內(nèi)搜索和循某一條路徑向下一層搜索交替進(jìn)行的過(guò)程.因此,B-樹的搜索時(shí)間與B-樹的階數(shù)m和B-樹的高度h直接有關(guān),必須加以權(quán)衡..在B-樹上進(jìn)行搜索,搜索成功所需的時(shí)間取決于關(guān)鍵碼所在的層次,搜索不成功所需的時(shí)間取決于樹的高度..在B-樹上搜索的示例38第三十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.B-樹上的插入.B-樹是從空樹起,逐個(gè)插入關(guān)鍵碼而生成的..在B-樹,每個(gè)非失敗結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)都在

[m/2-1,m-1]之間..插入在某個(gè)葉結(jié)點(diǎn)開始.如果在關(guān)鍵碼插入后結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)超出了上界m-1,則結(jié)點(diǎn)需要“分裂”,否則可以直接插入..實(shí)現(xiàn)“分裂”的原則39第三十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.設(shè)結(jié)點(diǎn)p中已經(jīng)有m-1個(gè)關(guān)鍵碼,當(dāng)再插入一個(gè)關(guān)鍵碼后結(jié)點(diǎn)中的狀態(tài)為:.(m,P0,K1,P1,K2,P2,……,Km,Pm)

其中Ki

<Ki+1,1

i<m這時(shí)必須把結(jié)點(diǎn)p分裂成兩個(gè)結(jié)點(diǎn)p和q,它們包含的信息分別為：

結(jié)點(diǎn)p：(m/2-1,P0,K1,P1,……,Km/2-1,Pm/2-1)

結(jié)點(diǎn)q：

(m-m/2,Pm/2,Km/2+1,Pm/2+1,……,Km,Pm)位于中間的關(guān)鍵碼Km/2與指向新結(jié)點(diǎn)q的指針形成一個(gè)二元組(Km/2,q),插入到這兩個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)中去.40第四十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三結(jié)點(diǎn)“分裂”的示例41第四十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.B-樹上的插入示例:從空樹開始逐個(gè)加入關(guān)鍵碼53,75,139,49,145,36,101建立3階B-樹.42第四十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.若設(shè)B-樹的高度為h.那么在自頂向下搜索到葉結(jié)點(diǎn)的過(guò)程中需要進(jìn)行h次讀盤..在插入新關(guān)鍵碼時(shí),需要自底向上分裂結(jié)點(diǎn),最壞情況下從被插關(guān)鍵碼所在葉結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都要分裂.43第四十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三.B-樹上的刪除.在B-樹上刪除一個(gè)關(guān)鍵碼時(shí),首先需要找到這個(gè)關(guān)鍵碼所在的結(jié)點(diǎn),從中刪去這個(gè)關(guān)鍵碼..若該結(jié)點(diǎn)不是葉結(jié)點(diǎn),且被刪關(guān)鍵碼為Ki,1

i

n,則在刪去該關(guān)鍵碼之后,應(yīng)以該結(jié)點(diǎn)Pi所指示子樹中的最小關(guān)鍵碼x來(lái)代替被刪關(guān)鍵碼Ki

所在的位置,然后在x所在的葉結(jié)點(diǎn)中刪除x..在葉結(jié)點(diǎn)上刪除有4種情況:1)被刪關(guān)鍵碼所在葉結(jié)點(diǎn)同時(shí)又是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)n

2,則直接刪去該關(guān)鍵碼并將修改后的結(jié)點(diǎn)寫回磁盤.44第四十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三2)被刪關(guān)鍵碼所在葉結(jié)點(diǎn)不是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)n

m/2,則直接刪去該關(guān)鍵碼并將修改后的結(jié)點(diǎn)寫回磁盤,刪除結(jié)束.45第四十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三3)被刪關(guān)鍵碼所在葉結(jié)點(diǎn)刪除前關(guān)鍵碼個(gè)數(shù)n=m/2-1,若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)n

m/2，則可按以下步驟調(diào)整該結(jié)點(diǎn),右兄弟(或左兄弟)結(jié)點(diǎn)以及其雙親結(jié)點(diǎn),以達(dá)到新的平衡。.將雙親結(jié)點(diǎn)中剛剛大于(或小于)該被刪關(guān)鍵碼的關(guān)鍵碼Ki

(1i

n)下移；.將右兄弟(或左兄弟)結(jié)點(diǎn)中的最小(或最大)關(guān)鍵碼上