數(shù)據(jù)結(jié)構(gòu)課件：第10章 查找

第九章

查找數(shù)據(jù)結(jié)構(gòu)一、查找表(SearchTable)2第一節(jié)查找的概念查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合對(duì)查找表的操作:1.查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；2.檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；3.在查找表中插入一個(gè)數(shù)據(jù)元素；4.從查找表中刪去某個(gè)數(shù)據(jù)元素第10章查找一、查找表(分類)3第一節(jié)查找的概念靜態(tài)查找表僅作查詢和檢索操作的查找表。動(dòng)態(tài)查找表在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素第10章查找二、關(guān)鍵字(Key)4第一節(jié)查找的概念關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）主關(guān)鍵字：可以識(shí)別唯一的一個(gè)記錄的關(guān)鍵字次關(guān)鍵字：能識(shí)別若干記錄的關(guān)鍵字第10章查找三、查找(Searching)5第一節(jié)查找的概念查找是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。查找成功：在查找表中查找到指定的記錄查找不成功：在查找表中沒有找到指定記錄第10章查找四、衡量查找算法的標(biāo)準(zhǔn)6第一節(jié)查找的概念時(shí)間復(fù)雜度空間復(fù)雜度平均查找長(zhǎng)度ASL第10章查找五、平均查找長(zhǎng)度(ASL)7第一節(jié)查找的概念平均查找長(zhǎng)度定義為確定記錄在表中的位置所進(jìn)行的和關(guān)鍵字比較的次數(shù)的平均值nASL=∑PiCii=1n為查找表的長(zhǎng)度，即表中所含元素的個(gè)數(shù)Pi為查找第i個(gè)元素的概率(∑Pi=1)Ci是查找第i個(gè)元素時(shí)同給定值K比較的次數(shù)第10章查找一、順序查找8第二節(jié)靜態(tài)查找表順序查找算法是順序表的查找方法在順序查找算法中，以順序表或線性鏈表表示靜態(tài)查找表第10章查找一、順序查找(算法)9第二節(jié)靜態(tài)查找表順序查找算法：1.從表中最后一個(gè)記錄開始2.逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較3.若某個(gè)記錄比較相等，則查找成功4.若直到第1個(gè)記錄都比較不等，則查找不成功第10章查找一、順序查找(算法實(shí)現(xiàn))第二節(jié)靜態(tài)查找表int

