Searching 查找運算是計算機中最常用的操作課件

1、第九章. 查找 （Chapter 9. Searching) 查找運算是計算機中最常用的操作之一。有人統計過，計算機大約有40%的運算是與查找相關的。 數據元素（或記錄）的某個數據項，能用來標識一個數據元素。若能唯一的標識一個數據元素， 則稱為主關鍵字（primary key），反之則為次關鍵字（secondary key）。關鍵字（key）查找表（search table）9.1 靜態(tài)表的查找查找（searching） 根據某個給定的值，在查找表中找尋關鍵字等于給定值的數據元素（或記錄）。若表中存在這樣的數據元素，則稱查找是成功的，查找結果即為查找到的數據元素；反之則稱查找是不成功的，此時查

2、找結果為空。 由同一類型的數據元素（或記錄）構成的集合。表中的元素基本上是固定的，這類查找表稱為靜態(tài)查找表（static search table）；若在查找過程中將不存在的元素插入查找表中，則稱這類查找表為動態(tài)查找表（dynamic search table）。 實際查找時，通常將給定值放在第 0 個記錄處，然后從后向前查找，直到找到所查記錄為止，找不到則返回結果 0。因為記錄 0 像哨兵一樣看守著查找表下界，所以不會越界。typedef struct keytype key; . . . . . . elemtype;一、無序表的查找：查找表中的各元素（或記錄）的關鍵字的值是無序的。typ

3、edef struct elemtype * elem; int length; sstable;int seqsearch ( sstable R, keytype K ) R.elem0.key := K; for ( i = R.length ; R.elemi.key != K ; i - ) ; return i;查找表的長度為 n：查找性能分析：平均查找長度（average search length） 為了確定記錄在查找表中的位置，需與給定值比較的關鍵字的個數的期望值稱為平均查找長度。在等概率情況下，順序查找有序表的平均查找長度為： ASL成功 = （n+1) / 2 和 ASL

4、不成功 = （n+2) / 2 。有序表的查找比較好的方法是折半查找（binary search）： 將給定值與中間的記錄進行比較，若找到則查找成功；否則若給定值比中間記錄小，則對前一半子表進行折半查找，反之則對后一半子表進行折半查找。若在查找過程中，遇到查找子表的上界小于下界，則表示查找失敗。int seqsearch ( sstable R, keytype K ) R.elem0.key := K; for ( i = R.length ; R.elemi.key K ; i - ) ; if (R.elemi.key=K) return i; else return 0;int bin

5、search ( sstable R , keytype K ) low = 1; high = R.length; while ( low K ) high = mid-1; else low = mid+1; return 0;查找性能分析： 折半查找每次只查表的一半，其所有記錄的查找路徑構成一棵二叉樹，稱為折半查找樹（或判定樹），每次查找只走了該樹的一條分支，故平均查找長度不超過 log2n + 1。 有一組記錄的關鍵字為1，2，3，4，5，6，7，8，求其在等概率情況下查找成功的平均查找長度： 例：42516378其查找樹如左圖所示：ASL成功 = = 21 / 8 。1*1+2*2+

6、3*4+4*18 有序表的查找也可用其它的查找方法，如費波拉契查找（Fibonacci search）。 設查找表記錄數為某個費波拉契數減一，即 n=Fu-1，則可將給定值與第Fu -1個記錄比較，若比其小，則在1 Fu -1-1 記錄間查找，否則在Fu -1+1 Fu-1記錄間查找 。如下圖所示：4251637 若有序表的關鍵字是均勻分布的，則還可用插值查找方法，其平均性能在記錄數較多時比折半查找好：將給定值先與第 i 個記錄比較，則 i = n。K- rL.keyrH.key- rL.key作 業(yè)25. 查找序列以帶頭結點的單鏈表表示，各結點中設一個訪問頻度，初始值為 0，每次查找成功后該

7、結點頻度值增加 1。試給出算法，在每次查找后查找序列均按訪問頻度從大到小排列。 查找效率最高即平均查找長度最小，根據前面所學知識，我們可以給出有序表在非等概率情況下應遵循的兩個原則：1、最先訪問的結點應是訪問概率最大的結點；2、每次訪問應使結點兩邊尚未訪問的結點的被訪概 率之和盡可能相等。三、靜態(tài)樹表的查找： 前面介紹的有序表查找都是在“等概率”情況下的，若在非等概率情況下應該怎樣查找才能使查找效率更高了？ 這樣的樹稱為靜態(tài)最優(yōu)查找樹（static optimal search tree），構造這樣一棵樹的時間代價太大，亦即時間復雜度很大，因此我們通常是構造次優(yōu)查找樹（nearly optim

