數(shù)據(jù)結(jié)構(gòu)課件考研輔導(dǎo)查找

1、查查 找找 主講：魯法明主講：魯法明 fm_ 上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束大大 綱綱l查找的基本概念查找的基本概念l順序查找法順序查找法l折半查找法折半查找法l補(bǔ)：二叉排序樹(shù)與平衡二叉樹(shù)補(bǔ)：二叉排序樹(shù)與平衡二叉樹(shù)lB-B-樹(shù)及其基本操作、樹(shù)及其基本操作、B+B+樹(shù)的基本概念樹(shù)的基本概念l散列散列(Hash)(Hash)表表l查找算法的分析及應(yīng)用查找算法的分析及應(yīng)用 靜態(tài)查找表靜態(tài)查找表 順序表上的操作順序表上的操作動(dòng)態(tài)查找表動(dòng)態(tài)查找表 樹(shù)表上的操作樹(shù)表上的操作哈希查找哈希查找哈希表上的操作哈希表上的操作上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束查找的基本概念查找的基本概念n查找表：用于查

2、找的同一類(lèi)型的數(shù)據(jù)元素或記錄構(gòu)成的查找表：用于查找的同一類(lèi)型的數(shù)據(jù)元素或記錄構(gòu)成的集合集合. Typedef structKeyType key;ElemType;. Typedef structKeyType key;ElemType;n查找：根據(jù)給定的值在查找表中確定一個(gè)關(guān)鍵字等于給查找：根據(jù)給定的值在查找表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素定值的記錄或數(shù)據(jù)元素. .n關(guān)鍵字：數(shù)據(jù)元素或記錄中某個(gè)數(shù)據(jù)項(xiàng)的值關(guān)鍵字：數(shù)據(jù)元素或記錄中某個(gè)數(shù)據(jù)項(xiàng)的值, ,用它可以用它可以標(biāo)識(shí)數(shù)據(jù)元素或記錄標(biāo)識(shí)數(shù)據(jù)元素或記錄. .若關(guān)鍵字能唯一標(biāo)識(shí)一個(gè)元素或若關(guān)鍵字能唯一標(biāo)識(shí)一個(gè)元素或記錄則稱其為主關(guān)鍵字

3、記錄則稱其為主關(guān)鍵字, ,否則稱其為次關(guān)鍵字。本章查否則稱其為次關(guān)鍵字。本章查找通常按主關(guān)鍵字查找，或查找不成功，或找到一個(gè)找通常按主關(guān)鍵字查找，或查找不成功，或找到一個(gè)n平均查找長(zhǎng)度平均查找長(zhǎng)度: :查找過(guò)程中關(guān)鍵字的平均比較次數(shù)查找過(guò)程中關(guān)鍵字的平均比較次數(shù). .如在如在長(zhǎng)度為長(zhǎng)度為n n的查找表上的查找表上, ,假設(shè)查找肯定成功則假設(shè)查找肯定成功則ASLASL成功成功=PiCi=PiCin靜態(tài)查找表與動(dòng)態(tài)查找：創(chuàng)建后僅查找或檢索、不允許靜態(tài)查找表與動(dòng)態(tài)查找：創(chuàng)建后僅查找或檢索、不允許插入或刪除的查找表稱為靜態(tài)查找表；允許則稱為動(dòng)態(tài)插入或刪除的查找表稱為靜態(tài)查找表；允許則稱為動(dòng)態(tài)查找表查找

4、表. .上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束1 1 靜態(tài)查找表靜態(tài)查找表l靜態(tài)查找表的存儲(chǔ)結(jié)構(gòu)選擇及其定義靜態(tài)查找表的存儲(chǔ)結(jié)構(gòu)選擇及其定義l普通表上的順序查找普通表上的順序查找(帶帶/不帶監(jiān)視哨不帶監(jiān)視哨)l有序表上的順序查找有序表上的順序查找l有序表上的折半查找有序表上的折半查找l其它其它上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束1.1 1.1 靜態(tài)查找表的存儲(chǔ)結(jié)構(gòu)靜態(tài)查找表的存儲(chǔ)結(jié)構(gòu)-靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu) 順序表順序表 -typedef * KeyType;/關(guān)鍵字類(lèi)型關(guān)鍵字類(lèi)型Typedef structKeyType key;ElemType; /元素類(lèi)型元素

5、類(lèi)型 typedef struct ElemType *elem; /空間基址空間基址, 0號(hào)留空它用號(hào)留空它用 int length; /表長(zhǎng)表長(zhǎng)SSTable /思考如何定義表、訪問(wèn)記錄和記錄關(guān)鍵字思考如何定義表、訪問(wèn)記錄和記錄關(guān)鍵字-線性表的順序存儲(chǔ)結(jié)構(gòu)定義線性表的順序存儲(chǔ)結(jié)構(gòu)定義-typedef * ElemType; typedef struct ElemType *elem; /空間基址空間基址 int length; /表長(zhǎng)表長(zhǎng) int listsize; /容量容量 Sqlist上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束1.2 1.2 普通順序表上的順序查找普通順序表上的順序查找-

6、靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)-typedef * KeyType;/關(guān)鍵字類(lèi)型關(guān)鍵字類(lèi)型Typedef structKeyType key;ElemType; /元素類(lèi)型元素類(lèi)型 typedef struct ElemType *elem; /空間基址空間基址, 0號(hào)留空它用號(hào)留空它用 int length; /表長(zhǎng)表長(zhǎng)SSTable /思考如何定義表和訪問(wèn)記錄及記錄關(guān)鍵字思考如何定義表和訪問(wèn)記錄及記錄關(guān)鍵字int Search_Seq(SSTable ST, KeyType key) /存在返下標(biāo),否返0 int i; for(i=1;iST.length)return