Search_Seq(SSTableST,KeyTypekey){ //若查找成功，返回位置 ST.elem[0].key=key; //“哨兵”，

for(i=ST.length;ST.elem[i].key!=key;--i); //從后往前找 returni; //找不到時(shí),i=0}//Search_Seq設(shè)置“哨兵”的目的是省略對(duì)下標(biāo)越界的檢查，提高算法執(zhí)行速度第10章查找一、順序查找(舉例)第二節(jié)靜態(tài)查找表第10章查找i=11找64監(jiān)視哨i=7i=8i=9i=10比較次數(shù)=5比較次數(shù)：查找第n個(gè)元素：1查找第n-1個(gè)元素：2……….查找第1個(gè)元素：n查找第i個(gè)元素：n+1-i查找失敗：n+10123456789101164513192137566475808892一、順序查找(算法性能分析)12第二節(jié)靜態(tài)查找表對(duì)順序表而言，Ci=n-i+1在等概率查找的情況下，Pi=1/nASL=n*P1+(n-1)P2+…+2Pn-1+Pn=(n+1)/2第10章查找一、順序查找(不等概率)13第二節(jié)靜態(tài)查找表如果被查找的記錄概率不等時(shí)，取Pn≥Pn-1≥···≥P2≥P1若查找概率無法事先測(cè)定，則查找過程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上第10章查找一、順序查找(特點(diǎn))14第二節(jié)靜態(tài)查找表優(yōu)點(diǎn)：1.簡(jiǎn)單2.適應(yīng)面廣(對(duì)表的結(jié)構(gòu)無任何要求)缺點(diǎn)：1.平均查找長(zhǎng)度較大2.特別是當(dāng)n很大時(shí)，查找效率很低第10章查找二、折半查找15第二節(jié)靜態(tài)查找表折半查找算法是有序表的查找方法在折半查找算法中，靜態(tài)查找表按關(guān)鍵字大小的次序，有序地存放在順序表中折半查找的原理是：1.先確定待查記錄所在的范圍(前部分或后部分)2.逐步縮小(一半)范圍直到找(不)到該記錄為止第10章查找二、折半查找(算法)16第二節(jié)靜態(tài)查找表1.n個(gè)對(duì)象從小到大存放在有序順序表ST中，k為給定值2.設(shè)low、high指向待查元素所在區(qū)間的下界、上界，即low=1,high=n3.設(shè)mid指向待區(qū)間的中點(diǎn)，即mid=(low+high)/24.讓k與mid指向的記錄比較若k=ST[mid].key，查找成功若k<ST[mid].key，則high=mid-1 [上半?yún)^(qū)間]若k>ST[mid].key，則low=mid+1 [下半?yún)^(qū)間]5.重復(fù)3,4操作，直至low>high時(shí)，查找失敗。第10章查找二、折半查找(舉例－成功)17第二節(jié)靜態(tài)查找表第10章查找找641234567891011513192137566475808892Low=1High=11mid=61234567891011513192137566475808892Low=7High=11mid=91234567891011513192137566475808892Low=7mid=7High=8二、折半查找(舉例－不成功)18第二節(jié)靜態(tài)查找表當(dāng)下界low大于上界high時(shí)，說明有序表中沒有關(guān)鍵字等于K的元素，查找不成功第10章查找1234567891011513192137566475808892High=6Low=7找59二、折半查找(判定樹)第二節(jié)靜態(tài)查找表判定樹：描述查找過程的二叉樹。有n個(gè)結(jié)點(diǎn)的判定樹的深度為log2n+1折半查找法在查找過程中進(jìn)行的比較次數(shù)最多不超過log2n+1有11個(gè)元素的表的例子第10章查找i1234567891011Ci342341342346391425781011二、折半查找(性能分析)第二節(jié)靜態(tài)查找表設(shè)有序表的長(zhǎng)度n=2h-1（即h=log2(n+1)）,則描述折半查找的判定樹是深度為h的滿二叉樹樹中層次為1的結(jié)點(diǎn)有1個(gè)，層次為2的結(jié)點(diǎn)有2個(gè)，層次為h的結(jié)點(diǎn)有2h-1個(gè)假設(shè)表中每個(gè)記錄的查找概率相等，則查找成功時(shí)折半查找的平均查找長(zhǎng)度第10章查找二、折半查找(特點(diǎn))第二節(jié)靜態(tài)查找表折半查找的效率比順序查找高(特別是在靜態(tài)查找表的長(zhǎng)度很長(zhǎng)時(shí))折半查找只能適用于有序表，并且以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)第10章查找三、分塊查找22第二節(jié)靜態(tài)查找表分塊查找是一種索引順序表(分塊有序表)查找方法，是折半查找和順序查找的簡(jiǎn)單結(jié)合索引順序表(分塊有序表)將整個(gè)表分成幾塊，塊內(nèi)無序，塊間有序所謂塊間有序是指后一塊表中所有記錄的關(guān)鍵字均大于前一塊表中的最大關(guān)鍵字第10章查找三、分塊查找(分塊有序表)23第二節(jié)靜態(tài)查找表主表：用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域索引表：每個(gè)結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針第10章查找1234567891011519132175566437888092211755929主表索引表三、分塊查找(舉例)24第二節(jié)靜態(tài)查找表采用折半查找方法在索引表中找到塊[第2塊]用順序查找方法在主表對(duì)應(yīng)塊中找到記錄[第3記錄]第10章查找1234567891011519132175566437888092找64211755929主表索引表三、分塊查找(性能分析)25第二節(jié)靜態(tài)查找表若將長(zhǎng)度為n的表分成b塊，每塊含s個(gè)記錄，并設(shè)表中每個(gè)記錄查找概率相等用折半查找方法在索引表中查找索引塊，ASL塊間≈log2(n/s+1)用順序查找方法在主表對(duì)應(yīng)塊中查找記錄，ASL塊內(nèi)=s/2ASL≈log2(n/s+1)+s/2第10章查找一、動(dòng)態(tài)查找表26第三節(jié)動(dòng)態(tài)查找表表結(jié)構(gòu)本身是在查找過程中動(dòng)態(tài)生成的若表中存在其關(guān)鍵字等于給定值key的記錄,表明查找成功；否則插入關(guān)鍵字等于key的記錄。第10章查找二、二叉排序樹27第三節(jié)動(dòng)態(tài)查找表空樹或者是具有如下特性的二叉樹：⑴.若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；⑵.若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；⑶.它的左、右子樹也都分別是二叉排序樹。第10章查找二、二叉排序樹(舉例)28第三節(jié)動(dòng)態(tài)查找表第10章查找二叉排序樹非二叉排序樹56645923788198021137556645923788198021137560二、二叉排序樹(查找)29第三節(jié)動(dòng)態(tài)查找表二叉排序樹又稱二叉查找樹查找算法：給定值與根結(jié)點(diǎn)比較：1.若相等，查找成功2.若小于，查找左子樹3.若大于，查找右子樹第10章查找在二叉排序樹中查找關(guān)鍵字值等于37,88,94566459237881980211375二、二叉排序樹(插入)30第三節(jié)動(dòng)態(tài)查找表二叉排序樹是一種動(dòng)態(tài)樹表當(dāng)樹中不存在查找的結(jié)點(diǎn)時(shí)，作插入操作新插入的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)（只需改動(dòng)一個(gè)結(jié)點(diǎn)的指針）該葉子結(jié)點(diǎn)是查找不成功時(shí)路徑上訪問的最后一個(gè)結(jié)點(diǎn)左孩子或右孩子(新結(jié)點(diǎn)值小于或大于該結(jié)點(diǎn)值)第10章查找二、二叉排序樹(插入舉例)31第三節(jié)動(dòng)態(tài)查找表插入結(jié)點(diǎn)94第10章查找56645923788198021137594二、二叉排序樹(生成舉例)32第三節(jié)動(dòng)態(tài)查找表畫出在初始為空的二叉排序樹中依次插入56,64,92,80,88,75時(shí)該樹的生長(zhǎng)全過程第10章查找566492888056649280566492566456566492888075二、二叉排序樹(中序遍歷)33第三節(jié)動(dòng)態(tài)查找表中序遍歷二叉排序樹，可得到一個(gè)關(guān)鍵字的有序序列,如5,13,19,21,37,56,64,92,75,80,88第10章查找566459237881980211375二、二叉排序樹(刪除)34第三節(jié)動(dòng)態(tài)查找表刪除二叉排序樹中的一個(gè)結(jié)點(diǎn)后，必須保持二叉排序樹的特性（左子樹的所有結(jié)點(diǎn)值小于根結(jié)點(diǎn)，右子樹的所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)）也即保持中序遍歷后，輸出為有序序列第10章查找二、二叉排序樹(刪除)35第三節(jié)動(dòng)態(tài)查找表被刪除結(jié)點(diǎn)具有以下三種情況：1.是葉子結(jié)點(diǎn)2.只有左子樹或右子樹3.同時(shí)有左、右子樹第10章查找二、二叉排序樹(刪除)36第三節(jié)動(dòng)態(tài)查找表1.被刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn)直接刪除結(jié)點(diǎn)，并讓其父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針變?yōu)榭盏?0章查找566459237881980211375刪除結(jié)點(diǎn)88二、二叉排序樹(刪除)第三節(jié)動(dòng)態(tài)查找表2.被刪除結(jié)點(diǎn)只有左子樹或右子樹刪除結(jié)點(diǎn),讓其父結(jié)點(diǎn)指向該結(jié)點(diǎn)的指針指向其左子樹(或右子樹),即用孩子結(jié)點(diǎn)替代被刪除結(jié)點(diǎn)即可第10章查找56645928819802113755659237881980211375刪除結(jié)點(diǎn)64(只有右子樹)刪除結(jié)點(diǎn)37(只有左子樹)566459237881980211375原圖二、二叉排序樹(刪除)38第三節(jié)動(dòng)態(tài)查找表3.被刪除結(jié)點(diǎn)p既有左子樹，又有右子樹以中序遍歷時(shí)的直接前驅(qū)s替代被刪除結(jié)點(diǎn)p，然后再刪除該直接前驅(qū)（只可能有左孩子）第10章查找PCpFPRfCLQSLQLSqs二、二叉排序樹(刪除)39第三節(jié)動(dòng)態(tài)查找表3.被刪除結(jié)點(diǎn)既有左子樹，又有右子樹(舉例)第10章查找56645923788198021137556649237881980215753764592218880191375原圖刪除結(jié)點(diǎn)13刪除結(jié)點(diǎn)56二、二叉排序樹(性能分析)40第三節(jié)動(dòng)態(tài)查找表在最好的情況下，二叉排序樹為一近似完全二叉樹時(shí)，其查找深度為log2n量級(jí)，即其時(shí)間復(fù)雜性為O(log2n)第10章查找755619645372180138892二、二叉排序樹(性能分析)第三節(jié)動(dòng)態(tài)查找表在最壞的情況下，二叉排序樹為近似線性表時(shí)(如以升序或降序輸入結(jié)點(diǎn)時(shí))，其查找深度為n量級(jí)，即其時(shí)間復(fù)雜性為O(n)第10章查找41808892647521191356375二、二叉排序樹(特性)42第三節(jié)動(dòng)態(tài)查找表一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列（通過中序遍歷）插入新記錄時(shí)，只需改變一個(gè)結(jié)點(diǎn)的指針，相當(dāng)于在有序序列中插入一個(gè)記錄而不需要移動(dòng)其它記錄二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作存儲(chǔ)結(jié)構(gòu)第10章查找二、二叉排序樹(特性)43第三節(jié)動(dòng)態(tài)查找表但當(dāng)插入記錄的次序不當(dāng)時(shí)(如升序或降序)，則二叉排序樹深度很深(11)，增加了查找的時(shí)間第10章查找808892647521191356375三、平衡二叉樹[AVL](定義)44第三節(jié)動(dòng)態(tài)查找表平衡二叉樹是二叉排序(查找)樹的另一種形式平衡二叉樹又稱AVL樹(Adelsen-VelskiiandLandis)其特點(diǎn)為：樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值不大于1，即|hL-hR|≤1第10章查找566459237881980211375AVL樹非AVL樹565641913753780928821三、平衡二叉樹[AVL](平衡因子)45第三節(jié)動(dòng)態(tài)查找表每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字,給出該結(jié)點(diǎn)左子樹的高度減去右子樹的高度所得的高度差,這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balanceAVL樹任一結(jié)點(diǎn)平衡因子只能取-1,0,1第10章查找56564191375378092882100-10-1000100三、平衡二叉樹[AVL](平衡化旋轉(zhuǎn))46第三節(jié)動(dòng)態(tài)查找表如果在一棵平衡的二叉查找樹中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)(處理)有兩類：1.單向旋轉(zhuǎn)(單向右旋和單向左旋)2.雙向旋轉(zhuǎn)(先左后右旋轉(zhuǎn)和先右后左旋轉(zhuǎn))第10章查找三、平衡二叉樹[AVL](平衡化旋轉(zhuǎn))47第三節(jié)動(dòng)態(tài)查找表每插入一個(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)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。第10章查找三、平衡二叉樹[AVL](平衡化單向旋轉(zhuǎn))48第三節(jié)動(dòng)態(tài)查找表如果這三個(gè)結(jié)點(diǎn)處于一條直線上(“/”型或“\”型)，則采用單向旋轉(zhuǎn)進(jìn)行平衡化單向旋轉(zhuǎn)分為單向右旋(“/”型)和單向左旋(“\”型)第10章查找ACBCBA單向左旋ACBABC單向右旋三、平衡二叉樹[AVL](平衡化雙向旋轉(zhuǎn))49第三節(jié)動(dòng)態(tài)查找表如果這三個(gè)結(jié)點(diǎn)處于一條折線上(“<”型或“>”型)，則采用雙向旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右(“<”型)和先右后左(“>”型)第10章查找ACB先左后右旋轉(zhuǎn)BCA先右后左旋轉(zhuǎn)ACBACBABCABC三、平衡二叉樹[AVL](單向右旋)50第三節(jié)動(dòng)態(tài)查找表在B左子樹BL上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到+2，造成不平衡。第10章查找hhhAARBRBBLhh+1BAARBRBLhhh+1ARBRABBLh000+1+1+2三、平衡二叉樹[AVL](單向右旋)51第三節(jié)動(dòng)態(tài)查找表為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和BL(“/”型)以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針(右)旋轉(zhuǎn)。第10章查找hhhAARBRBBLhh+1BAARBRBLhhh+1ARBRABBLh000+1+1+2三、平衡二叉樹[AVL](單向左旋)52第三節(jié)動(dòng)態(tài)查找表在B右子樹BR中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，出現(xiàn)不平衡。第10章查找hhhABBRALBLhhh+1ALABBRBLhhh+1BBRAALBL-1-20-100三、平衡二叉樹[AVL](單向左旋)53第三節(jié)動(dòng)態(tài)查找表沿插入路徑檢查三個(gè)結(jié)點(diǎn)A、B和BR(“\”型)以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針(左)旋轉(zhuǎn)第10章查找hhhABBRALBLhhh+1ALABBRBLhhh+1BBRAALBL-1-20-100三、平衡二叉樹[AVL](先左后右雙向旋轉(zhuǎn))54第三節(jié)動(dòng)態(tài)查找表在C的子樹CL或CR中插入新結(jié)點(diǎn)，該子樹的高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡第10章查找00+1hhAARCBL0h-1h-1BCLCR+2-1+1hhAh-1hARCBLBCLCR三、平衡二叉樹[AVL](先左后右雙向旋轉(zhuǎn))55第三節(jié)動(dòng)態(tài)查找表從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、B和C(“<”型)以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，做單向左旋第10章查找+2-1+1hhAh-1hARCBLBCLCR00+2hhAARCBL+2h-1hBCLCR三、平衡二叉樹[AVL](先左后右雙向旋轉(zhuǎn))56第三節(jié)動(dòng)態(tài)查找表再以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，做單向右旋第10章查找00+2hhAARCBL+2h-1hBCLCR00-1hhAh-1hARCBLBCLCR三、平衡二叉樹[AVL](先右后左雙向旋轉(zhuǎn))57第三節(jié)動(dòng)態(tài)查找表在C的子樹CL或CR中插入新結(jié)點(diǎn)，該子樹的高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡第10章查找-10000hhABBRCh-1ALCLCRh-1-1-2000hhABhALCLCRh-1CBR三、平衡二叉樹[AVL](先右后左雙向旋轉(zhuǎn))58第三節(jié)動(dòng)態(tài)查找表從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、C和D(“>”型)以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，作單向右旋第10章查找00-2hhABBR-2h-1hALCLCRC-1-2000hhABhALCLCRh-1CBR三、平衡二叉樹[AVL](先右后左雙向旋轉(zhuǎn))59第三節(jié)動(dòng)態(tài)查找表再以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，作單向左旋第10章查找00-2hhABBR-2h-1hALCLCRC0+10hhAh-1hBBRCALCLCR三、平衡二叉樹[AVL](舉例)60第三節(jié)動(dòng)態(tài)查找表畫出在初始為空的AVL樹中依次插入64,5,13,21,19,80,75,37,56時(shí)該樹的生長(zhǎng)過程，并在有旋轉(zhuǎn)時(shí)說出旋轉(zhuǎn)的類型。第10章查找640645+10645130-1+2左右雙旋13564000135210+1-1641234三、平衡二叉樹[AVL](續(xù)例)61第三節(jié)動(dòng)態(tài)查找表繼續(xù)插入19,80,75,37,56時(shí)該樹的生長(zhǎng)過程，并在有旋轉(zhuǎn)時(shí)說出旋轉(zhuǎn)的類型。第10章查找51356421190+1+2右單旋5136419000-121-2三、平衡二叉樹[AVL](續(xù)例)62第三節(jié)動(dòng)態(tài)查找表繼續(xù)插入19,80,75,37,56時(shí)該樹的生長(zhǎng)過程，并在有旋轉(zhuǎn)時(shí)說出旋轉(zhuǎn)的類型。第10章查找6513218019640-1-1-20564019左單旋-1132180三、平衡二叉樹[AVL](續(xù)例)63第三節(jié)動(dòng)態(tài)查找表繼續(xù)插入19,80,75,37,56時(shí)該樹的生長(zhǎng)過程，并在有旋轉(zhuǎn)時(shí)說出旋轉(zhuǎn)的類型。第10章查找7-2右左雙旋135190758021+164-175640001358021190三、平衡二叉樹[AVL](續(xù)例)64第三節(jié)動(dòng)態(tài)查找表繼續(xù)插入19,80,75,37,56時(shí)該樹的生長(zhǎng)過程，并在有旋轉(zhuǎn)時(shí)說出旋轉(zhuǎn)的類型。第10章查找8755+1+113643708019-121三、平衡二叉樹[AVL](續(xù)例)65第三節(jié)動(dòng)態(tài)查找表繼續(xù)插入19,80,75,37,56時(shí)該樹的生長(zhǎng)過程，并在有旋轉(zhuǎn)時(shí)說出旋轉(zhuǎn)的類型。第10章查找9左右雙旋56-257564+201337192180-1+2751350021+164560-1803719三、平衡二叉樹(刪除)66第三節(jié)動(dòng)態(tài)查找表如果被刪結(jié)點(diǎn)A最多只有一個(gè)孩子，那么將結(jié)點(diǎn)A從樹中刪去，并將其雙親指向它的指針指向它的唯一的孩子，并作平衡化處理如果被刪結(jié)點(diǎn)A沒有孩子，則直接刪除之，并作平衡化處理如果被刪結(jié)點(diǎn)A有兩個(gè)子女，則用該結(jié)點(diǎn)的直接前驅(qū)S替代被刪結(jié)點(diǎn)，然后對(duì)直接前驅(qū)S作刪除處理(S只有一個(gè)孩子或沒有孩子)第10章查找四、B-/B+樹67第三節(jié)動(dòng)態(tài)查找表移至17周上第10章查找一、哈希表(散列表)68第四節(jié)哈希表哈希(Hash)表又稱散列表散列表是一種直接計(jì)算記錄存放地址的方法，它在關(guān)鍵碼與存儲(chǔ)位置之間直接建立了映象。第10章查找一、哈希表(函數(shù))69第四節(jié)哈希表哈希函數(shù)是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象哈希函數(shù)在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立起一種對(duì)應(yīng)關(guān)系。可寫成：

addr(ai)=H(keyi)H(·)為哈希函數(shù)keyi是表中元素ai關(guān)鍵字,addr(ai)是存儲(chǔ)地址第10章查找一、哈希表(查找)70第四節(jié)哈希表哈希查找也叫散列查找，是利用哈希函數(shù)進(jìn)行查找的過程。首先利用哈希函數(shù)及記錄的關(guān)鍵字計(jì)算出記錄的存儲(chǔ)地址然后直接到指定地址進(jìn)行查找不需要經(jīng)過比較，一次存取就能得到所查元素第10章查找一、哈希表(沖突)71第四節(jié)哈希表不同的記錄，其關(guān)鍵字通過哈希函數(shù)的計(jì)算，可能得到相同的地址把不同的記錄映射到同一個(gè)散列地址上，這種現(xiàn)象稱為沖突第10章查找一、哈希表(定義)72第四節(jié)哈希表根據(jù)設(shè)定的哈希函數(shù)

H(key)和所選中的處理沖突的方法將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置如此構(gòu)造所得的查找表稱之為“哈希表”第10章查找二、哈希函數(shù)(均勻性)73第四節(jié)哈希表哈希函數(shù)實(shí)現(xiàn)的一般是從一個(gè)大的集合（部分元素，空間位置上一般不連續(xù)）到一個(gè)小的集合（空間連續(xù)）的映射一個(gè)好的哈希函數(shù)，對(duì)于記錄中的任何關(guān)鍵字，將其映射到地址集合中任何一個(gè)地址的概率應(yīng)該是相等的即關(guān)鍵字經(jīng)過哈希函數(shù)得到一個(gè)“隨機(jī)的地址”第10章查找二、哈希函數(shù)(要求)74第四節(jié)哈希表哈希函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果。哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵字，如果散列表允許有m個(gè)地址時(shí)，其值域必須在0到m-1之間。散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè)地址空間中第10章查找二、哈希函數(shù)(直接定址法)75第四節(jié)哈希表直接定址法中，哈希函數(shù)取關(guān)鍵字的線性函數(shù)

