1、第九章 查找9.1 靜態(tài)查找表 9.1.1 順序表的查找 9.1.2 有序表的查找9.2 動(dòng)態(tài)查找表 9.2.1 二叉排序樹和二叉平衡樹9.3 哈希( Hashing )表(散列表) 第九章 查找查找表 (search table): 同一類型數(shù)據(jù)元素構(gòu)成的集合。查找操作:(1)查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中;(2)檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性;(3)在查找表中插入一個(gè)數(shù)據(jù)元素;(4)從查找表中刪除某個(gè)數(shù)據(jù)元素.靜態(tài)查找表:對(duì)查找表只作(1)、(2)操作；動(dòng)態(tài)查找表：可以對(duì)查找表作(1)-(4)操作。有關(guān)查找的“詞”的含義關(guān)鍵字(KEY): 數(shù)據(jù)元素(或記錄)的某個(gè)數(shù)據(jù)項(xiàng)的值

2、,用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(或記錄). 可以唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字稱為主關(guān)鍵字(Primary Key); 否則稱為次關(guān)鍵字(Secondary Key). 查找(Searching) 根據(jù)給定的值,在查找表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素.9.1 靜態(tài)查找表可以用順序表，也可以用線性鏈表來(lái)表示靜態(tài)查找表。 順序表的查找typedef struct /靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu) ElemType *elem; int length;SSTable;elemlengthkey012.length-1length順序查找（Sequential Search）int Search_Seq(SS

3、Table ST, KeyType key) ST.elem0.key = key; / “哨兵” for(i=ST.length; !EQ(ST.elemi.key, key); -i); return i;性能分析： 設(shè)Pi為查找表中第i個(gè)記錄的概率(取Pi=1/n)；Ci為找到第i個(gè)記錄所需的查找次數(shù)。則 n ASL = Pi Ci = nP1+(n-1)P2+.+2Pn-1+Pn i=1 = n+(n-1) +.+2+1*1/n = (n+1)/2若查找成功與不成功的概率相同，即Pi=1/2n， ASL = nP1+(n-1)P2+.+2Pn-1+Pn+(n+1)/2 = (n+1)*

