第8章查找(1)

1、1第八章 查 找2 8.2 靜態(tài)查找表靜態(tài)查找表 8.3 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 8.4 哈希表查找哈希表查找本章目錄本章目錄 小小 結(jié)結(jié) 習(xí)習(xí) 題題 8.1 基本概念與術(shù)語基本概念與術(shù)語38.1 8.1 基本概念與術(shù)語基本概念與術(shù)語關(guān)鍵字關(guān)鍵字?jǐn)?shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) (字段字段)數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。組合項(xiàng)組合項(xiàng)如果一個(gè)數(shù)據(jù)項(xiàng)是由若干項(xiàng)組合構(gòu)成的，如果一個(gè)數(shù)據(jù)項(xiàng)是由若干項(xiàng)組合構(gòu)成的，則稱此數(shù)據(jù)項(xiàng)為組合項(xiàng)。則稱此數(shù)據(jù)項(xiàng)為組合項(xiàng)。 數(shù)據(jù)元素?cái)?shù)據(jù)元素（記錄）（記錄）數(shù)據(jù)元素是由若干數(shù)據(jù)項(xiàng)、組合項(xiàng)構(gòu)成數(shù)據(jù)元素是由若干數(shù)據(jù)項(xiàng)、組合項(xiàng)構(gòu)成的數(shù)據(jù)單位，是在某一問題中作為整體的

2、數(shù)據(jù)單位，是在某一問題中作為整體進(jìn)行考慮和處理的基本單位。進(jìn)行考慮和處理的基本單位。關(guān)鍵字是數(shù)據(jù)元素（記錄）中某個(gè)項(xiàng)或關(guān)鍵字是數(shù)據(jù)元素（記錄）中某個(gè)項(xiàng)或組合項(xiàng)的值，用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元組合項(xiàng)的值，用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（記錄）。素（記錄）。 48.1 8.1 基本概念與術(shù)語基本概念與術(shù)語( (續(xù)續(xù)) )動(dòng)態(tài)查找表動(dòng)態(tài)查找表查找表查找表查找表是由具有同一類型（屬性）的數(shù)查找表是由具有同一類型（屬性）的數(shù)據(jù)元素（記錄）組成的集合。據(jù)元素（記錄）組成的集合。靜態(tài)查找表靜態(tài)查找表僅對(duì)查找表進(jìn)行查找操作，而不改變的僅對(duì)查找表進(jìn)行查找操作，而不改變的查找表。也就說，在查找操作的過程中查找表。也就說，在

3、查找操作的過程中，查找表的結(jié)構(gòu)不發(fā)生變化。查找表中，查找表的結(jié)構(gòu)不發(fā)生變化。查找表中的數(shù)據(jù)元素的個(gè)數(shù)不會(huì)發(fā)生改變。的數(shù)據(jù)元素的個(gè)數(shù)不會(huì)發(fā)生改變。對(duì)查找表除進(jìn)行查找操作外，可能還要對(duì)查找表除進(jìn)行查找操作外，可能還要進(jìn)行向表中插入數(shù)據(jù)元素，或刪除表中進(jìn)行向表中插入數(shù)據(jù)元素，或刪除表中數(shù)據(jù)元素的表。查找表中的數(shù)據(jù)元素是數(shù)據(jù)元素的表。查找表中的數(shù)據(jù)元素是可以增加或者減少?？梢栽黾踊蛘邷p少。58.1 8.1 基本概念與術(shù)語基本概念與術(shù)語( (續(xù)續(xù)) )查找查找根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字的值等于給定值的記錄或數(shù)據(jù)元其關(guān)鍵字的值等于給定值的記錄或數(shù)據(jù)元素

4、的操作稱為查找。素的操作稱為查找。數(shù)據(jù)元素類型說明數(shù)據(jù)元素類型說明typedef struct KeyType key; /關(guān)鍵字字段關(guān)鍵字字段 /其它字段其它字段 ElemType；6 由于查找表中的數(shù)據(jù)元素之間不存在由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。明顯的組織規(guī)律，因此不便于查找。 為了提高查找的效率，為了提高查找的效率， 需要在查找表需要在查找表中的元素之間人為地中的元素之間人為地 附加某種確定的關(guān)附加某種確定的關(guān)系，換句話說，系，換句話說， 用另外一種結(jié)構(gòu)來表示用另外一種結(jié)構(gòu)來表示查找表。查找表。如何進(jìn)行查找？如何進(jìn)行查找？查找的方法取決于查找表的結(jié)構(gòu)。查

5、找的方法取決于查找表的結(jié)構(gòu)。7線性表：線性表：適用于靜態(tài)查找，主要采用順序查適用于靜態(tài)查找，主要采用順序查找技術(shù)、折半查找技術(shù)。找技術(shù)、折半查找技術(shù)。樹表：樹表：適用于動(dòng)態(tài)查找，主要采用二叉排序適用于動(dòng)態(tài)查找，主要采用二叉排序樹的查找技術(shù)。樹的查找技術(shù)。哈希表：哈希表：靜態(tài)查找和動(dòng)態(tài)查找均適用，主要靜態(tài)查找和動(dòng)態(tài)查找均適用，主要采用散列技術(shù)。采用散列技術(shù)。 本章討論的查找結(jié)構(gòu)本章討論的查找結(jié)構(gòu)88.2 8.2 靜態(tài)查找表靜態(tài)查找表靜態(tài)查找表結(jié)構(gòu)靜態(tài)查找表結(jié)構(gòu)1順序查找順序查找2有序表的折半查找有序表的折半查找3有序表的其他查找方法有序表的其他查找方法4分塊查找分塊查找59靜態(tài)查找表結(jié)構(gòu)靜態(tài)查找

6、表結(jié)構(gòu) 靜態(tài)查找靜態(tài)查找是指在查找的過程中查找表的結(jié)是指在查找的過程中查找表的結(jié)構(gòu)不發(fā)生變化的查找操作，也就是在查找構(gòu)不發(fā)生變化的查找操作，也就是在查找的過程中查找表中的數(shù)據(jù)元素既不增加也的過程中查找表中的數(shù)據(jù)元素既不增加也不減少。不減少。 靜態(tài)查找表可以有多種靜態(tài)查找表可以有多種表示方法表示方法，不同的，不同的表示方法其查找操作的實(shí)現(xiàn)也不相同表示方法其查找操作的實(shí)現(xiàn)也不相同。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)10鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)template struct Node T key; /關(guān)鍵字域關(guān)鍵字域 . /其他域其他域;template class StaticSea