H(key)=axkey+b其中a和b為常數(shù)第10章查找二、哈希函數(shù)(直接定址法－舉例)76第四節(jié)哈希表H(key)=key-2004131000第10章查找062004131006鄧煦男信息工程學(xué)院112004131011張國(guó)明男信息工程學(xué)院172004131017劉金棠男信息工程學(xué)院222004131022陳俊東男信息工程學(xué)院252004131025邱益林男信息工程學(xué)院312004131031陳明亮男信息工程學(xué)院322004131032郭寧男信息工程學(xué)院二、哈希函數(shù)(直接定址法－特性)77第四節(jié)哈希表直接定址法僅適合于地址集合的大小與關(guān)鍵字集合的大小相等的情況當(dāng)a=1時(shí)，H(key)=key，即用關(guān)鍵字作地址在實(shí)際應(yīng)用中能使用這種哈希函數(shù)的情況很少第10章查找二、哈希函數(shù)(數(shù)字分析法)78第四節(jié)哈希表假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)分析關(guān)鍵字集中的全體從中提取分布均勻的若干位或它們的組合作為地址。第10章查找二、哈希函數(shù)(數(shù)字分析法－舉例)79第四節(jié)哈希表有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)第10章查找8134653281372242813874228130136781322817813389678136853781419355…..分析：只取8只取1只取3、4只取2、7、5

