1、第9章 查找學(xué)習(xí)要點(diǎn): 熟練掌握順序表和有序表的查找方法熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法熟練掌握二叉排序樹的構(gòu)造和查找方法掌握二叉平衡樹的維護(hù)平衡方法熟練掌握哈希表的構(gòu)造方法掌握描述查找過程的判定樹的構(gòu)造方法何謂查找表？ 由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。特點(diǎn)：數(shù)據(jù)元素的類型相同；結(jié)構(gòu)松散先后次序無關(guān)緊要，只關(guān)心是否在集合內(nèi)。對查找表經(jīng)常進(jìn)行的操作：查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；檢索某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一個數(shù)據(jù)元素；從查找表中刪去某個數(shù)據(jù)元素。查找表可分為兩類：靜態(tài)查找：僅作查詢和檢索操作的查找表。動態(tài)查找：有時在查詢之后，還需要將“查詢”結(jié)果

2、為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。關(guān)鍵字：是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(識別)一個數(shù)據(jù)元素(或記錄)。若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”。若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”?？忌呖汲煽儽碇麝P(guān)鍵字次關(guān)鍵字查找： 根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素(記錄)。若查找表中存在這樣一個記錄，則稱“查找成功”，查找結(jié)果：給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”。如何進(jìn)行查找？查找的方法取