7、rchTablepublic: Node *ST; int index; StaticSearchTable() ST=NULL; /初始為空表初始為空表 index=0; /當(dāng)前元素個(gè)數(shù)當(dāng)前元素個(gè)數(shù) ;11順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)template class SqListprivate： T *elem； /表基址表基址 int length； /表長度表長度 int listsize； /表容量表容量 public： SqList(int m) ；/構(gòu)造函數(shù)，構(gòu)造函數(shù)， 創(chuàng)建容量為創(chuàng)建容量為m的空表的空表 SqList()；/析構(gòu)函數(shù)，刪除表空間析構(gòu)函數(shù)，刪除表空間12順序查找順序查找 查

8、找方法查找方法：從表的一端開始，向另一端逐個(gè)將給定值從表的一端開始，向另一端逐個(gè)將給定值key與關(guān)鍵字進(jìn)行比較與關(guān)鍵字進(jìn)行比較: 若相等，若相等，查找成功查找成功，給出數(shù)據(jù)元素在表中的，給出數(shù)據(jù)元素在表中的位置；位置； 若整個(gè)表檢測完，仍未找到與若整個(gè)表檢測完，仍未找到與key相同的關(guān)相同的關(guān)鍵字，則鍵字，則查找失敗查找失敗。13順序表的順序查找順序表的順序查找 算法思想算法思想： 將順序表中的將順序表中的0號(hào)單元設(shè)置為號(hào)單元設(shè)置為“哨兵哨兵” 。查找。查找時(shí)從順序表中的最后一個(gè)元素開始，依次向前進(jìn)時(shí)從順序表中的最后一個(gè)元素開始，依次向前進(jìn)行查找。行查找。 算法算法：int s_search1

9、(SqList & L，KeyType k) L.elem0.key = k； for( i = L.length;L.elemi.key k ;i- )； return i； 14順序表的順序查找順序表的順序查找 算法分析算法分析 查找成功時(shí)：查找成功時(shí)： ASL 查找不成功時(shí)：查找不成功時(shí)：ASL= 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(n)=O(n) 111(1)2ninnin n+115單鏈表的順序查找單鏈表的順序查找 算法思想：算法思想：從單鏈表的從單鏈表的首元結(jié)點(diǎn)首元結(jié)點(diǎn)開始，向后一個(gè)一個(gè)檢查開始，向后一個(gè)一個(gè)檢查結(jié)點(diǎn)的值域，同時(shí)設(shè)置一個(gè)結(jié)點(diǎn)的值域，同時(shí)設(shè)置一個(gè)計(jì)數(shù)器計(jì)數(shù)器，用以標(biāo)記

10、所，用以標(biāo)記所訪問結(jié)點(diǎn)在鏈表中的序號(hào)。若查找成功，返回序訪問結(jié)點(diǎn)在鏈表中的序號(hào)。若查找成功，返回序號(hào)的值，否則返回號(hào)的值，否則返回0。 P P a1ana216單鏈表的順序查找單鏈表的順序查找 算法：算法：int s_search2(Linklist head，KeyType k) p=head-next;j=1; while(p!=NULL &p-data!=k) p=p-next; j+; if(p-data= =k) return j; else return 0;17平均查找長度較大，特別是當(dāng)待查找集合中元素較多平均查找長度較大，特別是當(dāng)待查找集合中元素較多時(shí)，查找效率較低。時(shí)

11、，查找效率較低。缺點(diǎn)：缺點(diǎn)：算法簡單而且使用面廣。算法簡單而且使用面廣。對(duì)表中記錄的存儲(chǔ)沒有任何要求，順序存儲(chǔ)和鏈接對(duì)表中記錄的存儲(chǔ)沒有任何要求，順序存儲(chǔ)和鏈接存儲(chǔ)均可；存儲(chǔ)均可；對(duì)表中記錄的有序性也沒有要求，無論記錄是否按對(duì)表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可。關(guān)鍵碼有序均可。優(yōu)點(diǎn)：優(yōu)點(diǎn)：順序查找分析順序查找分析18有序表的折半查找有序表的折半查找 算法思想：算法思想：1 將給定值與中間元素的關(guān)鍵字比較：將給定值與中間元素的關(guān)鍵字比較：1.1若若相等相等，則，則查找成功查找成功；1.2若若小于小于，則在，則在左半?yún)^(qū)左半?yún)^(qū)繼續(xù)查找；繼續(xù)查找；1.3若若大于大于，則在，則在右

12、半?yún)^(qū)右半?yún)^(qū)繼續(xù)查找。繼續(xù)查找。2 不斷重復(fù)上述查找過程，直到查找成功，或所查不斷重復(fù)上述查找過程，直到查找成功，或所查找的區(qū)域無數(shù)據(jù)元素，找的區(qū)域無數(shù)據(jù)元素，查找失敗查找失敗。19有序表的折半查找有序表的折半查找 例如例如：已知如下：已知如下11個(gè)數(shù)據(jù)元素的有序表（關(guān)鍵字即為數(shù)據(jù)元素個(gè)數(shù)據(jù)元素的有序表（關(guān)鍵字即為數(shù)據(jù)元素的值）：（的值）：（05，13，19，21，37，56，64，75，80，88，92）現(xiàn)要查找關(guān)鍵字為現(xiàn)要查找關(guān)鍵字為64和和60的數(shù)據(jù)元素。的數(shù)據(jù)元素。Play20折半查找判定樹折半查找判定樹 判定樹判定樹：折半查找的過程可以用二叉樹來描折半查找的過程可以用二叉樹來描述，樹中

13、的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序表中的一個(gè)記述，樹中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序表中的一個(gè)記錄，結(jié)點(diǎn)的值為該記錄在錄，結(jié)點(diǎn)的值為該記錄在表中的位置。通常表中的位置。通常稱這個(gè)描述折半查找過程的二叉樹為折半查稱這個(gè)描述折半查找過程的二叉樹為折半查找判定樹，簡稱找判定樹，簡稱判定樹判定樹。21 當(dāng)當(dāng)n=0時(shí)，折半查找判定樹為空；時(shí)，折半查找判定樹為空； 當(dāng)當(dāng)n0時(shí)，折半查找判定樹的根結(jié)點(diǎn)是有序表中時(shí)，折半查找判定樹的根結(jié)點(diǎn)是有序表中序號(hào)為序號(hào)為mid=( (n+1) )/2的記錄，根結(jié)點(diǎn)的左子樹是與有的記錄，根結(jié)點(diǎn)的左子樹是與有序表序表r1 rmid- -1相對(duì)應(yīng)的折半查找判定樹，根結(jié)相對(duì)應(yīng)的折半查找判定樹，根結(jié)點(diǎn)的點(diǎn)的