7、0; else return i; /每次循環(huán)都要判斷i=ST.length和是否EQ,能否合并為一個(gè)操作 ST.elem0.key=key; /監(jiān)視哨，哨兵，位置也可在最后監(jiān)視哨，哨兵，位置也可在最后 for(i=ST.length ;!EQ(ST.elemi.key, key);-i); return i;/算法復(fù)雜度均為算法復(fù)雜度均為O(n),但平均查找時(shí)間幾乎減少一半但平均查找時(shí)間幾乎減少一半上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束帶監(jiān)視哨的順序查找性能分析：帶監(jiān)視哨的順序查找性能分析：int Search_Seq(SSTable ST, KeyType key int i; ST.el

8、em0.key=key; /監(jiān)視哨，哨兵 for(i=ST.length ;!EQ(ST.elemi.key, key);-i); return i;設(shè)查找第設(shè)查找第i個(gè)元素概率為個(gè)元素概率為Pi, 找不到概率找不到概率P0,則平均查找長(zhǎng)則平均查找長(zhǎng)度度ASLSS=n*P1+(n-1)*P2+.+Pi*(n-i+1)+.+1*Pn +(n+1)*P0通常查找不成功的概率認(rèn)為很小，可認(rèn)為通常查找不成功的概率認(rèn)為很小，可認(rèn)為P0=0若查找保證成功且各元素幾率同若查找保證成功且各元素幾率同(1/n)則則ASLSS=(n+1)/2若成功與否各若成功與否各50%，且各元素被找到概率同，且各元素被找到概率

9、同(1/2n)則則ASLSS=(n+1)/4 + (n+1)/2= 3*(n+1)/4 概率越大越靠后放則概率越大越靠后放則ASL越小越小,事先不知概率可動(dòng)態(tài)調(diào)事先不知概率可動(dòng)態(tài)調(diào)整整上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束1.3 1.3 有序順序表上的順序查找有序順序表上的順序查找typedef struct ElemType *elem; /元素由小到大排列元素由小到大排列 int length;SSTableint Search_Seq(SSTable ST, KeyType key) int i; for(i=1;i=ST.length;i+) /零單元留空它用 if(EQ(ST.ele

10、mi.key, key)return i; else if(GT(ST.elemi.key, key) return -1; return -1;若查找保證成功且各元素幾率同若查找保證成功且各元素幾率同(1/n)則則ASLSS=(n+1)/2若查找可能不成功則需借助判定樹(shù)描述查找過(guò)程若查找可能不成功則需借助判定樹(shù)描述查找過(guò)程設(shè)設(shè)n條記錄條記錄,則失敗結(jié)點(diǎn)則失敗結(jié)點(diǎn)n+1個(gè)個(gè),記錄結(jié)點(diǎn)記錄結(jié)點(diǎn)n個(gè)，假設(shè)到達(dá)個(gè)，假設(shè)到達(dá)各結(jié)點(diǎn)的概率相同各結(jié)點(diǎn)的概率相同1/(2n+1)則則ASL= (1+2+n)+(1+2+n+n)/(2*n+1)20103040(-,10)(10,20)(20,30)30,40)

11、(40,+)上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束1.4 1.4 折半查找折半查找l算法思想算法思想l存儲(chǔ)結(jié)構(gòu)選擇存儲(chǔ)結(jié)構(gòu)選擇l算法實(shí)現(xiàn)算法實(shí)現(xiàn)l性能分析性能分析上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束l算法思想算法思想針對(duì)有序表而言，又稱二分查找，思路如下：針對(duì)有序表而言，又稱二分查找，思路如下： low low指向最低端記錄指向最低端記錄,high,high指向最高端記錄指向最高端記錄; ;只要區(qū)間內(nèi)只要區(qū)間內(nèi)還有元素則定位還有元素則定位midmid到中間元素，比較待查元素與中間元到中間元素，比較待查元素與中間元素素, ,若比中間元素小則查找區(qū)間縮小為左半部分若比中間元素小則查找區(qū)間縮小為左

12、半部分, ,重新查找重新查找; ;若比中間元素大則查找區(qū)間縮小為右半部分若比中間元素大則查找區(qū)間縮小為右半部分, ,重新查找；重新查找；若相等則找到并返回位置若相等則找到并返回位置midmid。 區(qū)間內(nèi)無(wú)元素時(shí)返回區(qū)間內(nèi)無(wú)元素時(shí)返回0 0如找如找6464和和100100lowhighmidlowmidhighmid上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束l存儲(chǔ)結(jié)構(gòu)選擇存儲(chǔ)結(jié)構(gòu)選擇typedef struct ElemType *elem; /空間基址空間基址,0號(hào)留空它用，數(shù)組元素有序號(hào)留空它用，數(shù)組元素有序 int length; /表長(zhǎng)表長(zhǎng)SSTablelowlow指向最低端記錄：指向最低端

13、記錄：low=1low=1highhigh指向最高端記錄指向最高端記錄;high=ST.length;high=ST.length只要區(qū)間內(nèi)還有元素只要區(qū)間內(nèi)還有元素: while(low=high): while(low=high) 則定位到中間元素則定位到中間元素:mid=(low+high)/2:mid=(low+high)/2 若待查元素比中間元素小則查找區(qū)間縮小為左半部分若待查元素比中間元素小則查找區(qū)間縮小為左半部分 if(LT(key,ST.elemmid.key)high=mid-if(LT(key,ST.elemmid.key)high=mid-1 1 若比中間元素大則查找區(qū)間

14、縮小為右半部分：若比中間元素大則查找區(qū)間縮小為右半部分： if(GT(key,ST.elemmid.key)low=mid+1if(GT(key,ST.elemmid.key)low=mid+1 若相等則找到并返回位置若相等則找到并返回位置midmid if(EQ(key,ST.elemmid.key)return mid;if(EQ(key,ST.elemmid.key)return mid;區(qū)間內(nèi)無(wú)元素時(shí)返回區(qū)間內(nèi)無(wú)元素時(shí)返回-1: -1: 循環(huán)退出時(shí)循環(huán)退出時(shí)return 0return 0上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束l折半查找實(shí)現(xiàn)：折半查找實(shí)現(xiàn)：int Search_Bin

15、( SSTable ST, KeyType key ) /low=1,high=n,只要只要low=high則比較中間元素則比較中間元素,后改后改low或或high low = 1; high = ST.length; while (low ST.elemmid.key) return biSearch(ST,mid+1,high,key); 遞歸遞歸:參考專(zhuān)題課件參考專(zhuān)題課件遞歸邊界：區(qū)間長(zhǎng)度遞歸邊界：區(qū)間長(zhǎng)度為為1即即 low=high遞歸關(guān)系：遞歸關(guān)系：lowhigh時(shí)先與待查找區(qū)間中時(shí)先與待查找區(qū)間中間元素比較，相等則間元素比較，相等則找到，比中間元素小找到，比中間元素小則到左半?yún)^(qū)間則

16、到左半?yún)^(qū)間(降階降階)遞歸查找，比中間元遞歸查找，比中間元素大則到右半?yún)^(qū)間素大則到右半?yún)^(qū)間(降降階階)查找。查找。上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束性能分析性能分析折半查找的判定樹(shù)折半查找的判定樹(shù)639142578101111 元素值元素值 查找長(zhǎng)度查找長(zhǎng)度折半查找的判定樹(shù)折半查找的判定樹(shù):比較時(shí)生成根比較時(shí)生成根,到左側(cè)區(qū)間比較時(shí)生成左孩子到左側(cè)區(qū)間比較時(shí)生成左孩子,右側(cè)比右側(cè)比較生成右孩子，如此遞歸較生成右孩子，如此遞歸折半查找判定樹(shù)特點(diǎn)：右子樹(shù)中各結(jié)點(diǎn)值比根大折半查找判定樹(shù)特點(diǎn)：右子樹(shù)中各結(jié)點(diǎn)值比根大,左子樹(shù)中各結(jié)點(diǎn)值比根左子樹(shù)中各結(jié)點(diǎn)值比根小小,子樹(shù)也如此子樹(shù)也如此.根據(jù)判定樹(shù)可如

17、下完成查找：從根結(jié)點(diǎn)開(kāi)始根據(jù)判定樹(shù)可如下完成查找：從根結(jié)點(diǎn)開(kāi)始,比當(dāng)前元素大比當(dāng)前元素大就向右、小則向左就向右、小則向左,或者找到或者找到,或者到空或者到空折半查找判定樹(shù)葉子結(jié)點(diǎn)所在層次之差最多為折半查找判定樹(shù)葉子結(jié)點(diǎn)所在層次之差最多為1,可證此類(lèi)樹(shù)深度為可證此類(lèi)樹(shù)深度為log2n+1,籍此可證查找成功時(shí)最壞查找長(zhǎng)度為籍此可證查找成功時(shí)最壞查找長(zhǎng)度為log2n+1,借助方形外部結(jié)借助方形外部結(jié)點(diǎn)可證不成功時(shí)的最大查找長(zhǎng)度也如此。平均長(zhǎng)度點(diǎn)可證不成功時(shí)的最大查找長(zhǎng)度也如此。平均長(zhǎng)度log2n+1-1,12233334444上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束性能分析性能分析平均查找長(zhǎng)度平均查找

18、長(zhǎng)度最壞查找長(zhǎng)度為最壞查找長(zhǎng)度為log2n+1,復(fù)雜度復(fù)雜度O(log2n)當(dāng)判定樹(shù)為滿二叉樹(shù)時(shí)當(dāng)判定樹(shù)為滿二叉樹(shù)時(shí)(n=2h-1),若查找成功且各元素幾率同若查找成功且各元素幾率同(1/n)則則ASLbs=(1*20+2*21+3*22+h*2h-1)/nlog2(n+1)-1對(duì)具體例子要會(huì)求查找成功和不成功的平均查找長(zhǎng)度對(duì)具體例子要會(huì)求查找成功和不成功的平均查找長(zhǎng)度5個(gè)關(guān)鍵字，如個(gè)關(guān)鍵字，如A B C D ECADBEDBACFEG7個(gè)關(guān)鍵字，如個(gè)關(guān)鍵字，如A B C D E F G上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束1.51.5其它：靜態(tài)查找表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作其它：靜態(tài)查找表的鏈?zhǔn)?/p>

19、存儲(chǔ)結(jié)構(gòu)及操作typedef * KeyType;/關(guān)鍵字類(lèi)型關(guān)鍵字類(lèi)型Typedef structKeyType key;ElemType; /元素類(lèi)型元素類(lèi)型typedef struct LNode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct LNode * next; /指針域指針域LNode,*LinkList;Typedef LinkList SSTable;int Search_Seq(SSTable ST, KeyType key) LNode *p=ST-next; while(p!=NULL&!EQ(p-data.key, key) /注意技巧注意技巧

20、 p=p-next; /不可寫(xiě)成不可寫(xiě)成p+ return P;說(shuō)明說(shuō)明:平均比較次數(shù)與順序存儲(chǔ)結(jié)構(gòu)上的相應(yīng)算法同，折半不適用平均比較次數(shù)與順序存儲(chǔ)結(jié)構(gòu)上的相應(yīng)算法同，折半不適用上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束題目說(shuō)明：題目說(shuō)明：l計(jì)算普通順序表上順序查找、有序順序表上計(jì)算普通順序表上順序查找、有序順序表上順序查找和折半查找的平均查找長(zhǎng)度。順序查找和折半查找的平均查找長(zhǎng)度。l前兩個(gè)理解過(guò)程，最后一個(gè)在給定表長(zhǎng)時(shí)會(huì)前兩個(gè)理解過(guò)程，最后一個(gè)在給定表長(zhǎng)時(shí)會(huì)求，未給定時(shí)理解最壞查找長(zhǎng)度、復(fù)雜度，求，未給定時(shí)理解最壞查找長(zhǎng)度、復(fù)雜度，記住平均查找長(zhǎng)度。可結(jié)合實(shí)例驗(yàn)證記住平均查找長(zhǎng)度?？山Y(jié)合實(shí)例驗(yàn)證

21、l算法設(shè)計(jì)算法設(shè)計(jì)l設(shè)計(jì)高效查找算法，如設(shè)計(jì)高效查找算法，如0909年考題年考題l遞歸關(guān)鍵找邊界條件和遞歸關(guān)系，遞歸關(guān)系遞歸關(guān)鍵找邊界條件和遞歸關(guān)系，遞歸關(guān)系不明顯可考慮降階、分治、回溯不明顯可考慮降階、分治、回溯上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2 2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表l存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)l二叉排序樹(shù)二叉排序樹(shù)l平衡二叉樹(shù)平衡二叉樹(shù)lB B樹(shù)與基本操作樹(shù)與基本操作lB+B+樹(shù)的基本概念樹(shù)的基本概念上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.1 2.1 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)l為方便增刪需用鏈?zhǔn)酱鎯?chǔ)，但單鏈表查找效為方便增刪需用鏈?zhǔn)酱鎯?chǔ)，但單鏈表查找效率太低，希望類(lèi)似折半查找的判