3、決于查找表的結(jié)構(gòu)。由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。為了提高查找的效率， 需要在查找表中的元素之間人為地附加某種確定的關(guān)系 用另外一種結(jié)構(gòu)(如，線性結(jié)構(gòu)、樹結(jié)構(gòu)等)來表示查找表。9.1 靜態(tài)查找表抽象數(shù)據(jù)類型靜態(tài)查找表的定義：ADT StaticSearchTable 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識數(shù)據(jù)元素。 數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合。 基本操作P： Create(&ST, n); Destroy(&ST); Search(ST, key); Traverse(ST, Visit(); ADT S

4、taticSearchTable靜態(tài)查找表的順序存儲結(jié)構(gòu)：typedef struct keyType key; / 關(guān)鍵字域 / 其它屬性域 ElemType ;typedef struct ElemType *elem; / 數(shù)據(jù)元素存儲空間基址，建表時 /按實(shí)際長度分配，0號單元留空 int length; / 表的長度 SSTable;9.1.1 順序表的查找以順序表表示靜態(tài)查找表, 稱為順序查找表?；仡欗樞虮淼牟檎襥nt LocateElem_Sq(L, e, compare( )過程：ST.elem假設(shè)給定值 e=64,要求 ST.elemk = e, 問: k = ?kkint

5、location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem; while ( k=L.length & !(*compare)(*p+,e) k+; if ( k= L.length) return k; else return 0; /locationST.elemiST.elemi60ikey=64key=60i64監(jiān)視哨int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函

6、數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時，i為0 / Search_Seq分析順序查找的時間性能：定義： 查找算法的平均查找長度(Average Search Length) ，為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值：其中: n 為表長，Pi 為查找表中第i個記錄的概率， 且 ，Ci為找到該記錄時，曾和給定值 比較過的關(guān)鍵字的個數(shù)。對順序表而言，Ci = n-i+1ASL = n

7、P1 +(n-1)P2+.+2Pn-1+Pn在等概率查找的情況下 ，順序表查找的平均查找長度為：在不等概率查找的情況下，ASLss 在PnPn-1P2P1 時取極小值。 若查找概率無法事先測定，則查找過程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。當(dāng)查找不成功的情況不能忽視時，且等概率情況下 = =3(n+1)/4忽略查找不成功的情況順序查找的優(yōu)點(diǎn)：算法簡單，適應(yīng)面廣！ 缺點(diǎn)：平均查找長度較大，特別是n很大時， 查找效率低！9.1.2 有序表的查找若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。例如：key=64的查找過程如下ST.elemST.leng

8、thlowhighmidlow mid high midlow 指示查找區(qū)間的下界high 指示查找區(qū)間的上界mid = (low+high)/2568064int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low 50時，可得近似結(jié)果：注意：折半查找只適用于等概率的有序表，且限于 順序存儲結(jié)構(gòu)！9.1.3 靜態(tài)樹表的查找在不等概率查找的情況下，折半查找不是有序表最好的查找方法。例如：關(guān)鍵字: A B C D E Pi： 0.2 0.3 0.05 0.3 0.15 Ci： 2

9、 3 1 2 3此時，ASL=20.2+30.3+10.05+20.3+30.15=2.4若改變Ci的值 2 1 3 2 3則，ASL=20.2+10.3+30.05+20.3+30.15=1.9定義：使帶權(quán)內(nèi)路徑長度之和PH值： 達(dá)最小的判定樹稱為靜態(tài)最優(yōu)查找樹。其中，hi為第i個結(jié)點(diǎn)在二叉樹上的層次數(shù)； wi = pi，稱為結(jié)點(diǎn)的權(quán)值。次優(yōu)二叉樹的構(gòu)造方法：選擇樹的根結(jié)點(diǎn)ri, 使 達(dá)最??；分別對子序列rl,rl+1,ri-1和ri+1,ri+2,rh構(gòu)造次優(yōu)查找樹，并分別設(shè)為根結(jié)點(diǎn)ri的左右子樹。為便于計(jì)算，引入累計(jì)權(quán)值和 并設(shè) wl-1 = 0 和 swl-1 = 0, 則推導(dǎo)可得例如

10、：023811151823lh211812431018h9608EC21Ah53lhG3013wl-1 = 0swl-1 = 0所得次優(yōu)二叉樹為：ECGABDF 查找比較“總次數(shù)” = 32+41+25+33 +14+33+25 = 52 查找比較“總次數(shù)” = 32+21+35+13 +34+23+35 = 59和折半查找相比較DBACFEG構(gòu)造次優(yōu)二叉樹的算法：Status SecondOptimal(BiTree &T, ElemType R, float sw, int low, int high) / 由有序表Rlow.high及其累計(jì)權(quán)值表sw遞歸構(gòu)造次優(yōu)查找樹T。 選擇最小的Pi

11、值； if (!(T = (BiTree)malloc(sizeof(BiTNode) return ERROR; T-data = Ri; / 生成結(jié)點(diǎn) if (i=low) T-lchild = NULL; / 左子樹空 else SecondOptimal(T-lchild, R, sw, low, i-1); / 構(gòu)造左子樹 if (i=high) T-rchild = NULL; / 右子樹空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 構(gòu)造右子樹 return OK; / SecondOptimal次優(yōu)查找樹的平均查找長度和l

12、ogn成正比。9.1.4 索引順序表的查找索引順序表的查找過程：由索引確定記錄所在區(qū)間；在順序表的某個區(qū)間內(nèi)進(jìn)行查找。 可見，索引順序查找的過程也是一個“縮小區(qū)間”的查找過程。注意：索引可以根據(jù)查找表的特點(diǎn)來構(gòu)造。索引順序查找的平均查找長度 = 查找“索引”的平均查找長度 + 查找“順序表”的平均查找長度又稱為“分塊查找”課后作業(yè)P56：9.89.2 動態(tài)查找表特點(diǎn)：表結(jié)構(gòu)本身在查找過程中動態(tài)生成。抽象數(shù)據(jù)類型動態(tài)查找表的定義：ADT DynamicSearchTable 數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識數(shù)據(jù)元素。 數(shù)據(jù)關(guān)系：數(shù)據(jù)元素同屬

13、一個集合。 基本操作：InitDSTable(&DT); DestroyDSTable(&DT); SearchDSTable(DT, key); InsertDSTable(&DT, e); DeleteDSTable(&T, key); TraverseDSTable(DT, Visit();ADT DynamicSearchTable;9.2.1 二叉排序樹和平衡二叉樹二叉排序(查找)樹：或者是一棵空樹；或者是具有如下特性的二叉樹，若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；它的左、右子樹也都分別是二叉排序樹。例如：

14、 503080209010854035252388是二叉排序樹66不二叉排序樹的存儲結(jié)構(gòu)：二叉鏈表typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;二叉排序樹的查找算法：若二叉排序樹為空，則查找不成功；否則，若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。例如：如下二叉排序樹50308020908540358832查找關(guān)鍵字= 50 ,5

15、05035 ,503040355090 ,50809095 從上述查找過程可見，在查找過程中，生成了一條查找路徑：從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)； 查找成功或者從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。 查找不成功算法描述如下：Status BitTree SearchBST(BiTree T,KeyType key, BiTree f, BitTree &p) /*在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key 的數(shù)據(jù)元素,若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)， 返回True;否則返回False,指針p指向搜索路徑的最后一個結(jié)

16、點(diǎn),指針f指向當(dāng)前訪問的結(jié)點(diǎn)的雙親, 其初始調(diào)用值為NULL*/ if (!T) p = f; return FALSE; /樹為空時，退出； else f=T; if EQ (key, T-data.key) p = T; return TRUE; /找到； else if LT (key, T-data.key) return SearchBST(T-lchild,key,T,p); /小,查左子樹； else return SearchBST(T-rchild,key,T,p); /大,查右子樹;/SearchBST設(shè) key = 4830201040352523fTfTfTpfTfTT

17、TTfffp22二叉排序樹的插入算法：根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進(jìn)行；若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個新的葉子結(jié)點(diǎn)，其插入位置由查找過程得到。算法描述：Status Insert BST(BiTree &T, ElemType e ) / 當(dāng)二叉排序樹中不存在關(guān)鍵字等于 e.key 的數(shù)據(jù)元素時， /插入元素值為 e 的結(jié)點(diǎn)，并返回 TRUE; 否則，不進(jìn)行插入 /并返回FALSE。 if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BSTs = (

18、BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點(diǎn)分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 為新的根結(jié)點(diǎn)else if ( LT (e.key, p-data.key) ) p-lchild = s; / 插入 *s 為 *p 的左孩子 else p-rchild = s; / 插入 *s 為 *p 的右孩子return TRUE; / 插入成功二叉排序樹的刪除算法： 和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性?？?/p>

19、分三種情況討論：被刪除的結(jié)點(diǎn)是葉子50308020908540358832被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；50308020908540358832 其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。被刪關(guān)鍵字 = 4080被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。503080209085403588324040以其直接前驅(qū)(后繼)替代之，然后再刪除該前驅(qū)(后繼)結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字 = 50算法描述：Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序樹 T 中

20、存在其關(guān)鍵字等于 key 的 / 數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回 / 函數(shù)值 TRUE，否則返回函數(shù)值 FALSE if (!T) return FALSE; / 不存在關(guān)鍵字等于key的數(shù)據(jù)元素 else / DeleteBSTif ( EQ (key, T-data.key) ) Delete (T); return TRUE; / 找到關(guān)鍵字等于key的數(shù)據(jù)元素 else if ( LT (key, T-data.key) ) DeleteBST ( T-lchild, key ); / 繼續(xù)在左子樹中進(jìn)行查找并刪除 else DeleteBST ( T-rchild, key

21、); / 繼續(xù)在右子樹中進(jìn)行查找并刪除其中刪除操作Delete過程如下：void Delete ( BiTree &p ) / 從二叉排序樹中刪除結(jié)點(diǎn) p，并重接它的左子樹或右子樹 if (!p-rchild) else if (!p-lchild) else / Delete/ 右子樹為空樹則只需重接它的左子樹q = p; p = p-lchild; free(q);/ 左子樹為空樹只需重接它的右子樹q = p; p = p-rchild; free(q);ppppqqqqpppp/ 左右子樹均不空q = p; s = p-lchild;while (!s-rchild) q = s; s

22、= s-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū)p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接*q的左子樹free(s);二叉排序樹查找性能分析： 對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的 ASL 值。但是，含有n個結(jié)點(diǎn)的二叉排序樹的平均查找長度ASL和樹的形態(tài)有關(guān)。例如：由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹，由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹，2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1

23、+2+3+2+3）/ 5 = 2.2平均情況：假設(shè)長度為 n 的序列中有 k 個關(guān)鍵字小于第一個關(guān)鍵字，則必有 n-k-1 個關(guān)鍵字大于第一個關(guān)鍵字,由它構(gòu)造的二叉排序樹：它的平均查找長度是n和k的函數(shù)P(n, k) ( 0 k n-1 ) 假設(shè) n 個關(guān)鍵字可能出現(xiàn)的 n! 種排列的可能性相同，則含 n 個關(guān)鍵字的二叉排序樹的平均查找長度：n-k-1k式在等概率查找的情況下，把式帶入式，即對上式從k等于0至n-1求和，再取平均值,有：查找左子樹中每個關(guān)鍵字時所用比較次數(shù)的平均值查找右子樹中每個關(guān)鍵字時所用比較次數(shù)的平均值式平衡二叉樹(又稱AVL樹)：是二叉排序樹的另一種形式，其特點(diǎn)為：樹中每

24、個結(jié)點(diǎn)的左、右子樹深度之差(稱為平衡因子BF)的絕對值不大于1 ( ) 。例如：AVL樹的平均查找長度和logn是同數(shù)量級的！548254821是平衡樹不是平衡樹構(gòu)造平衡二叉樹的方法： 在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)，對失去平衡的最小子樹進(jìn)行調(diào)整。例如：依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右順時針旋轉(zhuǎn)一次先向右順時針旋轉(zhuǎn)再向左逆時針旋轉(zhuǎn)426589642895向左逆時針旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字 9失去平衡后調(diào)整的規(guī)律見教材P234。查找性能分析： 在平衡樹上進(jìn)行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)不超過平衡樹的深度。

25、問題：含 n 個關(guān)鍵字的平衡二叉樹可能達(dá)到的最大深度是多少？先看幾個具體情況：n = 0空樹最大深度為 0n = 1最大深度為 1n = 2最大深度為 2反過來，深度為 h 的二叉平衡樹中所含結(jié)點(diǎn)的最小值 Nh 是多少？n = 4最大深度為 3n = 7最大深度為 4h = 0N0 = 0h = 1h = 2h = 3一般情況下N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用歸納法可證得Nh = Fh+2 - 1斐波納契序列相似 = h+2/5 由此推得，深度為h的二叉平衡樹中所含結(jié)點(diǎn)的最小值 Nh = h+2/5 - 1。 反之，含有 n 個結(jié)點(diǎn)的二叉平衡樹能

26、達(dá)到的最大深度 hn = log(5 (n+1) - 2。 因此，在二叉平衡樹上進(jìn)行查找時，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)和 log(n) 相當(dāng)。9.2.2 B-樹定義：是一種平衡的多路查找樹。例如：4階B-樹一棵m階(結(jié)點(diǎn)的最大分支數(shù))的B-樹上：非終端結(jié)點(diǎn)結(jié)構(gòu)為：(n, A0 ,K1 ,A1 ,K2 , A2 ,K3 , A3 ,Kn , An )每個非終端結(jié)點(diǎn)可能含有：至多n個關(guān)鍵字Ki，n m-1；至少含有m/2-1個關(guān)鍵字Ki，即m/2-1n;n+1個指向子樹的指針Ai(0in);非葉結(jié)點(diǎn)中的多個關(guān)鍵字均自小至大有序排列，即：K1 K2 keynum; i=Search(p

27、, K); / 在p-key1.keynum中查找 i ，p-keyi=Kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的雙親 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功 / SearchBTreeB-樹的插入： 在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)，有下列幾種情況：插入后，該結(jié)點(diǎn)的關(guān)鍵字個數(shù)nm，不修改指針; 例如：插入后，該結(jié)點(diǎn)的關(guān)鍵字個數(shù) n=m，則需進(jìn)行“結(jié)點(diǎn)分裂”，令 s = m/2，在原結(jié)點(diǎn)中保留(A0，K1， ，Ks-1，As-1)；建新結(jié)點(diǎn)(As，Ks+1， ，Kn，An)；將(Ks, p)插入