14、右子樹是與右子樹是與rmid+1 rn相對(duì)應(yīng)的折半查找判相對(duì)應(yīng)的折半查找判定樹。定樹。 判定樹的構(gòu)造方法判定樹的構(gòu)造方法22查找成功：查找成功：在表中查找任一記錄的過程，即是在表中查找任一記錄的過程，即是折半查找判定樹中從根結(jié)點(diǎn)到該記錄結(jié)點(diǎn)的路折半查找判定樹中從根結(jié)點(diǎn)到該記錄結(jié)點(diǎn)的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在樹徑，和給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在樹中的層數(shù)。中的層數(shù)。查找不成功：查找不成功：查找失敗的過程就是走了一條查找失敗的過程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，和給定值進(jìn)行從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，和給定值進(jìn)行的關(guān)鍵碼的比較次數(shù)等于該路徑上內(nèi)部結(jié)點(diǎn)的關(guān)鍵碼的比較次數(shù)等于該路

15、徑上內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)。的個(gè)數(shù)。折半查找性能分析折半查找性能分析 23有序表的折半查找有序表的折半查找 算法分析：算法分析：假設(shè)表中每個(gè)元素的查找是等概率的假設(shè)表中每個(gè)元素的查找是等概率的 當(dāng)當(dāng)n較大時(shí)，可以近似為：較大時(shí)，可以近似為：ASL= -1所以有：所以有：T(n)=O(log2n )121111*2log (1) 1nhjiiiinASLp cjnnn2log (1)n24順序表順序表有序表有序表表的特性表的特性無序有序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序 或 鏈?zhǔn)巾樞虿鍎h操作插刪操作易于進(jìn)行需移動(dòng)元素ASL的值的值大小查找性能對(duì)比查找性能對(duì)比25有序表的其它查找方法有序表的其它查找方法 插值查找插值查

16、找 插值查找是插值查找是平均性能最好平均性能最好的查找方法，但的查找方法，但只適合于只適合于關(guān)鍵字均勻分布關(guān)鍵字均勻分布的表，其時(shí)間效的表，其時(shí)間效率仍然是率仍然是O(log2n)。 26有序表的其它查找方法有序表的其它查找方法 斐波那契查找斐波那契查找 斐波那契查找通過斐波那契查找通過斐波那契數(shù)列斐波那契數(shù)列對(duì)有序表對(duì)有序表進(jìn)行分割，查找區(qū)間的兩個(gè)端點(diǎn)和中點(diǎn)都進(jìn)行分割，查找區(qū)間的兩個(gè)端點(diǎn)和中點(diǎn)都與斐波那契數(shù)有關(guān)。與斐波那契數(shù)有關(guān)。27 分塊查找分塊查找 適用條件：適用條件：將查找表分成若干個(gè)子表，將查找表分成若干個(gè)子表，子表為非子表為非有序表有序表，但要求，但要求子表之間子表之間是存在著是存

17、在著有有序序關(guān)系。關(guān)系。 28 分塊查找分塊查找 算法思想：算法思想：1 用給定值用給定值k在索引表中檢測在索引表中檢測索引項(xiàng)索引項(xiàng)，以確定，以確定所要進(jìn)行的查找在查找表中的查找所要進(jìn)行的查找在查找表中的查找分塊分塊 (由由于索引項(xiàng)按關(guān)鍵字字段有序，可用順序查找于索引項(xiàng)按關(guān)鍵字字段有序，可用順序查找或折半查找或折半查找) ;2 對(duì)該分塊進(jìn)行順序查找。對(duì)該分塊進(jìn)行順序查找。 29分塊查找分塊查找 示例示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 532

18、2 48 861 7 13索引表查38找到！找到！30分塊查找分塊查找 算法分析：算法分析： 設(shè)設(shè)n個(gè)數(shù)據(jù)元素的查找表分為個(gè)數(shù)據(jù)元素的查找表分為m個(gè)子表，且每個(gè)子表，且每個(gè)子表均為個(gè)子表均為t個(gè)元素，則個(gè)元素，則t= 。 分塊查找的平均查找長度為：分塊查找的平均查找長度為： mn318.3 8.3 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 二叉排序二叉排序樹樹1平衡二叉樹（平衡二叉樹（AVL樹）樹）2B-樹和樹和B+樹樹332二叉排序樹二叉排序樹 二叉排序樹（二叉排序樹（Binary Sort Tree）或者是一棵空樹；或或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：者是具有下列性質(zhì)的二叉樹： 若左子樹不空若左子樹

19、不空，則左子，則左子樹上所有結(jié)點(diǎn)的值均小于根樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；結(jié)點(diǎn)的值；若右子樹不空若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。大于根結(jié)點(diǎn)的值。 左右子樹也都是二叉排左右子樹也都是二叉排序樹序樹。45125333724100619078一棵二叉排序樹示例一棵二叉排序樹示例33二叉排序樹二叉排序樹 查找過程查找過程1 若根結(jié)點(diǎn)的關(guān)鍵字值若根結(jié)點(diǎn)的關(guān)鍵字值等于等于查找的關(guān)鍵字，成功；查找的關(guān)鍵字，成功；2 若根結(jié)點(diǎn)的關(guān)鍵字值若根結(jié)點(diǎn)的關(guān)鍵字值不等于不等于查找的關(guān)鍵字，查找的關(guān)鍵字，2.1 若若小于小于根結(jié)點(diǎn)的關(guān)鍵字值，查其左子樹；根結(jié)點(diǎn)的關(guān)鍵字值，

20、查其左子樹；2.2 若若大于大于根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹。在根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹。在左右子樹上的操作類似。左右子樹上的操作類似。3450308020908540358832例如例如:查找關(guān)鍵字查找關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 ,35從上述查找過程可見，在查找過程中，從上述查找過程可見，在查找過程中，生成了一條查找路徑生成了一條查找路徑: : 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直從根結(jié)點(diǎn)出發(fā)

21、，沿著左分支或右分支逐層向下直至指針指向空樹為止。至指針指向空樹為止。 查找成功查找成功 查找不成功查找不成功36查找性能的分析查找性能的分析 對(duì)于每一棵特定的二叉排序樹，均對(duì)于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的可按照平均查找長度的定義來求它的 ASL 值，顯然，由值相同的值，顯然，由值相同的 n 個(gè)關(guān)鍵字，個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長的平均查找長 度的值不同，甚至可能度的值不同，甚至可能差別很大。差別很大。37二叉排序樹二叉排序樹 例4024123755122437405540，24，12，37，55 12