22、定樹(shù)，左子率太低，希望類(lèi)似折半查找的判定樹(shù)，左子樹(shù)均比根小，右子樹(shù)均比根大，子樹(shù)內(nèi)部也樹(shù)均比根小，右子樹(shù)均比根大，子樹(shù)內(nèi)部也滿足這一規(guī)律，如此比較一次即可將查找范滿足這一規(guī)律，如此比較一次即可將查找范圍縮小到一個(gè)子樹(shù)上圍縮小到一個(gè)子樹(shù)上-二叉排序樹(shù)二叉排序樹(shù)l二叉排序樹(shù)整體越矮則查找效率越高，類(lèi)似二叉排序樹(shù)整體越矮則查找效率越高，類(lèi)似折半查找的判定樹(shù)，同樣結(jié)點(diǎn)個(gè)數(shù)的二叉樹(shù)折半查找的判定樹(shù)，同樣結(jié)點(diǎn)個(gè)數(shù)的二叉樹(shù)何時(shí)最矮何時(shí)最矮-二叉平衡樹(shù)二叉平衡樹(shù)(類(lèi)滿二叉樹(shù)類(lèi)滿二叉樹(shù))l若能將二叉排序樹(shù)推廣為三叉、四叉則整體若能將二叉排序樹(shù)推廣為三叉、四叉則整體高度會(huì)更矮，查找效果更好高度會(huì)更矮，查找效果更好