8、al search tree），構造它的時間代價遠遠低于構造最優(yōu)查找樹，但查找性能只比最優(yōu)查找樹差1%2%，很少差3%以上。 這兩個原則可用一句話來表示，即判定樹為帶權內路徑長度之和最小的二叉樹，亦即： PH = wihi 最小，其中 n 為有序表長度，hi 為第 i 個結點在判定樹上的層次數，wi = cpi，c 為某個常數，pii =1n為第 i 個結點的查找概率。次優(yōu)查找樹的構造： 設有序表每個記錄的權值為 wl,wl+1,wh，第一個應訪問的結點號為 i ，則有：pi = wj - wj 最小，即 pi = Min pj 再分別對 rl,rl+1,ri-1 和 ri+1,ri+2,rh

9、 分別構造次優(yōu)查找樹。j =i +1j =lhi - lljh為便于計算，引入累計權值swi=wj，并設wl-1=swl-1=0，則：j=liwjj =i +1hwjj =li -1swi-1 - swl-1 =swh - swi =pi = | swh + swl-1 - swi - swi-1 |35689311013最大關鍵字起始地址索引表231611356283125194157689375886913245678910111213141516順序表9.2 動態(tài)表的查找一、二叉排序樹： 二叉排序樹（binary sort tree）或者為空樹，或者為這樣一棵樹：根結點的左子樹的所有結點

10、的關鍵字值均比根結點的關鍵字值小；根結點的右子樹的所有結點的關鍵字值均比根結點的關鍵字值大；根結點的左右子樹也是二叉排序樹。 二叉排序樹是動態(tài)查找樹，即在查找時將未找到的給定值的記錄插入到查找樹中，查找樹是動態(tài)生成的。 54 32 25 9 94 73 68有查找請求 54、32、54、25、73、25、94、68、32、73、9，查找結果如下：例：查找失敗查找失敗查找成功查找失敗查找失敗查找成功查找失敗查找失敗查找成功查找成功查找失敗二叉排序樹的查找：若當前結點指針為空或當前結點為所找結點則返回當前指針；若當前結點關鍵字值比給定值大則繼續(xù)查找當前結點的左子樹；否則就繼續(xù)查找當前結點的右子樹。

11、二叉排序樹的插入：先用給定值查找二叉排序樹，查找成功則返回所找結點指針；否則在找不到時的葉結點的左子樹或右子樹處插入給定值記錄。（新插入的結點一定是葉子結點）二叉排序樹的刪除：若將刪除的結點是葉子結點，直接刪除即可；若將刪除的結點只有左子樹或只有右子樹，則可用左孩子或右孩子直接替換將要刪除結點位置；若將刪除的結點左、右子樹均存在，則可用將要刪除結點左子樹的最右結點（關鍵字值最大的結點）替換將要刪除結點，用替換結點的左子樹（若存在）替換“替換結點”。二叉排序樹的查找分析：ASL與二叉排序樹的高度有關。由于二叉排序樹是根據查找請求序列建立的，因此很可能退化成為線性表（什么情況下？），如何解決這一問

12、題呢？二、平衡二叉樹： 平衡二叉樹（balanced binary tree) 又稱 AVL樹(G. M. Adelson-Velskii & Y. M. Landis. An algorithm for the organization of information. Soviet Math. Dokl., 3:1259-1262, 1962.) ，它具有如下性質：或者為空樹，或者根結點的左、右子樹也均為平衡二叉樹，且左、右子樹的樹高之差的絕對值不超過1。平衡因子（balance factor）：結點的左子樹高度減去右子樹高度的值稱為該結點的平衡因子。因此平衡二叉樹也可以這樣定義：平衡二叉樹