22、，24，37，40，5535 / ) 54321 (1niiicp1i2 . 25/ ) 23221 (*niicp38二叉排序樹二叉排序樹 算法分析：算法分析：在二叉排序樹中進(jìn)行查找的平均查找長在二叉排序樹中進(jìn)行查找的平均查找長度和二叉樹的形態(tài)有關(guān)，即，度和二叉樹的形態(tài)有關(guān)，即，最壞最壞: O(n)（單支樹）（單支樹）最好最好: O(log2n)（形態(tài)勻稱，與二分查（形態(tài)勻稱，與二分查找的判定樹相似）找的判定樹相似）39 根據(jù)動(dòng)態(tài)查找表的定義，根據(jù)動(dòng)態(tài)查找表的定義，“插入插入”操作操作在在查找不成功查找不成功時(shí)才進(jìn)行時(shí)才進(jìn)行;二叉排序樹的插入二叉排序樹的插入 若二叉排序樹為空樹，則新插入的結(jié)

23、點(diǎn)若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為為新的根結(jié)點(diǎn)新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必；否則，新插入的結(jié)點(diǎn)必為一個(gè)為一個(gè)新的葉子結(jié)點(diǎn)新的葉子結(jié)點(diǎn)，其插入位置由查，其插入位置由查找過程得到。找過程得到。40二叉排序樹的插入二叉排序樹的插入例：在下圖給定的二叉排序樹中插入結(jié)點(diǎn)例：在下圖給定的二叉排序樹中插入結(jié)點(diǎn)20451253337241006190782041二叉排序樹的構(gòu)造二叉排序樹的構(gòu)造例例 關(guān)鍵字序列為關(guān)鍵字序列為 10， 18， 3， 8， 12， 2， 7， 3 1018381227342二叉排序樹刪除二叉排序樹刪除 操作要點(diǎn)：操作要點(diǎn)：1 從二叉排序樹刪除一個(gè)結(jié)點(diǎn)之后，要使得從二叉排序樹

24、刪除一個(gè)結(jié)點(diǎn)之后，要使得刪刪除之后除之后二叉樹二叉樹還是還是一棵一棵二叉排序樹二叉排序樹；2 從二叉排序樹刪除一個(gè)結(jié)點(diǎn)，既可能是葉子從二叉排序樹刪除一個(gè)結(jié)點(diǎn)，既可能是葉子結(jié)點(diǎn)也可能是分支結(jié)點(diǎn)，處理的方法不同。結(jié)點(diǎn)也可能是分支結(jié)點(diǎn)，處理的方法不同。43二叉排序樹刪除二叉排序樹刪除三種情況三種情況 ：設(shè)待刪結(jié)點(diǎn)為設(shè)待刪結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為，其雙親結(jié)點(diǎn)為f 。（1）p結(jié)點(diǎn)為葉結(jié)點(diǎn)結(jié)點(diǎn)為葉結(jié)點(diǎn)（2）p結(jié)點(diǎn)只有右子樹結(jié)點(diǎn)只有右子樹pr或只有左子樹或只有左子樹pl（3）p結(jié)點(diǎn)既有左子樹結(jié)點(diǎn)既有左子樹pl又有右子樹又有右子樹pr44二叉排序樹刪除二叉排序樹刪除 第一種情況：第一種情況：p結(jié)點(diǎn)為葉結(jié)點(diǎn)結(jié)點(diǎn)為

25、葉結(jié)點(diǎn) 由于刪去葉結(jié)點(diǎn)后不影響整棵樹的特性，由于刪去葉結(jié)點(diǎn)后不影響整棵樹的特性，所以，只需將被刪結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針?biāo)?，只需將被刪結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針域改為空指針。域改為空指針。63421815X45二叉排序樹刪除二叉排序樹刪除 第二種情況：第二種情況：p結(jié)點(diǎn)只有右子樹結(jié)點(diǎn)只有右子樹pr或只有左子樹或只有左子樹pl，此時(shí)，只，此時(shí)，只需將需將pr或或pl替換替換f結(jié)點(diǎn)的結(jié)點(diǎn)的p子樹即可。子樹即可。63421812156342181546二叉排序樹刪除二叉排序樹刪除中序遍歷：中序遍歷：P PR S QSPRQ中序遍歷：中序遍歷：PR S Qp結(jié)點(diǎn)只有右子樹結(jié)點(diǎn)只有右子樹pr(1)SPPRQ

26、中序遍歷：中序遍歷：Q S P PRSQPR中序遍歷：中序遍歷：Q S PRp結(jié)點(diǎn)只有右子樹結(jié)點(diǎn)只有右子樹pr(2)SQPRP刪除刪除1263421812156342181547二叉排序樹刪除二叉排序樹刪除SPPLQ中序遍歷：中序遍歷：PL P S QSPLQ中序遍歷：中序遍歷：PL S Qp結(jié)點(diǎn)只有左子樹結(jié)點(diǎn)只有左子樹pl（1）SQPLP中序遍歷：中序遍歷：Q S PL PSQPL中序遍歷：中序遍歷：Q S PLp結(jié)點(diǎn)只有左子樹結(jié)點(diǎn)只有左子樹pl（2）63421815634215刪除刪除1848二叉排序樹刪除二叉排序樹刪除 第三種情況：第三種情況：p結(jié)點(diǎn)既有左子樹結(jié)點(diǎn)既有左子樹pl又有右子樹

27、又有右子樹pr ，可按中序遍，可按中序遍歷保持有序進(jìn)行調(diào)整。歷保持有序進(jìn)行調(diào)整。10362418121549二叉排序樹刪除二叉排序樹刪除FPCPRCLQQLSSL中序遍歷：中序遍歷：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍歷：中序遍歷：CL C QL Q SL S PR Fp結(jié)點(diǎn)既有左子樹結(jié)點(diǎn)既有左子樹pl又有右子樹又有右子樹pr(1)FPCPRCL中序遍歷：中序遍歷：CL C P PR FFCPRCL中序遍歷：中序遍歷：CL C PR Fp結(jié)點(diǎn)既有左子樹結(jié)點(diǎn)既有左子樹pl又有右子樹又有右子樹pr(2)50二叉排序樹刪除二叉排序樹刪除10362418121563

28、42181215刪除刪除10例例51p / 右子樹為空樹則只需重接它的左子樹q = p; p = p-lchild; delete(q);pqq52/ 左子樹為空樹只需重接它的右子樹q = p; p = p-rchild; delete(q);ppqq53q = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū)/ 左右子樹均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接*q的左子樹delete