4、3/4有序表的查找:折半查找（Binary Search）確定待查記錄的區(qū)間，逐步縮小范圍直到找到或找不到該記錄為止。例子： 數(shù)據(jù)元素有序表如下,查找關(guān)鍵字key=21的數(shù)據(jù)元素。 21(05，13，19，21，37，56，64，75，80，88，92）下標(biāo): 0 1 2 3 4 5 6 7 8 9 10 11 05，13，19，21，37，56，64，75，80，88，92 low mid highmid = (low+high)/2; key=ST.elemmid.key查找成功;當(dāng)keyST.elemmid.key時(shí)下一個(gè)待查區(qū)間為mid+1,high折半查找的性能分析查找上例中所有元素

5、的判定二叉樹為6314795102118判定樹判定樹上每個(gè)結(jié)點(diǎn)需要的查找次數(shù)剛好為該結(jié)點(diǎn)所在的層數(shù).查找成功時(shí)查找次數(shù)不會(huì)超過(guò)判定樹的深度n個(gè)結(jié)點(diǎn)的判定樹的深度為log2n+1.折半查找的算法復(fù)雜度為log2n+19.2 動(dòng)態(tài)查找表9.2.1 二叉排序樹什么是二叉排序樹(Binary Sort Tree) ?二叉排序樹是空樹,或者是具有以下性質(zhì)的二叉樹:(1)若左子樹非空,則左子樹上所有結(jié)點(diǎn)的值均小于 它的根結(jié)點(diǎn)的值;(2)若右子樹非空,則右子樹上所有結(jié)點(diǎn)的值均大于 它的根結(jié)點(diǎn)的值;(3)它的左、右子樹也分別為二叉排序樹。二叉排序樹舉例45123375378100249061二叉排序樹查找過(guò)程

6、： 從根結(jié)點(diǎn)出發(fā)，結(jié)點(diǎn)的值與key進(jìn)行比較：（1）相等時(shí)查找成功；（2）key較大時(shí)，沿右子樹繼續(xù)查找（無(wú)右子樹表明查找失?。?；（3）key較小時(shí)，沿左子樹繼續(xù)查找（無(wú)左子樹表明查找失敗）。其中序遍歷序列:3,12,24,37,45,53,61,78,90,100二叉排序樹的生成(插入結(jié)點(diǎn))二叉排序樹的生成(連續(xù)進(jìn)行插入操作)例如:對(duì)45,24,53,45,12,24,90關(guān)鍵字序列的二叉排序樹生成過(guò)程如下:452412534524125390452453452445二叉排序樹結(jié)點(diǎn)的刪除(保持二叉排序樹的特性及次序)設(shè)被刪除的結(jié)點(diǎn)為*p,其父結(jié)點(diǎn)為*f,并不失一般性假設(shè)*p為*f的左孩子,則(

7、1)若*p為葉結(jié)點(diǎn),即PL和PR均為空.直接刪除不會(huì)影響樹結(jié)構(gòu);(2)若*p只有PL或只有PR.只要令PL或PR直接成為其雙親結(jié)點(diǎn)*f的左孩子即可,這樣也不會(huì)影響樹結(jié)構(gòu);(3)若*p有PL也有PR.為保持中序遍歷二叉樹的序列不變,可以有兩種處理方法:其一是令PL為*f的左子樹,PR為*s的右子樹(*s為中序遍歷PL的最后一個(gè)結(jié)點(diǎn));其二是令*p的直接前驅(qū)(或直接后繼)*s替代*p,然后刪除直接前驅(qū)(或直接后繼)*s.若*s有左孩子則左孩子取代*s的位置.這樣雖然影響了樹結(jié)構(gòu),但不會(huì)影響中序遍歷二叉樹時(shí)的結(jié)點(diǎn)次序.在二叉排序樹中刪除結(jié)點(diǎn)*pFPCPRSLCLQSQLFSCPRSLCLQQLFCP

8、LCLSQL二叉排序樹的查找分析n個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長(zhǎng)度和樹的形態(tài)有關(guān)45,24,53,45,12,37,93最壞情況是二叉排序樹蛻變單支樹:12,24,37,45, 53,93452412539337452412539337ASL = O(log2n)ASL = O(n/2)二叉排序樹舉例(題目)已知如下所示長(zhǎng)度為12的表(Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)試按表中元素的順序依次插入一棵初始為空的二叉排序樹,畫出插入插入完成之后的二叉排序樹,并求其在等概率的情況下查找成功的平均查找長(zhǎng)度ASL;(2)若對(duì)表中元素

9、先進(jìn)行排序構(gòu)成有序表,求其在等概率的情況下對(duì)此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長(zhǎng)度;二叉排序樹舉例(解答1)(Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)JanFebAprMarJuneMayDecOctSep二叉排序樹JulyAugNov其在等概率(1/12)的情況下查找成功的平均查找長(zhǎng)度:ASL=(1+2*2+3*3+4*3+5*2+6*1)/12 = 42/12 = 3.5JulyDecAprMayJuneOctFebNovDec判定樹JanAugAug二叉排序樹舉例(解答2)(Apr,Aug,Dec,Fab,Jan,July

10、,June,Mar,May,Nov,Oct,Sep)其在等概率(1/12)的情況下查找成功的平均查找長(zhǎng)度:ASL=(1+2*2+3*4+4*5)/12 = 37/12 = 3.19.2.2 平衡二叉樹什么是平衡二叉樹(Balanced Binary Tree) ?平衡二叉樹是空樹,或者是具有以下性質(zhì)的二叉樹:它的左子樹和右子樹也都是平衡二叉樹并且左子樹和右子樹的深度之差的絕對(duì)值不超過(guò)1結(jié)點(diǎn)的平衡因子BF(Balance Factor)是左子樹的深度減去右子樹的深度,它只可能是 -1, 0, 1平衡二叉樹(也稱AVL樹)的深度為O(log N)(其中N為結(jié)點(diǎn)個(gè)數(shù))它的平均查找長(zhǎng)度也是O(log N)平衡二叉樹及平衡因子舉例-1100-110平衡的二叉樹1100不平衡的二叉樹-1000-210 2-101 00不平衡二叉樹及平衡因子舉例二叉排序樹轉(zhuǎn)成平衡樹示例設(shè)關(guān)鍵字序列為(13,24,37,90,53) 013-113 024 037 013-213-124 024 037 053 013 013 037 090 053-124 190-237-224(a)(b)(c)(d)(e)(f)(g)(h)2413375390二叉排序樹轉(zhuǎn)成平衡樹失去平衡后進(jìn)行調(diào)整的四種情況(1)單向右旋平衡處理當(dāng)在左子樹上插入左結(jié)點(diǎn),使平衡因子由1增至2時(shí)(2)單向左旋平衡處理(上例從圖(d)