23、上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束（1）若左子樹(shù)不空，則左子樹(shù)所有結(jié)點(diǎn)的）若左子樹(shù)不空，則左子樹(shù)所有結(jié)點(diǎn)的值均嚴(yán)格小于根結(jié)點(diǎn)的值；值均嚴(yán)格小于根結(jié)點(diǎn)的值； 二叉排序樹(shù)或者是一棵空樹(shù)；或者是具二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)：有如下特性的二叉樹(shù)：（3）左、右子樹(shù)也都分別是二叉排序樹(shù)。）左、右子樹(shù)也都分別是二叉排序樹(shù)。（2）若右子樹(shù)不空，則右子樹(shù)上）若右子樹(shù)不空，則右子樹(shù)上 所有結(jié)點(diǎn)所有結(jié)點(diǎn)的值均嚴(yán)格大于根結(jié)點(diǎn)的值；的值均嚴(yán)格大于根結(jié)點(diǎn)的值；2.2 2.2 二叉排序樹(shù)（二叉查找樹(shù)）二叉排序樹(shù)（二叉查找樹(shù)）折半查找的判定樹(shù)是二叉排序樹(shù)，特殊的二叉排序樹(shù)折半查找的判定樹(shù)是二叉排

24、序樹(shù)，特殊的二叉排序樹(shù)上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束503080209010854035252388例如例如:是二叉排序樹(shù)。是二叉排序樹(shù)。66不不上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束 1）若根結(jié)點(diǎn)的關(guān)鍵字等于給定值則查找成功）若根結(jié)點(diǎn)的關(guān)鍵字等于給定值則查找成功,返根返根 2）若給定值小于根結(jié)點(diǎn)關(guān)鍵字則遞歸找左子樹(shù)并返回）若給定值小于根結(jié)點(diǎn)關(guān)鍵字則遞歸找左子樹(shù)并返回查找結(jié)果查找結(jié)果 3）若給定值大于根結(jié)點(diǎn)關(guān)鍵字則遞歸找右子樹(shù)并返回）若給定值大于根結(jié)點(diǎn)關(guān)鍵字則遞歸找右子樹(shù)并返回查找結(jié)果查找結(jié)果 若二叉排序樹(shù)為空，則查找不成功；否則若二叉排序樹(shù)為空，則查找不成功；否則:2.2.12.2.

25、1二叉排序樹(shù)（二叉查找樹(shù)）的查找二叉排序樹(shù)（二叉查找樹(shù)）的查找BiTree SearchBST(BiTree T,KeyType key) if(!T) return NULL; else if(EQ(key,T-data.key)return T; else if(LT(key,T-data.key)return(SearchBST(T-lchild,key); else return(SearchBST(T-rchild,key);上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束50308020908540358832查找關(guān)鍵字查找關(guān)鍵字= 50 ,505035 ,503040355090 ,508

26、09095l非遞歸思路：非遞歸思路：p最初指向根結(jié)點(diǎn)，只要最初指向根結(jié)點(diǎn)，只要p不空且不空且p所指結(jié)點(diǎn)不是所求則根據(jù)比較結(jié)果令所指結(jié)點(diǎn)不是所求則根據(jù)比較結(jié)果令p變?yōu)楫?dāng)前結(jié)變?yōu)楫?dāng)前結(jié)點(diǎn)的左孩子或右孩子。如此重復(fù)則最終點(diǎn)的左孩子或右孩子。如此重復(fù)則最終p空或者找空或者找到到上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束二叉排序樹(shù)查找的非遞歸實(shí)現(xiàn)二叉排序樹(shù)查找的非遞歸實(shí)現(xiàn)l思路：思路：p最初指向根結(jié)點(diǎn)，只要最初指向根結(jié)點(diǎn)，只要p不空且不空且p所指結(jié)所指結(jié)點(diǎn)不是所求則根據(jù)比較結(jié)果令點(diǎn)不是所求則根據(jù)比較結(jié)果令p變?yōu)楫?dāng)前結(jié)點(diǎn)的左變?yōu)楫?dāng)前結(jié)點(diǎn)的左孩子或右孩子。如此重復(fù)則最終孩子或右孩子。如此重復(fù)則最終p空或者找到空