數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位與另兩位的疊加作哈希地址二、哈希函數(shù)(數(shù)字分析法－特性)80第四節(jié)哈希表數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況數(shù)字分析法完全依賴于關(guān)鍵碼集合。如果換一個(gè)關(guān)鍵碼集合，選擇哪幾位要重新決定。第10章查找二、哈希函數(shù)(平方取中法)81第四節(jié)哈希表以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。第10章查找二、哈希函數(shù)(平方取中法－舉例)82第四節(jié)哈希表此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵碼的標(biāo)識(shí)符的內(nèi)碼的平方,然后按照散列表的大小取中間的若干位作為散列地址。第10章查找二、哈希函數(shù)(平方取中法－舉例)83第四節(jié)哈希表標(biāo)識(shí)符的八進(jìn)制內(nèi)碼表示及其平方值標(biāo)識(shí)符內(nèi)碼

內(nèi)碼的平方散列地址A

01

01 001A1 0134

20420 042B

02

4 004DMAX

04150130

21526443617100 443DMAX10415013034

5264473522151420 352AMAX

01150130

135423617100 236AMAX10115013034

3454246522151420 652第10章查找二、哈希函數(shù)(平方取中法－特性)84第四節(jié)哈希表平方取中法是較常用的構(gòu)造哈希函數(shù)的方法適合于關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)且頻度很高的情況中間所取的位數(shù)，由哈希表長(zhǎng)決定第10章查找二、哈希函數(shù)(折疊法)85第四節(jié)哈希表將關(guān)鍵字分割成位數(shù)相同的若干部分(最后部分的倍數(shù)可以不同)，然后取它們的疊加和(舍去進(jìn)位)為哈希地址。移位疊加:將分割后的幾部分低位對(duì)齊相加間界疊加:從一端沿分割界來回折送，然后對(duì)齊相加第10章查找二、哈希函數(shù)(折疊法－舉例)86第四節(jié)哈希表關(guān)鍵字為：0442205864，哈希地址位數(shù)為4第10章查找586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加二、哈希函數(shù)(折疊法－特性)87第四節(jié)哈希表折疊法適合于關(guān)鍵字的數(shù)字位數(shù)特別多，而且每一位上數(shù)字分布大致均勻的情況第10章查找二、哈希函數(shù)(除留余數(shù)法)88第四節(jié)哈希表取關(guān)鍵字被某個(gè)不大于哈希表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址