29、(s);pqs54平衡二叉樹平衡二叉樹(AVL(AVL樹樹) )n定義：定義：平衡二叉樹又稱平衡二叉樹又稱AVL樹，樹，它或者是一棵空樹，或者是它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹具有下列性質(zhì)的二叉樹：n平衡因子平衡因子balance：結(jié)點(diǎn)左子樹與右子樹的高度差。結(jié)點(diǎn)左子樹與右子樹的高度差。即即 |左子樹深度左子樹深度-右子樹深度右子樹深度| 1左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹；所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值 155判斷下列二叉樹是否判斷下列二叉樹是否AVL樹？樹？n任一結(jié)點(diǎn)的平衡因子只能?。喝我唤Y(jié)點(diǎn)的平衡因子只能?。?1、0 或

30、或 1；否則，；否則，這棵二叉樹就失去平衡，不再是這棵二叉樹就失去平衡，不再是AVL樹；樹；n對(duì)于一棵有對(duì)于一棵有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的AVL樹，其樹，其高度保持在高度保持在O(log2n)數(shù)量級(jí)，數(shù)量級(jí)，ASL也保持在也保持在O(log2n)量級(jí)。量級(jí)。平衡二叉樹平衡二叉樹(AVL(AVL樹樹) )56平衡二叉樹平衡二叉樹(AVL(AVL樹樹) )平衡平衡旋轉(zhuǎn)旋轉(zhuǎn) 如果在一棵如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須就有可能造成失衡，此時(shí)必須重新調(diào)整樹重新調(diào)整樹的結(jié)構(gòu)的結(jié)構(gòu)，使之恢復(fù)平衡。稱調(diào)整平衡過程，使之恢復(fù)平衡。稱調(diào)整平衡過程為為平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)。L

31、L平衡平衡旋轉(zhuǎn)旋轉(zhuǎn)RR平衡平衡旋轉(zhuǎn)旋轉(zhuǎn)LR平衡平衡旋轉(zhuǎn)旋轉(zhuǎn)RL平衡平衡旋轉(zhuǎn)旋轉(zhuǎn)57若在若在A的的左子樹的左子樹上插入左子樹的左子樹上插入結(jié)結(jié)點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至2，需要進(jìn)行一次需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)。(以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）ABCABC若在若在A的的右子樹的右子樹上插入右子樹的右子樹上插入結(jié)結(jié)點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從-1增加至增加至-2，需要進(jìn)行一次需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)逆時(shí)針旋轉(zhuǎn)。(以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：ABC1）LL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：ABC平衡二叉樹平衡二叉樹(AVL(AVL樹樹) )58若在若在

32、A的的右右子樹的子樹的左左子樹上插入子樹上插入結(jié)結(jié)點(diǎn)，使點(diǎn)，使A的平衡因子從的平衡因子從-1增加至增加至-2，需要需要先進(jìn)行先進(jìn)行順順時(shí)針旋轉(zhuǎn)，再時(shí)針旋轉(zhuǎn)，再逆逆時(shí)時(shí)針旋轉(zhuǎn)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：ABCABCABC若在若在A的的左左子樹的子樹的右右子樹上插入子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至2，需要，需要先進(jìn)行先進(jìn)行逆逆時(shí)針旋轉(zhuǎn)，再時(shí)針旋轉(zhuǎn)，再順順時(shí)針旋轉(zhuǎn)。時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡二叉樹平衡二叉樹(AVL(AVL樹樹)

33、)59基本思想：基本思想：在構(gòu)造二叉排序樹的過程中，每在構(gòu)造二叉排序樹的過程中，每插入一個(gè)結(jié)點(diǎn)時(shí)，先檢查是否因插入而破壞插入一個(gè)結(jié)點(diǎn)時(shí)，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。構(gòu)造平衡二叉樹構(gòu)造平衡二叉樹(AVL(AVL樹樹) )60例：例：請(qǐng)將下面

34、序列構(gòu)成一棵請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹平衡二叉排序樹： （ 13，24，37，90，53）需要需要RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞B逆轉(zhuǎn)逆轉(zhuǎn),B為根）為根）需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞C先順后逆）先順后逆）平衡二叉樹平衡二叉樹(AVL(AVL樹樹) )61 查找分析查找分析: 在平衡樹上進(jìn)行查找的過程和二叉排序樹相同在平衡樹上進(jìn)行查找的過程和二叉排序樹相同 深度為深度為 h 的二叉平衡樹中所含結(jié)點(diǎn)的最小值的二叉平衡樹中所含結(jié)點(diǎn)的最小值 含有含有 n 個(gè)結(jié)點(diǎn)的二叉平衡樹能達(dá)到的最大深度個(gè)結(jié)點(diǎn)的二叉平衡樹能達(dá)到的最大深度 在平衡樹上進(jìn)行查找的時(shí)間復(fù)雜度為在平衡樹上進(jìn)行查找的時(shí)間復(fù)雜度為 O

35、(logn)平衡二叉樹平衡二叉樹(AVL(AVL樹樹) )62 B-B-樹樹 2 3 7 2 20 253 79 84 93 4 35 41 51 53 2 66 682 71 762 12 302 69 781 54tF F FFF FFFFFFFFFFFFFFFFabcdeghfi一棵一棵5階的階的B-樹樹 B-樹是一種 平衡平衡 的 多路多路 查找查找 樹：63 在在 m 階的階的B-樹上，每個(gè)非終端結(jié)點(diǎn)可能含有樹上，每個(gè)非終端結(jié)點(diǎn)可能含有： n 個(gè)關(guān)鍵字關(guān)鍵字 Ki（1 in） nm n 個(gè)指向記錄的指針指向記錄的指針 Di（1in） n+1 個(gè)指向子樹的指針指向子樹的指針 Ai（0i

36、n）;多叉樹的特性多叉樹的特性 B-B-樹樹64 非葉結(jié)點(diǎn)中的非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字多個(gè)關(guān)鍵字均均自小至大自小至大有序排有序排列，即：列，即：K1 K2 Kn; 且且 Ai-1 所指子樹上所有關(guān)鍵字均小于所指子樹上所有關(guān)鍵字均小于Ki; Ai 所指子樹上所有關(guān)鍵字均大于所指子樹上所有關(guān)鍵字均大于Ki;查找樹的特性查找樹的特性 B-B-樹樹65平衡樹的特性平衡樹的特性 樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上同一層次上; 根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹; 其余所有非葉結(jié)點(diǎn)均至少含有其余所有非葉結(jié)點(diǎn)均至少含

37、有 m/2 棵棵子樹，子樹，至多含有至多含有 m 棵子樹棵子樹; B-B-樹樹66從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找點(diǎn)內(nèi)進(jìn)行順序（或折半）查找 兩個(gè)過程交兩個(gè)過程交叉進(jìn)行：叉進(jìn)行： 若若查找成功查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置；的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置； 若若查找不成功查找不成功，則返回插入位置。，則返回插入位置。 B-B-樹的查找樹的查找67 在查找不成功之后，需進(jìn)行插入。顯然，關(guān)在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)，鍵字插入的