27、或者找到BiTNode *Search(BiTree T, KeyType key) BiTNode *p=T; while(p!=null&!EQ(key,p-data.key) if(LT(key,p-data.key)p=p-lchild; elsep=p-rchild; return p;上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.2.2 2.2.2 二叉排序樹(shù)結(jié)點(diǎn)的插入二叉排序樹(shù)結(jié)點(diǎn)的插入2010252320102325上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束查找定位子函數(shù)查找定位子函數(shù)非遞歸非遞歸l思路思路:p最初指向根結(jié)點(diǎn)最初指向根結(jié)點(diǎn),只要只要p不空且不空且p所指結(jié)點(diǎn)非所所

28、指結(jié)點(diǎn)非所求則根據(jù)比較結(jié)果令求則根據(jù)比較結(jié)果令p變?yōu)楫?dāng)前結(jié)點(diǎn)的左孩子或右孩變?yōu)楫?dāng)前結(jié)點(diǎn)的左孩子或右孩子。如此重復(fù)則最終子。如此重復(fù)則最終p空或者找到。找到返回空或者找到。找到返回TRUE，否則返回否則返回FALSE。同時(shí)設(shè)引用型參數(shù)。同時(shí)設(shè)引用型參數(shù)f帶回帶回“父節(jié)點(diǎn)父節(jié)點(diǎn)”BiTNode *SearchBST(BiTree T, KeyType key,BiTNode * &f) BiTNode *p=T; f=NULL; while(p!=null&!EQ(key,p-data.key) f=p; if(LT(key,p-data.key)p=p-lchild; elsep

29、=p-rchild; return p;上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束插入算法：插入算法：Status InsertBST(BiTree &T,ElemType e ) BiTNode *p,*f,*s; p=SearchBST( T, e.key, f ); if (p!=NULL) return FALSE; else s=(BiTree)malloc(sizeof(BiTNode); if(s=NULL) return FALSE; s-data=e;s-lchild=NULL;s-rchild=NULL; if(f=NULL) T=s; /原樹(shù)為空原樹(shù)為空 else i

30、f( LT(e.key,p-data.key) )p-lchild=s; else p-rchild=s; return TRUE; /插入成功插入成功 上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束20102523查找定位查找定位-遞歸函數(shù)遞歸函數(shù)上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束if (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) )elsereturn SearchBST (T-lchild, key, T, p ); / 在左子樹(shù)中繼續(xù)查找在左子樹(shù)中繼續(xù)查找return SearchBST (T-rchil

31、d, key, T, p ); / 在右子樹(shù)中繼續(xù)查找在右子樹(shù)中繼續(xù)查找上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束30201040352523fTfTfT22pfTfTTTTfffp48上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束插入算法插入算法基于遞歸查找定位基于遞歸查找定位Status Insert BST(BiTree &T,ElemType e ) if (!SearchBST ( T, e.key, NULL, p ) s=(BiTree)malloc(sizeof(BiTNode); s-data=e;s-lchild=NULL;s-rchild=NULL; if(!p) T=s;

32、/未找到插入位置未找到插入位置,意味著原樹(shù)空意味著原樹(shù)空 else if( LT(e.key,p-data.key) )p-lchild=s; else p-rchild=s; return TRUE; /插入成功插入成功 else return FALSE;/原樹(shù)中存在元素關(guān)鍵字與原樹(shù)中存在元素關(guān)鍵字與e等等上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束說(shuō)明：說(shuō)明：l看書(shū)做題及時(shí)鞏固所講知識(shí)點(diǎn)看書(shū)做題及時(shí)鞏固所講知識(shí)點(diǎn)l不明白的問(wèn)題或題目發(fā)不明白的問(wèn)題或題目發(fā)fm_，屆時(shí)統(tǒng)一，屆時(shí)統(tǒng)一講解講解l如何有效查找單鏈表中倒數(shù)第如何有效查找單鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束回

33、顧：回顧：l查找的基本概念查找的基本概念l靜態(tài)查找表靜態(tài)查找表l順序查找法（哨順序查找法（哨 有序表）有序表）l折半查找法（有序順序表折半查找法（有序順序表 判定樹(shù)）判定樹(shù)）l動(dòng)態(tài)查找表動(dòng)態(tài)查找表l存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)l二叉排序樹(shù)：定義二叉排序樹(shù)：定義+ +查找查找+ +插入插入+ +刪除刪除l平衡二叉樹(shù)平衡二叉樹(shù)lB B樹(shù)與基本操作樹(shù)與基本操作lB+B+樹(shù)的基本概念樹(shù)的基本概念l哈希查找哈希查找上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.2.3 2.2.3 二叉排序樹(shù)結(jié)點(diǎn)的刪除二叉排序樹(shù)結(jié)點(diǎn)的刪除Status DeleteBST(BiTree &T,KeyType key) /找到

34、關(guān)鍵字為找到關(guān)鍵字為key元素則刪除并返回刪除結(jié)果元素則刪除并返回刪除結(jié)果,否則返回否則返回FALSE if(!T)return FALSE; else if( EQ(key,T-data.key) return( delete(T) ); else if(LT(key,T-data.key) return DeleteBST(T-lchild, key); else return( DeleteBST(T-rchild,key) ); 如刪除如刪除23,由由T為引用型知最后執(zhí)行實(shí)為為引用型知最后執(zhí)行實(shí)為delete(T-rchild-lchild)最終執(zhí)行最終執(zhí)行Delete(T)時(shí)時(shí)T是是

35、T-rchild-lchild的別名的別名,即雙親左指針即雙親左指針,刪刪除函數(shù)設(shè)計(jì)為除函數(shù)設(shè)計(jì)為delete(BiTree &p)，則，則p也是也是T-rchild-lchild，通過(guò)，通過(guò)p即可操作雙親指針即可操作雙親指針, 對(duì)于上例只需令對(duì)于上例只需令p=NULL即可。但若即可。但若p左右子樹(shù)左右子樹(shù)不空需認(rèn)真考慮以保證刪除后仍然是二叉排序樹(shù)不空需認(rèn)真考慮以保證刪除后仍然是二叉排序樹(shù)20102523上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束50308020908540358832被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空空”if

36、(!p-lchild&!p-rchild)p=NULL;p是是T-rchild-rchild-lchild-rchild的的別名別名,是是88雙親的右指針雙親的右指針,隱含雙親信息隱含雙親信息,不必再定位雙親不必再定位雙親上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束50308020908540358832雙親結(jié)點(diǎn)的相應(yīng)指針域指向被刪結(jié)點(diǎn)的唯一子樹(shù)雙親結(jié)點(diǎn)的相應(yīng)指針域指向被刪結(jié)點(diǎn)的唯一子樹(shù)被刪關(guān)鍵字被刪關(guān)鍵字 = 4080if(!p-lchild)BiTree q=p;p=p-rchild;free(q);/刪除刪除80時(shí)時(shí)p是是T-rchild的別名的別名,相當(dāng)雙親的孩子指針相當(dāng)雙親的孩子指

37、針, 而而q則是另一個(gè)則是另一個(gè)普通指針變量普通指針變量,雖然也指向雖然也指向80,但但q改變不影響改變不影響80的雙親指針的雙親指針上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束5030802090854035883245設(shè)設(shè)p指向刪除結(jié)點(diǎn)指向刪除結(jié)點(diǎn),找找p左子樹(shù)中最大結(jié)點(diǎn)左子樹(shù)中最大結(jié)點(diǎn)s”取代取代”p，分兩種情況：，分兩種情況：(1)p的左孩子存在右子樹(shù)的左孩子存在右子樹(shù),此時(shí)最大結(jié)點(diǎn)此時(shí)最大結(jié)點(diǎn)s必位于該右子樹(shù)必位于該右子樹(shù),且且s必為右必為右上方第一個(gè)右孩子為空的結(jié)點(diǎn)。設(shè)置輔助指針上方第一個(gè)右孩子為空的結(jié)點(diǎn)。設(shè)置輔助指針q指向指向s的雙親，則的雙親，則s=p-lchild-rchild;

38、q=p-lchild;while(s-rchild) q=s; s=s-rchild; p-data=s-data; q-rchild=s-lchild; (2) p的左孩子不存在右子樹(shù)的左孩子不存在右子樹(shù),此時(shí)此時(shí)p-lchild最大最大,故故 s=p-lchild; p-data=s-data; p-lchild=s-lchild; free(s);被刪關(guān)鍵字被刪關(guān)鍵字 = 504542上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束Status Delete(&p)/從二叉排序樹(shù)中刪除結(jié)點(diǎn)從二叉排序樹(shù)中刪除結(jié)點(diǎn)p,并重接其左右子樹(shù)并重接其左右子樹(shù).p含雙親信息含雙親信息if(!p-rchi

39、ld) /包含包含p為葉子結(jié)點(diǎn)的情況為葉子結(jié)點(diǎn)的情況 q=p; p=p-lchild; free(q); /刪除刪除p結(jié)點(diǎn)，注意結(jié)點(diǎn)，注意p與與q不同不同 else if(!p-lchild) q=p; p=p-rchild; free(q);/q為普通指針為普通指針,p是雙親指針別是雙親指針別名名else/結(jié)點(diǎn)結(jié)點(diǎn)p左右子樹(shù)均不空左右子樹(shù)均不空,書(shū)中是下述兩種情況合并書(shū)中是下述兩種情況合并,會(huì)分析會(huì)分析 if(!p-lchild-rchild)/p的左孩子無(wú)右子樹(shù)時(shí)的左孩子無(wú)右子樹(shù)時(shí),p左孩子最大左孩子最大 s=p-lchild; p-data=s-data; /用用s取代取代p p-lch

40、ild=s-lchild; free(s);s=NULL; else /p的左孩子有右子樹(shù)的左孩子有右子樹(shù),最大元素是該右子樹(shù)中第一個(gè)無(wú)最大元素是該右子樹(shù)中第一個(gè)無(wú)/右孩子的結(jié)點(diǎn)右孩子的結(jié)點(diǎn) s=p-lchild-rchild; q=p-lchild; while(s-rchild) q=s; s=s-rchild; p-data=s-data; q-rchild=s-lchild;free(s);s=NULL; /此算法是按前面思路得到，教材在此基礎(chǔ)上進(jìn)行了此算法是按前面思路得到，教材在此基礎(chǔ)上進(jìn)行了“整理整理”上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束關(guān)鍵字輸入序列關(guān)鍵字輸入序列 3，1，2，

41、5，4：關(guān)鍵字輸入序列：關(guān)鍵字輸入序列： 1，2，3，4，5：21345354122.2.42.2.4二叉排序樹(shù)查找性能分析二叉排序樹(shù)查找性能分析( (假設(shè)查找成假設(shè)查找成功功) )平均：1ASL2log=O(log )nnCnn 二叉排序樹(shù)中序遍歷序列必嚴(yán)格遞增二叉排序樹(shù)中序遍歷序列必嚴(yán)格遞增;若中序遞增則必二叉排序樹(shù)若中序遞增則必二叉排序樹(shù)總體深度越小越好，最好情況下類(lèi)似折半查找的判定樹(shù)，任意結(jié)總體深度越小越好，最好情況下類(lèi)似折半查找的判定樹(shù)，任意結(jié)點(diǎn)的左右子樹(shù)深度之差絕對(duì)值不超過(guò)點(diǎn)的左右子樹(shù)深度之差絕對(duì)值不超過(guò)1.平衡二叉樹(shù)平衡二叉樹(shù):任意結(jié)點(diǎn)左右子樹(shù)深度差任意結(jié)點(diǎn)左右子樹(shù)深度差(平衡因

42、子平衡因子)絕對(duì)值不超過(guò)絕對(duì)值不超過(guò)1上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.3 2.3 平衡二叉樹(shù)平衡二叉樹(shù)(BBT(BBT或或AVLAVL樹(shù)或樹(shù)或Height Height Balanced Tree)Balanced Tree) 樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)深度之差樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)深度之差(平平衡因子衡因子)為為0 1 或或-1 。1RLhh52815281-1是二叉平衡樹(shù)，是二叉平衡樹(shù)，同時(shí)是二叉排序樹(shù)同時(shí)是二叉排序樹(shù) 是二叉排序樹(shù)是二叉排序樹(shù)不是平衡二叉樹(shù)不是平衡二叉樹(shù)“最小不平衡二叉樹(shù)最小不平衡二叉樹(shù)”440上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束u平衡的二叉排序樹(shù)的構(gòu)造平衡的

43、二叉排序樹(shù)的構(gòu)造l思路：按二叉排序樹(shù)進(jìn)行構(gòu)造，每插入思路：按二叉排序樹(shù)進(jìn)行構(gòu)造，每插入一個(gè)結(jié)點(diǎn)，檢查該結(jié)點(diǎn)是否導(dǎo)致不平衡。一個(gè)結(jié)點(diǎn)，檢查該結(jié)點(diǎn)是否導(dǎo)致不平衡。若導(dǎo)致不平衡則找若導(dǎo)致不平衡則找“最小不平衡樹(shù)最小不平衡樹(shù)”，通過(guò)旋轉(zhuǎn)使該最小的不平衡樹(shù)平衡即可。通過(guò)旋轉(zhuǎn)使該最小的不平衡樹(shù)平衡即可。l旋轉(zhuǎn)原則：第一保證平衡性；第二保證旋轉(zhuǎn)原則：第一保證平衡性；第二保證是二叉排序樹(shù)是二叉排序樹(shù)l例：例：13 24 37 90 53 95 10 5 40 上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束RR型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的右孩子的右子樹(shù)中插型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的右孩子的右子樹(shù)中插入新結(jié)點(diǎn)導(dǎo)致失

44、衡。入新結(jié)點(diǎn)導(dǎo)致失衡。abBCAhabBCAh例：例：13 24 37 90 53 95 10 5 40上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束RL型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的右孩子的左子樹(shù)上插入新結(jié)點(diǎn)導(dǎo)致失衡。型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的右孩子的左子樹(shù)上插入新結(jié)點(diǎn)導(dǎo)致失衡。abCDABhcabCDABhcacDCbAB例：例：13 24 37 90 53 95 10 5 40上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束RR型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的右孩子的右子樹(shù)中插入新結(jié)點(diǎn)導(dǎo)致失衡。型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的右孩子的右子樹(shù)中插入新結(jié)點(diǎn)導(dǎo)致失衡。abBCAhabBCAh例：例：13 24

45、37 90 53 95 10 5 40上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束LL型：在最小不平衡二叉樹(shù)根節(jié)點(diǎn)的左孩子的左子樹(shù)上插入新結(jié)點(diǎn)導(dǎo)致失衡。型：在最小不平衡二叉樹(shù)根節(jié)點(diǎn)的左孩子的左子樹(shù)上插入新結(jié)點(diǎn)導(dǎo)致失衡。abBCAhabBCAh例：例：13 24 37 90 53 95 10 5 40上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束LR型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的左孩子的右子樹(shù)上插入新結(jié)點(diǎn)導(dǎo)致失衡。型：在最小不平衡二叉樹(shù)根結(jié)點(diǎn)的左孩子的右子樹(shù)上插入新結(jié)點(diǎn)導(dǎo)致失衡。abCDABhcabCDABhc例：例：13 24 37 90 53 95 10 5 40上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束作業(yè)

46、作業(yè)1：45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 87454532453216453216453216779445321677944532167794384532167794384532167794384445321677943844214532167794384421394532167794384421394532167794384421396845321677943844213968334532167794384421396833453216779438442139683387453216779438442139683387上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)

47、節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.4 B-2.4 B-樹(shù)及其基本操作樹(shù)及其基本操作l概念：可看作平衡二叉排序樹(shù)的推廣，是一概念：可看作平衡二叉排序樹(shù)的推廣，是一種種“平衡平衡”的的“多路多路”“”“查找查找”樹(shù)，如下例樹(shù)，如下例是一個(gè)是一個(gè)4階階B-樹(shù)樹(shù)(階數(shù)由結(jié)點(diǎn)的最大子樹(shù)個(gè)數(shù)階數(shù)由結(jié)點(diǎn)的最大子樹(shù)個(gè)數(shù)決定決定) root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.4.1 B-2.4.1 B-樹(shù)形式化定義樹(shù)形式化定義l一顆一顆m階的階的B樹(shù)是空樹(shù)，或是滿足下列特性的樹(shù)是空樹(shù)，或是滿足下列特性的m

48、叉樹(shù)：叉樹(shù)：l(1)樹(shù)中每個(gè)結(jié)點(diǎn)至多有樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)棵子樹(shù)(m-1個(gè)關(guān)鍵字個(gè)關(guān)鍵字)l(2)若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)則至少有兩棵子樹(shù)若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)則至少有兩棵子樹(shù)l(3)根之外所有非終端結(jié)點(diǎn)至少有根之外所有非終端結(jié)點(diǎn)至少有ceil(m/2)棵子樹(shù)棵子樹(shù)l(4) 非終端結(jié)點(diǎn)包含信息非終端結(jié)點(diǎn)包含信息(n, A0,K1,A1,K1,A2,.,Kn ,An)lKi為關(guān)鍵字為關(guān)鍵字,有序有序; Ai為指向子樹(shù)根結(jié)點(diǎn)的指針為指向子樹(shù)根結(jié)點(diǎn)的指針,且且Ai所指所指子樹(shù)中所有結(jié)點(diǎn)關(guān)鍵字均介于子樹(shù)中所有結(jié)點(diǎn)關(guān)鍵字均介于Ki-1和和Ki之間之間.l(5)葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上葉子結(jié)點(diǎn)都出現(xiàn)在同