H(key)=keyMODp(p≤m)m為表長(zhǎng)p為不大于m的素?cái)?shù)或是不含20以下的質(zhì)因子第10章查找二、哈希函數(shù)(除留余數(shù)法－p值)89第四節(jié)哈希表給定一組關(guān)鍵字為:12,39,18,24,33,21，若取p=9,則他們對(duì)應(yīng)的哈希函數(shù)值將為: 3,3,0,6,6,3可見，若p中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能第10章查找二、哈希函數(shù)(除留余數(shù)法－特性)90第四節(jié)哈希表除留余數(shù)法是一種最簡(jiǎn)單、最常用的構(gòu)造哈希函數(shù)的方法不令可以對(duì)關(guān)鍵字直接取模(MOD)，也可在折疊、平方取中等運(yùn)算之后取模第10章查找三、處理沖突的方法91第四節(jié)哈希表“處理沖突”的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。處理沖突的方法主要有三種：1.開放定址法2.再哈希法3.鏈地址法第10章查找三、處理沖突的方法(開放定址法)92第四節(jié)哈希表為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列：H0,H1,H2,…,Hs，1≤s≤m-1 Hi=[H(key)+di]MODm i=1,2,…,sH(key)為哈希函數(shù)m為哈希表長(zhǎng)第10章查找三、處理沖突的方法(開放定址法－線性探測(cè))93第四節(jié)哈希表當(dāng)di取1,2,3,…,m-1時(shí)，稱這種開放定址法為線性探測(cè)再散列舉例：給定關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}，設(shè)定哈希函數(shù)H(key)=keyMOD11(表長(zhǎng)=11)第10章查找190123145568118236112136251012345678910三、處理沖突的方法(開放定址法－二次探測(cè))94第四節(jié)哈希表當(dāng)di取=12,22,32,…時(shí)，稱這種開放定址法為二次探測(cè)再散列舉例：給定關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}，設(shè)定哈希函數(shù)H(key)=keyMOD11(表長(zhǎng)=11)第10章查找112121313012345678910190123146855118236三、處理沖突的方法(開放定址法－特性)95第四節(jié)哈希表優(yōu)點(diǎn)：只要哈希表中有空位置，總能找到一個(gè)不發(fā)生沖突的地址缺點(diǎn)：易產(chǎn)生“二次聚集”，即在處理同義詞的沖突過程中，又添加了非同義詞的沖突，對(duì)查找不利第10章查找三、處理沖突的方法(再哈希法)96第四節(jié)哈希表構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，計(jì)算下一個(gè)哈希地址，直到?jīng)_突不再發(fā)生，即： Hi=Rhi(key)i=1,2,……kRhi—不同的哈希函數(shù)特點(diǎn)：不易產(chǎn)生聚集，但增加計(jì)算時(shí)間第10章查找三、處理沖突的方法(鏈地址法)97第四節(jié)哈希表將所有哈希地址相同的記錄都鏈接在同一鏈表中舉例：給定關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}，設(shè)定哈希函數(shù)H(key)=keyMOD11(表長(zhǎng)=11)[表后插入]第10章查找^^^^^01234567891019^2301^145568^11^82^36^三、處理沖突的方法(鏈地址法－舉例)98第四節(jié)哈希表例：已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=keyMOD13,用鏈地址法處理沖突[表頭插入]第10章查找0123456789101112