13、是所有結點的平衡因子的絕對值均小于2的二叉樹。我們談論的平衡二叉樹其實是平衡二叉排序樹。平衡二叉樹的插入：平衡二叉樹插入時分為四種類型：LL型、LR型、RL型和RR型。 1、將新的結點插入在平衡二叉樹中，沿著剛插入的結點到根結點的路徑修改所經過結點的平衡因子，直到找到某結點A 的 平衡因子為 2 或修改完根結點的平衡因子后仍為平衡二叉樹。 2、若結點A 的平衡因子為2 ，則需進行調整，設 A 的兒子和孫子（剛經過的結點）分別為 B 和 C，則有： A B C A C BLR0-12000 A B CRL0 1-2 B C A000 A B C A B CLL012000 A B C C B A

14、RR0-1-2000# JAN FEB APR AUG MAR JUN MAY JUL JAN FEB MAR APR MAY JUN JUL AUG SEP OCT 有一組關鍵字序列JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV、DEC，以此建立 AVL 樹。 例：LR AUG0 APR-1 FEB2 OCT0 SEP1 MAY-2 SEP OCT JAN FEB MAR APR MAY JUN JUL AUG NOV DEC NOV SEP OCT JAN FEB MAR APR MAY JUN JUL AUGRLRR OCT1 MAR-1 JAN-