49、一層次上,不帶信息，相當(dāng)于查不帶信息，相當(dāng)于查找失敗結(jié)點(diǎn)找失敗結(jié)點(diǎn) root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.4.2 B-2.4.2 B-樹(shù)上的查找樹(shù)上的查找l類(lèi)似二叉排序樹(shù)的查找，是一個(gè)順指針查找結(jié)點(diǎn)和類(lèi)似二叉排序樹(shù)的查找，是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過(guò)程在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過(guò)程l查找操作包括在查找操作包括在B樹(shù)中找結(jié)點(diǎn)和在結(jié)點(diǎn)中找關(guān)鍵字，樹(shù)中找結(jié)點(diǎn)和在結(jié)點(diǎn)中找關(guān)鍵字，前者在磁盤(pán)上進(jìn)行前者在磁盤(pán)上進(jìn)行,后者在內(nèi)存中進(jìn)行后者在內(nèi)存中

50、進(jìn)行, 在磁盤(pán)上進(jìn)在磁盤(pán)上進(jìn)行查找的次數(shù)或者說(shuō)待查關(guān)鍵字所在結(jié)點(diǎn)在行查找的次數(shù)或者說(shuō)待查關(guān)鍵字所在結(jié)點(diǎn)在B-樹(shù)上樹(shù)上的層次是決定查找效率的首要因素的層次是決定查找效率的首要因素,故提高路數(shù)可改故提高路數(shù)可改善查找效率。設(shè)含善查找效率。設(shè)含N個(gè)關(guān)鍵字則讀盤(pán)次數(shù)不超過(guò)個(gè)關(guān)鍵字則讀盤(pán)次數(shù)不超過(guò)1+log（m/2,(n+1)/2），詳見(jiàn)），詳見(jiàn)P240 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.4.3 B-2.4.3 B-樹(shù)結(jié)點(diǎn)的插入樹(shù)結(jié)點(diǎn)的插入l類(lèi)似二叉排序樹(shù)的插入，首先查找，若