38、位置必定在最下層的非葉結(jié)點(diǎn)，有下列幾種情況：有下列幾種情況： 插入后該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm，不修改指針，不修改指針; 插入后該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n=m，則需進(jìn)行，則需進(jìn)行“結(jié)結(jié)點(diǎn)分裂點(diǎn)分裂”； 若雙親為空，則建新的根結(jié)點(diǎn)。若雙親為空，則建新的根結(jié)點(diǎn)。 B-B-樹的插入樹的插入683 階階B-樹的插入樹的插入50 20 40 80 插入關(guān)鍵字插入關(guān)鍵字 = 60, 60 80 90, 60 80 90 90 50 80 60 30 40 20 30 50 808030 50 B-B-樹的插入樹的插入69n找到待刪關(guān)鍵字所在結(jié)點(diǎn)；找到待刪關(guān)鍵字所在結(jié)點(diǎn)

39、；n 刪除該結(jié)點(diǎn)之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)刪除該結(jié)點(diǎn)之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于不能小于 m/2 -1，否則，要從其左，否則，要從其左(或右或右)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)“借調(diào)借調(diào)”關(guān)鍵字；關(guān)鍵字；n 若其左和右兄弟結(jié)點(diǎn)均無關(guān)鍵字可借若其左和右兄弟結(jié)點(diǎn)均無關(guān)鍵字可借(結(jié)結(jié)點(diǎn)中只有最少量的關(guān)鍵字點(diǎn)中只有最少量的關(guān)鍵字)，則必須進(jìn)行，則必須進(jìn)行結(jié)點(diǎn)的結(jié)點(diǎn)的“合并合并”. B-B-樹的刪除樹的刪除70B+B+樹樹 71B+樹的結(jié)構(gòu)特點(diǎn)：樹的結(jié)構(gòu)特點(diǎn)： 每個(gè)葉子結(jié)點(diǎn)中含有每個(gè)葉子結(jié)點(diǎn)中含有 n 個(gè)關(guān)鍵字和個(gè)關(guān)鍵字和 n 個(gè)指向記錄的指針；個(gè)指向記錄的指針；并且，所有葉子結(jié)點(diǎn)并且，所有葉子結(jié)點(diǎn)彼此相鏈接構(gòu)成一

40、個(gè)彼此相鏈接構(gòu)成一個(gè)有序鏈表有序鏈表，其其頭指針頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)；指向含最小關(guān)鍵字的結(jié)點(diǎn)；B+B+樹樹 72 每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵字每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵字 Ki 即即為為其相應(yīng)其相應(yīng)指針指針 Ai 所指子樹中關(guān)鍵字的最大值；所指子樹中關(guān)鍵字的最大值； 所有葉子結(jié)點(diǎn)都處在所有葉子結(jié)點(diǎn)都處在同一層次同一層次上，每個(gè)上，每個(gè)葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于 m/2 和和 m 之間。之間。B+B+樹樹 73B+B+樹的查找過程樹的查找過程n既可以進(jìn)行縮小范圍的查找，也可以進(jìn)行既可以進(jìn)行縮小范圍的查找，也可以進(jìn)行順序查找；順序查找；n 在在進(jìn)行縮小范圍進(jìn)行縮小范圍的查

41、找時(shí)，不管成功與否，的查找時(shí)，不管成功與否，都必須查到葉子結(jié)點(diǎn)才能結(jié)束；都必須查到葉子結(jié)點(diǎn)才能結(jié)束；n 若在若在結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)內(nèi)查找時(shí)，給定值查找時(shí)，給定值Ki， 則應(yīng)繼續(xù)在則應(yīng)繼續(xù)在 Ai 所指子樹中進(jìn)行查找。所指子樹中進(jìn)行查找。74B+B+樹的插入和刪除樹的插入和刪除n類似于類似于B-樹樹n必要時(shí)，也需要進(jìn)行結(jié)點(diǎn)的必要時(shí)，也需要進(jìn)行結(jié)點(diǎn)的“分裂分裂”或或“歸并歸并”。758.4 8.4 哈希表查找哈希表查找( (雜湊法、散列法雜湊法、散列法) )哈希表與哈希方哈希表與哈希方法法1常用的哈希函數(shù)常用的哈希函數(shù)2處理沖突的方法處理沖突的方法3哈希表的查找分析哈希表的查找分析476 以上兩節(jié)討論的表

42、示查找表的各種結(jié)構(gòu)的共以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：同特點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系。不存在一個(gè)確定的關(guān)系。 查找的過程查找的過程為給定值依次和關(guān)鍵字集合中為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較。各個(gè)關(guān)鍵字進(jìn)行比較。 查找的效率查找的效率取決于和給定值進(jìn)行比較的關(guān)取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。鍵字個(gè)數(shù)。77 用這類方法表示的查找表，其平均查找用這類方法表示的查找表，其平均查找長度都不為零長度都不為零 只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，中的位置， 對(duì)于頻繁使用的

43、查找表，希望對(duì)于頻繁使用的查找表，希望 ASL = 0。 即要求：即要求：記錄在表中位置和其關(guān)鍵字之間記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系存在一種確定的關(guān)系。78若以下標(biāo)為若以下標(biāo)為000 999 的順序表表示之。的順序表表示之。例如：為每年招收的例如：為每年招收的 1000 名新生建立一張查名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為 xx000 xx999 (前兩位為年份前兩位為年份)。則查找過程可以簡單進(jìn)行：取給定值（學(xué)號(hào)）則查找過程可以簡單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，的后三位，不需要經(jīng)過比較便可直接從順序表不需要經(jīng)過比較便可直接從順

44、序表中找到待查關(guān)鍵字。中找到待查關(guān)鍵字。79但是，對(duì)于但是，對(duì)于動(dòng)態(tài)查找表動(dòng)態(tài)查找表而言，而言，因此在一般情況下，需在關(guān)鍵字與記錄在表因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以以 f(key) 作為關(guān)鍵字為作為關(guān)鍵字為 key 的記錄在表中的位置，的記錄在表中的位置，通常稱這個(gè)函數(shù)通常稱這個(gè)函數(shù) f(key) 為哈希函數(shù)。為哈希函數(shù)。1) 表長不確定；表長不確定；2) 在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。圍，而不知道確切的關(guān)鍵字。80Zhao, Qian, Sun, Li