15、2含有 n 個關鍵字的平衡二叉樹的最大深度為多少？平衡二叉樹的查找分析： 用 Nh 表示深度為 h 的平衡二叉樹含有的最少結點數，則：N0 = 0、N1 = 1、N2 = 2、Nh = Nh -1 + Nh -2 + 1 = h+2/5-1，其中 = （1 +5 ）/ 2，則含有 n 個結點的平衡二叉樹的最大深度為 log(5 ( n + 1) - 2，因此，平衡二叉樹查找的時間復雜度為 O ( log n )。三、B 樹 B 樹是一種平衡的多路查找樹，主要應用在文件系統中。一棵 m 階的 B 樹，或為空樹，或為滿足下列特性的 m 叉樹： 1、樹中每個結點最多有 m 棵子樹； 2、若根結點不是

16、葉子結點，則最少有兩棵子樹；3、除根之外的所有非終端結點最少有 m / 2 棵子樹；4、所有非終端結點包含 （n,A0,K1,A1,K2,Kn,An）信息數據； 5、所有葉子結點在同一層上，且不帶信息。 其中n為結點中關鍵字個數，Ai為指向子樹的指針，Ki為關鍵字。B 的查找： B 樹是一棵平衡的多路排序樹，只是每個結點的關鍵字不只一個，因此整棵樹的查找方法與二叉排序樹的查找相似，只需對每個結點內部實行順序查找。 具有 N 個關鍵字的 B 樹深度不超過 ( log m / 2 ( N+1 ) / 2 ) + 1。2、被刪關鍵字所在結點的關鍵字個數 = m / 2 - 1 ，而與該結點相鄰的兄弟

17、結點的關鍵字個數 m / 2 ，則需將其兄弟結點中靠近該結點的關鍵字上移至父母結點中，再從父母結點中下移一個緊挨剛才上移關鍵字的關鍵字到該結點中，然后從該結點中刪去該關鍵字即可；3、被刪關鍵字所在結點及其相鄰的兄弟結點的關鍵字個數均等于 m / 2 - 1，設其父母結點指向其兄弟結點的指針為 Ai ，則從該結點中刪除該關鍵字后，將該結點中剩余的關鍵字和父母結點中的 Ki 關鍵字一起合并到其右兄弟（無右兄弟則為左兄弟）結點中即可。四、B + 樹： B+ 樹是B 樹的變形，廣泛應用在文件系統中，特別是數據庫的 VSAM 文件系統中。一棵 m 階 B+ 樹與一棵 m 階 B 樹的不同之處在：1、有

18、n 棵子樹的結點中有 n 個關鍵字； 2、所有葉子結點中包含了全部關鍵字的信息及指向這些關鍵字記錄的指針，且葉子結點以關鍵字大小自小至大順序鏈接；3、所有非終端結點可以看成是索引部分，其中只含有其子樹中最大（或最小）關鍵字。 其實 B+ 樹已不是一棵真正意義上的樹型結構了，其終端結點已連成了線性有序表。 鍵樹（key tree）又稱數字查找樹（digital search tree），它的每個結點只包含組成關鍵字的字符或數字。鍵樹主要用來存儲一些關鍵字表或標識符表，有利于這些關鍵字的查找。 鍵樹的常用存儲方式有兩種： 1、孩子兄弟的二叉樹表示法（雙鏈樹）； 2、多重鏈表表示法（Trie 樹）。

19、五、鍵樹：作 業(yè)27. 試從空樹開始，按以下順序向2-3樹中插入關鍵字建樹：20，30，50，52，60，68，70。如果此后再刪去50和68，畫出每一步執(zhí)行后的狀態(tài)。9.3 散列表查找 前面所介紹的查找方法的查找效率各不相同，且相適應的查找表也不一樣，但都有一個共性，即平均查找長度不會為 1。那么有沒有辦法使平均查找長度等于 1，即一次查找成功呢？ 散列表（Hash table）的查找就是為了解決這個問題而提出的。 散列表是如此構造的：給定一個線性表空間，選取一 個自變量為關鍵字的映射函數，其函數值為關鍵字在線性表空間中的存儲位置，關鍵字經該函數映射后即可存儲到線性表空間中；查找時也用相同的

20、方法即可找到該記錄。 該線性表空間即稱為散列表（也叫哈稀表），所選取的函數稱為散列函數（Hash function），得到的函數值稱為散列地址，得到散列地址的過程稱為哈稀造表或散列。理論上散列表查找成功的平均查找長度 ASL成功 = 1。 但實際上經常會遇見這樣的情況：不同的兩個關鍵字經過散列函數運算后所得到的散列地址相同，這種現象稱為沖突（collision），而產生沖突的兩個關鍵字對該散列函數而言稱為同義詞（synonym）。 我們應盡可能選取沖突少的散列函數，但不能完全避免沖突的產生，而有了沖突就需要找相應的解決辦法。 構造散列函數的方法很多，原則是希望構造的散列函數是均勻的（unifo

21、rm），亦即經散列函數映象到地址集合中的任何一個地址的概率是相等的，這樣做能盡可能減少沖突。散列函數的構造方法：最常用的散列函數構造方法有以下幾種：1、直接定址法：H( key ) = a * key + b， a、b為常數；2、數字分析法：分析關鍵字，找出其中幾位數字作散列地址；3、平方取中法：關鍵字平方后中間幾位數字與所有數字相關，可選取來作為散列地址；4、折疊法：將關鍵字分割成位數相同的幾部分相疊加作為散列地址；5、除留余數法：H( key ) = key MOD p， pm，m 為比散列表長度小的數；6、偽隨機數法：選取一個用關鍵字作為種子的偽隨機數發(fā)生器生成散列地址。 與構造散列函數

22、一樣，解決沖突的方法也很多，原則是盡可能避免產生二次聚集的情況不同散列地址的記錄間因解決沖突而產生新的沖突的現象。解決沖突的方法：最常用的解決沖突方法有以下幾種：1、開放定址法：Hi =(H(key) + di) MOD m, i = 1,2, k (km)；其中 H(key) 為散列函數，m 為散列表長，di 為增量序列，取值為：、 di =1,2,m-1，稱為線性探測（linear probing）再散列； 、 di = 12, -12,22, -22,k2 ( km/2 )，稱為二次探測（quadratic probing）再散列； 、 di = 偽隨機數，稱為偽隨機探測（random

23、probing）再散列；2、再散列法：Hi =RHi(key), i =1,2,k，RHi為不同的散列函數；3、鏈地址法：散列表設立指針，將所有散列地址為此位置的關鍵字記錄用單鏈表形式存儲起來；4、公共溢出區(qū)法：建立公共溢出區(qū)，將所有發(fā)生沖突的關鍵字記錄存儲到公共溢出區(qū)中去。散列函數的查找及分析： 散列表的查找過程與散列表的建立過程相同：利用建表時的散列函數和解決沖突的方法，逐步去進行查找，直到找到該記錄或找不到該記錄（該單元為空或空指針）為止。 因此，在刪除記錄時，不是將該位置置為空，而是將其置為“被刪除”，否則查找鏈就會斷。 一般的，關鍵字數目一定，散列表空間越大，沖突相對越少。裝填因子（load factor）： = 表中填入的記錄數散列表長度 即越小，發(fā)生沖突的可能性就越?。?越大，發(fā)生沖突的可能性就越大。理論上查找成功的平均查找長度為：線性探測再散列： ASL ( 1 + 1 / ( 1 - ) / 2鏈地址： ASL 1 + / 2理論上查找不成功的平均查找長度為：線