51、查找成功則類(lèi)似二叉排序樹(shù)的插入，首先查找，若查找成功則不能插入，否則應(yīng)試圖插入到查找路徑中最后一個(gè)不能插入，否則應(yīng)試圖插入到查找路徑中最后一個(gè)內(nèi)部結(jié)點(diǎn)上。但每個(gè)內(nèi)部結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)必須在內(nèi)部結(jié)點(diǎn)上。但每個(gè)內(nèi)部結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)必須在Ceil(m/2-1)和和m-1之間，若插入后超出上界之間，若插入后超出上界m-1則需則需要進(jìn)行要進(jìn)行“分裂分裂”l分裂分裂:選中間關(guān)鍵字上移選中間關(guān)鍵字上移,當(dāng)前結(jié)點(diǎn)分成兩個(gè)當(dāng)前結(jié)點(diǎn)分成兩個(gè),下層相下層相應(yīng)分；若上移導(dǎo)致雙親關(guān)鍵字個(gè)數(shù)超界則繼續(xù)上應(yīng)分；若上移導(dǎo)致雙親關(guān)鍵字個(gè)數(shù)超界則繼續(xù)上移移.P242圖圖9.16 root 50 15 71 84 3 8 20 26 4

52、3 56 62 78 89 96FFFF FFFFFFFFFF F上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.4.4 B-2.4.4 B-樹(shù)結(jié)點(diǎn)的刪除樹(shù)結(jié)點(diǎn)的刪除l先找到關(guān)鍵字所在結(jié)點(diǎn)，若結(jié)點(diǎn)不是最下層的非終端結(jié)點(diǎn)，設(shè)先找到關(guān)鍵字所在結(jié)點(diǎn)，若結(jié)點(diǎn)不是最下層的非終端結(jié)點(diǎn)，設(shè)關(guān)鍵字為關(guān)鍵字為Ki,則應(yīng)用則應(yīng)用Ai所指向子樹(shù)中的最小關(guān)鍵字所指向子樹(shù)中的最小關(guān)鍵字x代替代替Ki,然后然后在在x所在結(jié)點(diǎn)所在結(jié)點(diǎn)(必為最下層非終端結(jié)點(diǎn)必為最下層非終端結(jié)點(diǎn))上刪除上刪除x。問(wèn)題歸結(jié)為在。問(wèn)題歸結(jié)為在最下層的非終端結(jié)點(diǎn)上刪除關(guān)鍵字最下層的非終端結(jié)點(diǎn)上刪除關(guān)鍵字l(1)若刪除后最下層非終端結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)仍然不超

53、出下界若刪除后最下層非終端結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)仍然不超出下界Ceil(m/2)-1則直接刪除則直接刪除l(2)若刪除前關(guān)鍵字個(gè)數(shù)為若刪除前關(guān)鍵字個(gè)數(shù)為Ceil(m/2)-1，且該結(jié)點(diǎn)左，且該結(jié)點(diǎn)左/右兄弟關(guān)鍵右兄弟關(guān)鍵字個(gè)數(shù)未達(dá)下界，則將雙親左字個(gè)數(shù)未達(dá)下界，則將雙親左/右側(cè)關(guān)鍵字下移、左右側(cè)關(guān)鍵字下移、左/右兄弟右右兄弟右/左端關(guān)鍵字上移即可左端關(guān)鍵字上移即可l(3)若所在結(jié)點(diǎn)及其左右兄弟結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)均達(dá)下界則雙親左若所在結(jié)點(diǎn)及其左右兄弟結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)均達(dá)下界則雙親左/右右側(cè)關(guān)鍵字下移并與左側(cè)關(guān)鍵字下移并與左/右兄弟合并；若下移后雙親結(jié)點(diǎn)不滿足要右兄弟合并；若下移后雙親結(jié)點(diǎn)不滿足要求則上層重復(fù)該過(guò)