45、, Wu, Chen, Han, Ye, Dei 例如：對(duì)于如下例如：對(duì)于如下 9 個(gè)關(guān)鍵字個(gè)關(guān)鍵字設(shè)設(shè) 哈希函數(shù)哈希函數(shù) f(key) = (Ord(第一個(gè)字母第一個(gè)字母) -Ord(A)+1)/2 ChenZhaoQianSunLiWuHanYeDei問題問題: 若添加關(guān)鍵字若添加關(guān)鍵字 Zhou , 怎么辦？怎么辦？能否找到另一個(gè)哈希函數(shù)？能否找到另一個(gè)哈希函數(shù)？811) 哈希哈希(Hash)函數(shù)是一個(gè)函數(shù)是一個(gè)映象，映象，即：即： 將關(guān)鍵字的集合映射到某個(gè)地址集合上，將關(guān)鍵字的集合映射到某個(gè)地址集合上， 它的設(shè)置很靈活，只要這個(gè)地址集合的它的設(shè)置很靈活，只要這個(gè)地址集合的 大小不超出允

46、許范圍即可大小不超出允許范圍即可;2) 由于哈希函數(shù)是一個(gè)由于哈希函數(shù)是一個(gè)壓縮映象，壓縮映象，因此，因此，在一般情況下，很容易產(chǎn)生在一般情況下，很容易產(chǎn)生“沖突沖突”現(xiàn)象，現(xiàn)象，即：即： key1 key2，而而 f(key1) = f(key2)。823) 很難很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。使沖突盡可能少地產(chǎn)生。 因此，在構(gòu)造這種特殊的因此，在構(gòu)造這種特殊的“查找表查找表” 時(shí)，除了需要選擇一個(gè)時(shí)，除了需要選擇一個(gè)“好好”(盡可能少盡可能少產(chǎn)生沖突產(chǎn)生沖突)的的哈

47、希函數(shù)哈希函數(shù)之外之外;還需要找到一還需要找到一種種“處理沖突處理沖突” 的方法。的方法。83哈希表的定義哈希表的定義: : 根據(jù)設(shè)定的根據(jù)設(shè)定的哈希函數(shù)哈希函數(shù) H(key) 和所選中的和所選中的處處理沖突的方法理沖突的方法，將一組關(guān)鍵字，將一組關(guān)鍵字映象到映象到一個(gè)有一個(gè)有限的、地址連續(xù)的地址集限的、地址連續(xù)的地址集 (區(qū)間區(qū)間) 上，并以關(guān)上，并以關(guān)鍵字在地址集中的鍵字在地址集中的“象象”作為相應(yīng)記錄在表作為相應(yīng)記錄在表中的中的存儲(chǔ)位置存儲(chǔ)位置，如此構(gòu)造所得的查找表稱之，如此構(gòu)造所得的查找表稱之為為“哈希表哈希表”。84哈希表與哈希方法哈希表與哈希方法 需解決兩個(gè)問題：需解決兩個(gè)問題：（

48、1）構(gòu)造好的哈希函數(shù)：構(gòu)造好的哈希函數(shù)：所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度。所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度。所選函數(shù)對(duì)關(guān)鍵字計(jì)算出的地址，應(yīng)在哈希地所選函數(shù)對(duì)關(guān)鍵字計(jì)算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。址集中大致均勻分布，以減少空間浪費(fèi)。（2）制定解決沖突的方案。制定解決沖突的方案。85哈希表與哈希方法哈希表與哈希方法 例如：已知例如：已知ki：12，33，65，9，38，71，82，63，75，15，24，57，54，88，98；分布在；分布在20個(gè)單元個(gè)單元中，一個(gè)單元存放一個(gè)關(guān)鍵字（中，一個(gè)單元存放一個(gè)關(guān)鍵字（m=20），如果選），如果選H(ki)=ki/5

49、（除法求整數(shù)）作為哈希函數(shù)，則得到（除法求整數(shù)）作為哈希函數(shù)，則得到的的Hash表為：表為：0123456789101112131415161718199121524333854576365717582889886常用的哈希函數(shù)常用的哈希函數(shù) 直接定址法直接定址法 除留余數(shù)法除留余數(shù)法乘余取整法乘余取整法數(shù)字分析法數(shù)字分析法平方取中法平方取中法折疊法折疊法(Folding)87常用的哈希函數(shù)常用的哈希函數(shù)直接定址法直接定址法 Hash(key)=akey+b (a、b為常數(shù)為常數(shù)) 即取關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址即取關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址 特點(diǎn)特點(diǎn)：所得地址集合與關(guān)鍵字集合大小

50、相等，所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突。不會(huì)發(fā)生沖突。適用情況？適用情況？事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。 88常用的哈希函數(shù)常用的哈希函數(shù)例例 關(guān)鍵字集合為關(guān)鍵字集合為100，300，500，700，800，900，選取哈希函數(shù)為：選取哈希函數(shù)為：Hash(key)=key/100，則所建立，則所建立的哈希表如下：的哈希表如下： Hash(100)=100/100=1 Hash(300)=300/100=3 Hash(500)=500/100=5 0 1 2 3 4 5 6 7 8 9 Hash(700)=700/

51、100=7 Hash(800)=800/100=8 Hash(900)=900/100=9100900300500700 80089常用的哈希函數(shù)常用的哈希函數(shù)除留余數(shù)法除留余數(shù)法Hash(key)=key mod p (p是一個(gè)整數(shù)是一個(gè)整數(shù)) 即取關(guān)鍵字除以即取關(guān)鍵字除以p的余數(shù)作為哈希地址。的余數(shù)作為哈希地址。 選取合適的選取合適的p很重要，若哈希表表長為很重要，若哈希表表長為m，則，則要求要求pm，且接近，且接近m或等于或等于m。p一般選取一般選取質(zhì)質(zhì)數(shù)數(shù)，也可以是不包含小于，也可以是不包含小于20質(zhì)因子的合數(shù)。質(zhì)因子的合數(shù)。 90 給定一組關(guān)鍵字為給定一組關(guān)鍵字為: 12, 39,