79^271145568841920102311^^^^^^^^^^^^四、哈希表的實(shí)現(xiàn)99第四節(jié)哈希表假設(shè)哈希函數(shù)為關(guān)鍵字求模運(yùn)算，哈希表用拉鏈法解決沖突，其結(jié)構(gòu)可以定義如下： #defineLEN32

structnode{

intdata;

structnode*next;};

structnode*HashTab[LEN];第10章查找四、哈希表的實(shí)現(xiàn)－哈希函數(shù)hash()100第四節(jié)哈希表返回值為哈希表地址

int

hash(intkey){

retAddr=keyMODLEN;

return(retAddr); }第10章查找四、哈希表的實(shí)現(xiàn)－查找過程101第四節(jié)哈希表對(duì)于給定值key，計(jì)算哈希地址p=hash(Key)若HashTab[p].next=NULL，則查找不成功若HashTab[p].next.data=key，則查找成功否則“求下一地址”，再進(jìn)行比較第10章查找給定k值計(jì)算hash(key)此地址為空關(guān)鍵字==key查找失敗查找成功按處理沖突方法計(jì)算下一地址YNYN四、哈希表的實(shí)現(xiàn)－查找函數(shù)search()102第四節(jié)哈希表若找到key，返回其結(jié)點(diǎn)指針；否則將其插入表中再返回其結(jié)點(diǎn)指針[表頭插入] node*sear