54、程。如動(dòng)畫(huà)或求則上層重復(fù)該過(guò)程。如動(dòng)畫(huà)或P245-F9.17 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96FFFF FFFFFFFFFF F上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束2.5 B+2.5 B+樹(shù)的基本概念樹(shù)的基本概念 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqm階階B+樹(shù)：可看作多層索引表。關(guān)鍵字及記錄的位置信息全部包樹(shù)：可看作多層索引表。關(guān)鍵字及記錄的位置信息全部包含在葉結(jié)點(diǎn)中，每個(gè)結(jié)點(diǎn)至多包含含在葉結(jié)點(diǎn)中，每個(gè)結(jié)點(diǎn)至多包含m個(gè)子樹(shù)，葉結(jié)點(diǎn)內(nèi)與葉結(jié)點(diǎn)個(gè)子樹(shù)，葉結(jié)點(diǎn)

55、內(nèi)與葉結(jié)點(diǎn)間關(guān)鍵字均有序，均在最下層且依關(guān)鍵字順序鏈接成一個(gè)鏈表。間關(guān)鍵字均有序，均在最下層且依關(guān)鍵字順序鏈接成一個(gè)鏈表。上層結(jié)點(diǎn)是對(duì)葉結(jié)點(diǎn)最大上層結(jié)點(diǎn)是對(duì)葉結(jié)點(diǎn)最大/小值的提取。其余同小值的提取。其余同B樹(shù)的定義樹(shù)的定義與與B-樹(shù)區(qū)別：結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)與子樹(shù)數(shù)同樹(shù)區(qū)別：結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)與子樹(shù)數(shù)同 關(guān)鍵字信息均在葉中關(guān)鍵字信息均在葉中 存在葉結(jié)點(diǎn)鏈表存在葉結(jié)點(diǎn)鏈表 上層結(jié)點(diǎn)關(guān)鍵字信息是冗余上層結(jié)點(diǎn)關(guān)鍵字信息是冗余上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束pB+B+樹(shù)的查找樹(shù)的查找l順序查找和按樹(shù)順序查找和按樹(shù)(隨機(jī)隨機(jī))查找兩種查找兩種l順序查找類(lèi)似有序順序表上的普通查找順序查找類(lèi)似有序順序表上的普通查找

56、,折半不可用折半不可用l隨機(jī)查找即使在中間找到也不停止隨機(jī)查找即使在中間找到也不停止,必須走到葉結(jié)點(diǎn)必須走到葉結(jié)點(diǎn) 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sq上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束作作 業(yè)業(yè)l作業(yè)作業(yè)1：按如下插入順序構(gòu)造平衡二叉樹(shù)：按如下插入順序構(gòu)造平衡二叉樹(shù)： 45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 87l作業(yè)作業(yè)2：從空樹(shù)開(kāi)始，按以下次序向：從空樹(shù)開(kāi)始，按以下次序向3階階B-樹(shù)中插入關(guān)鍵碼：樹(shù)中插入關(guān)鍵碼：20，30，50，52，60，68，70。先

57、畫(huà)出創(chuàng)建后形成的。先畫(huà)出創(chuàng)建后形成的B-樹(shù)，樹(shù)，之后刪除之后刪除50，68，畫(huà)出最終的，畫(huà)出最終的B-樹(shù)樹(shù)上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束 一、什么是哈希表？二、哈希函數(shù)的構(gòu)造方法二、哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法 四、哈希表的查找及性能分析四、哈希表的查找及性能分析上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束前述查找表的各種存儲(chǔ)結(jié)構(gòu)前述查找表的各種存儲(chǔ)結(jié)構(gòu), ,無(wú)法根據(jù)所查找關(guān)鍵字計(jì)無(wú)法根據(jù)所查找關(guān)鍵字計(jì)算元素位置，因記錄在表中的位置和它的關(guān)鍵字取值算元素位置，因記錄在表中的位置和它的關(guān)鍵字取值無(wú)任何關(guān)系。通過(guò)比較進(jìn)行查找，至少比較無(wú)任何關(guān)系。通過(guò)比較進(jìn)行查找，至少比較1 1次次,

58、, 查找查找長(zhǎng)度均不為零長(zhǎng)度均不為零 對(duì)于頻繁使用的查找表希望對(duì)于頻繁使用的查找表希望ASLASL接近接近0 0，如何做到？，如何做到？上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束例如：為每年固定招收的例如：為每年固定招收的1000 名新生建名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，關(guān)鍵立一張查找表，其關(guān)鍵字為學(xué)號(hào)，關(guān)鍵字取值范圍為字取值范圍為2005000 2005999存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu):以下標(biāo)為以下標(biāo)為000 999 的順序表表示該查找的順序表表示該查找表表,i號(hào)元素對(duì)應(yīng)學(xué)號(hào)為號(hào)元素對(duì)應(yīng)學(xué)號(hào)為2005i的學(xué)生信息的學(xué)生信息查找方案：直接根據(jù)查找方案：直接根據(jù)key值后三位便可定位相應(yīng)元值后三位便可定

59、位相應(yīng)元素素,無(wú)需比較無(wú)需比較. Hash函數(shù)函數(shù):從關(guān)鍵字到存儲(chǔ)地址之間的映像函數(shù)，從關(guān)鍵字到存儲(chǔ)地址之間的映像函數(shù)，如上例如上例 H(key)=key-2005000或或H(key)=key MOD 1000上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束沖突沖突:不同的關(guān)鍵字可能得到統(tǒng)一哈希地址的現(xiàn)象。若可不同的關(guān)鍵字可能得到統(tǒng)一哈希地址的現(xiàn)象。若可能出現(xiàn)沖突則應(yīng)制定相應(yīng)的沖突處理方法，如將同余的記能出現(xiàn)沖突則應(yīng)制定相應(yīng)的沖突處理方法，如將同余的記錄組成一個(gè)鏈表錄組成一個(gè)鏈表Hash函數(shù)函數(shù):H(key)=key MOD100根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法,將

60、一組關(guān)鍵字將一組關(guān)鍵字映象到一組有限的連續(xù)的存儲(chǔ)空間上，以關(guān)鍵字對(duì)應(yīng)的映象到一組有限的連續(xù)的存儲(chǔ)空間上，以關(guān)鍵字對(duì)應(yīng)的Hash函數(shù)值作存儲(chǔ)地址，如此所得表稱為哈希表。函數(shù)值作存儲(chǔ)地址，如此所得表稱為哈希表。映像過(guò)程稱為哈希造表或散列映像過(guò)程稱為哈希造表或散列,存儲(chǔ)地址稱為哈希地址存儲(chǔ)地址稱為哈希地址或散列地址?；蛏⒘械刂?。關(guān)鍵是構(gòu)造合適的關(guān)鍵是構(gòu)造合適的Hash函數(shù)和找合適的沖突處理方法函數(shù)和找合適的沖突處理方法上頁(yè)上頁(yè) 下頁(yè)下頁(yè)節(jié)節(jié)末頁(yè)末頁(yè)結(jié)束結(jié)束 對(duì)數(shù)值型的關(guān)鍵字常見(jiàn)構(gòu)造方法有：對(duì)數(shù)值型的關(guān)鍵字常見(jiàn)構(gòu)造方法有：若非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理若非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余數(shù)法除留