52、18, 24, 33, 21，若取若取 p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為則他們對(duì)應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3例如：例如：為什么要對(duì)為什么要對(duì) p p 加限制？加限制？ 可見，若可見，若 p 中含質(zhì)因子中含質(zhì)因子 3, 則所有含質(zhì)因子則所有含質(zhì)因子 3 的的關(guān)鍵字均映射到關(guān)鍵字均映射到“3 的倍數(shù)的倍數(shù)”的地址上，從而增的地址上，從而增加了加了“沖突沖突”的可能。的可能。91除留余數(shù)法舉例除留余數(shù)法舉例已知一組關(guān)鍵字已知一組關(guān)鍵字19,14,23,01,68,20,84,27,55,11,10,79設(shè)表長設(shè)表長m為為16，試構(gòu)造哈希表。，試構(gòu)造哈希表。 分析：分析：

53、取哈希函數(shù)取哈希函數(shù) H(key) = key mod p , 且取且取p=13, (13為小于為小于16的最大素?cái)?shù)的最大素?cái)?shù))， 則有哈希函數(shù)則有哈希函數(shù) H(key) = key mod 13。 由此由此,H(19) = 6, H(14) = 1, H(23) = 10, H(01)=1, ,H(68) = 3, H(20) = 7, H(84) = 5, H(27) = 1, H(55) = 3, 可見在利用以上函數(shù)構(gòu)造哈希表可見在利用以上函數(shù)構(gòu)造哈希表時(shí)，發(fā)生了沖突。其中，時(shí)，發(fā)生了沖突。其中，14，01，27，79為同義為同義詞，詞，.92常用的哈希函數(shù)常用的哈希函數(shù)乘余取整法乘余取

54、整法Hash(key)= B*(A*key mod 1) (A、B均為均為常數(shù)，且常數(shù)，且0A1，B為整數(shù)為整數(shù)) B取什么值并不關(guān)鍵，但取什么值并不關(guān)鍵，但A的選擇卻很重要，的選擇卻很重要，最佳的選擇依賴于關(guān)鍵字集合的特征。最佳的選擇依賴于關(guān)鍵字集合的特征。一般取一般取A= 0.6180339較為理想。較為理想。93常用的哈希函數(shù)常用的哈希函數(shù)數(shù)字分析法數(shù)字分析法 對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址作哈希地址例例 有有80個(gè)記錄，關(guān)鍵字為個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地位十進(jìn)制數(shù)，哈希地址為址為2位十進(jìn)制數(shù)位十進(jìn)制數(shù)8 1 3

55、4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析：分析： 只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 數(shù)字分布近乎隨機(jī)數(shù)字分布近乎隨機(jī)所以：取所以：取任意兩位或兩位任意兩位或兩位 與另兩位的疊加作哈希地址與另兩位的疊加作哈希地址94常用的哈希函數(shù)常用的哈希函數(shù)數(shù)字分析法數(shù)字分析法 對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址作哈希地址例例 有

56、有80個(gè)記錄，關(guān)鍵字為個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地位十進(jìn)制數(shù)，哈希地址為址為2位十進(jìn)制數(shù)位十進(jìn)制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 適用情況適用情況:能預(yù)先估計(jì)出全部關(guān)鍵碼能預(yù)先估計(jì)出全部關(guān)鍵碼的每一位上各種數(shù)字出現(xiàn)的每一位上各種數(shù)字出現(xiàn)的頻度，不同的關(guān)鍵碼集的頻度，不同的關(guān)鍵碼集合需要重新分析。合需要重新分析。95常用的哈希函數(shù)常用的哈希函數(shù)平方取中法平方取中法 取關(guān)鍵字平方

57、后的中間幾位為哈希地址取關(guān)鍵字平方后的中間幾位為哈希地址 事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大。事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大。適用情況適用情況:例：散列地址為例：散列地址為2位，則關(guān)鍵碼位，則關(guān)鍵碼1234的散列地址為：的散列地址為：(1234)2152275696常用的哈希函數(shù)常用的哈希函數(shù)6. 折疊法折疊法(Folding)將關(guān)鍵字自左到右分成位數(shù)相等的幾部分，將關(guān)鍵字自左到右分成位數(shù)相等的幾部分，最后一部分位數(shù)可以短些，然后將這幾部分最后一部分位數(shù)可以短些，然后將這幾部分疊加求和。疊加求和。有兩種疊加方法：有兩種疊加方法： （1） 移位法移位法 。 （2） 間界疊

58、加法間界疊加法 。適用情況適用情況:關(guān)鍵碼位數(shù)很多，事先不知道關(guān)鍵碼的分布。關(guān)鍵碼位數(shù)很多，事先不知道關(guān)鍵碼的分布。 97常用的哈希函數(shù)常用的哈希函數(shù) 例例 關(guān)鍵字為關(guān)鍵字為 ：0442205864，哈希地址位數(shù)為，哈希地址位數(shù)為45 8 6 44 2 2 0 0 41 0 0 8 8H(key)=0088移位疊加移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加間界疊加98隨機(jī)數(shù)法隨機(jī)數(shù)法設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = Random(key)其中，其中，Random 為偽隨機(jī)函數(shù)為偽隨機(jī)函數(shù) 通常，此方法用于對(duì)長度不等的關(guān)鍵字構(gòu)造哈希函

59、數(shù)。通常，此方法用于對(duì)長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。99 實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字包括關(guān)鍵字的范圍和形態(tài)的范圍和形態(tài))，總的原則是總的原則是使產(chǎn)生沖突的可能使產(chǎn)生沖突的可能性降到盡可能地小。性降到盡可能地小。100處理沖突的方法處理沖突的方法 開放定址法開放定址法 由關(guān)鍵字得到的哈希地址一旦產(chǎn)生了由關(guān)鍵字得到的哈希地址一旦產(chǎn)生了沖突沖突，就去尋找下一個(gè)空的哈希地址。就去尋找下一個(gè)空的哈希地址。 即即 Hi=(H(key)+di)MOD m，i=1,2,k(k m-1)其中：其

60、中：H(key)為為哈希函數(shù)哈希函數(shù)m為為哈希表表長哈希表表長di為為增量序列增量序列101處理沖突的方法處理沖突的方法 分類分類 線性探測法線性探測法 di=1,2,3,，m-1 二次探測法二次探測法di=1,-1,2,-2,3,k(k m/2) 雙哈希函數(shù)探測法雙哈希函數(shù)探測法 di=偽隨機(jī)數(shù)序列偽隨機(jī)數(shù)序列102例如例如: 關(guān)鍵字集合關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 設(shè)定哈希函數(shù)設(shè)定哈希函數(shù) H(key) = key MOD 11 ( 表長表長=11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10190123