數(shù)據(jù)結(jié)構(gòu)查找

1、第九章第九章 查找查找靜態(tài)查找表靜態(tài)查找表9.19.1動態(tài)查找表動態(tài)查找表9.29.2哈希表哈希表9.39.3（1）掌握靜態(tài)查找表的順序表的查找、有序表的折半查找、靜 態(tài)樹表查找（最優(yōu)查找樹）、索引順序表的查找方法。 （2）掌握動態(tài)查找表的二叉排序樹、B_樹和B+樹的概念和構(gòu)造 方法。（3）掌握哈希表方法處理思想和過程。各種查找方法的處理過程n查找表查找表(Search Table)：同一類型的數(shù)據(jù)元同一類型的數(shù)據(jù)元素的集合。素的集合。n靜態(tài)查找表靜態(tài)查找表(Static Search Table)：查詢某個查詢某個元素、檢索指定元素的屬性。元素、檢索指定元素的屬性。n動態(tài)查找表動態(tài)查找表(D

2、ynamic Search Table) ：查找查找后插入、刪除。后插入、刪除。n關(guān)鍵字關(guān)鍵字(Key) ：可以唯一標識一個數(shù)據(jù)元素可以唯一標識一個數(shù)據(jù)元素或記錄的數(shù)據(jù)項的值?；蛴涗浀臄?shù)據(jù)項的值。第九章第九章 查找查找n查找，檢索查找，檢索(Searching)：給出一個：給出一個key值，值，在含有若干個結(jié)點的序列中找出它。在含有若干個結(jié)點的序列中找出它。n查找成功查找成功當某個元素的當某個元素的key值等于給定值值等于給定值K，返回該元素的位置。返回該元素的位置。n查找失敗查找失敗所有元素的所有元素的key值均不等于給定值均不等于給定值值K，返回表示失敗的標志。，返回表示失敗的標志。第九章

3、第九章 查找查找n平均查找長度平均查找長度Average Search Length： n n ASL= pici 可簡化為：可簡化為：ASL=1/n ci i=1 i=1nn為結(jié)點個數(shù)，為結(jié)點個數(shù)，pi是查找第是查找第i個結(jié)點的概率，個結(jié)點的概率， 且且pi=1/n， ，即各結(jié)點的查找概率相等。，即各結(jié)點的查找概率相等。ci是找到第是找到第i個結(jié)點時與個結(jié)點時與key值進行的比較次數(shù)。值進行的比較次數(shù)。第九章第九章 查找查找 n pi=1 i=1典型的關(guān)鍵字類型說明和定義典型的關(guān)鍵字類型說明和定義n類型說明類型說明typedef float KeyType; /實型實型typedef int

4、 KeyType; /整型整型typedef char KeyType; /字符型字符型n類型定義類型定義typedef struct KeyType key; /關(guān)鍵字域關(guān)鍵字域 /其它域其它域SElemType;9.1 靜態(tài)表查找靜態(tài)表查找n靜態(tài)查找表的抽象數(shù)據(jù)類型靜態(tài)查找表的抽象數(shù)據(jù)類型ADT StaticsearchTable 數(shù)據(jù)對象數(shù)據(jù)對象D：具有同一特性和類型的元素的集合、具有同一特性和類型的元素的集合、可唯一標識數(shù)據(jù)元素的關(guān)鍵字?？晌ㄒ粯俗R數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：數(shù)據(jù)集合數(shù)據(jù)集合 基本操作基本操作P：create(&ST,n) /構(gòu)造查找表構(gòu)造查找表 d

5、estroy(&ST) /銷毀查找表銷毀查找表 search(ST,ch) /查找表中指定元查找表中指定元素素 Traverse(ST,visit() /遍歷表遍歷表 ADT StaticsearchTable9.1.1 順序表的查找順序表的查找n順序表順序表(Sequential List)：線性表的順序存儲結(jié)構(gòu)：線性表的順序存儲結(jié)構(gòu) 用數(shù)組用數(shù)組AMaxSize表示表示n元素類型為元素類型為ElemType，關(guān)鍵字，關(guān)鍵字key域的類型為域的類型為KeyType9.1.1 順序表查找順序表查找n順序查找，線性查找順序查找，線性查找Sequential Search：一種：一種最基本

6、和最簡單的查找方法。從表中的第一個最基本和最簡單的查找方法。從表中的第一個元素開始，順序掃描。元素開始，順序掃描。n將給定的值與表中逐個元素的關(guān)鍵字進行比較，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。直到兩者相符，查到所要找的元素為止。n對于表中記錄的關(guān)鍵字是無序的表，只能采用對于表中記錄的關(guān)鍵字是無序的表，只能采用這種方法。這種方法。n靜態(tài)查找表的順序存儲結(jié)構(gòu)typedef struct ElemType *elem; int length;SSTable;順序查找順序查找int Search_Seq(SSTable ST, KeyType key) ST

7、.elem0.key=key; for(i=ST.length; ST.elemi.key!=key;i-) return i; 順序查找順序查找int Seqsch1(ElemType A,int n,KeyType K) An.key=K; 設(shè)置崗哨設(shè)置崗哨 for(int i=0; ;i+) if(Ai.key=K) break; if(in) return i; else return -1; n省略了對下標越界省略了對下標越界的檢查，提高算法的檢查，提高算法的執(zhí)行速度的執(zhí)行速度n時間復(fù)雜度為時間復(fù)雜度為O(n)n速度慢速度慢順序查找表的平均查找長度順序查找表的平均查找長度n在等概率且

8、查找成功的情況下：在等概率且查找成功的情況下： n n ASLss=PiCi=(1/n)(n-i+1) i=1 i=1 =(n+1)/2順序查找表的平均查找長度順序查找表的平均查找長度n順序查找成功時最多查找順序查找成功時最多查找n次，不成功時的次，不成功時的查找次數(shù)為查找次數(shù)為n+1。n此時的查找概率為此時的查找概率為Pi=1/(2n) n ASLss=1/(2n)(n-i+1)+1/2(n+1) i=1 =3/4(n+1)9.1.2 有序表的查找有序表的查找n有序表有序表：關(guān)鍵字有序，即表中的各元素按關(guān)關(guān)鍵字有序，即表中的各元素按關(guān)鍵字的值有序鍵字的值有序(升序或降序升序或降序)存放。存放

9、。n二分查找，折半查找二分查找，折半查找(Binary Search)：在有：在有序表中進行，先確定表的中點位置，再通過序表中進行，先確定表的中點位置，再通過比較確定下一步在哪一個半?yún)^(qū)查找。比較確定下一步在哪一個半?yún)^(qū)查找。n假設(shè)指針low和high分別指示待查元素所在區(qū)間的下界和上界，指針mid指示區(qū)間的中間位置，mid= (low+high)/2 n(1)若若key=rmid.key，成功，否則：成功，否則：n(2)若krmid.key, 則則low=mid+1，重復(fù)重復(fù)(1)；n直到查找成功直到查找成功n查找不成功時查找不成功時: lowhigh?；舅枷牖舅枷雗查找2112345678

10、910 1105 13 19 21 37 56 64 75 80 88 92lowhighmidhighmid lowmidn例如：已知11個數(shù)據(jù)元素的有序表：05,13,19,21,37,56,64,75,80,88,92現(xiàn)要查找關(guān)鍵字為21和85的數(shù)據(jù)元素。n查找8512345678910 1105 13 19 21 37 56 64 75 80 88 92lowhighmid lowmid lowmidhighint BinSearch(SeqList R,KeyType K) int low=1,high=n,mid; mid為二分點為二分點while(lowK) 繼續(xù)繼續(xù) high=

11、mid-1; Rlow.mid-1 else low=mid+1; Rmid+1.high return 0; 查找失敗查找失敗查找成功查找成功二分查找二分查找二分查找的判定樹二分查找的判定樹n二分查找的判定樹二分查找的判定樹：以：以Rmid為根結(jié)點，左、為根結(jié)點，左、右兩個區(qū)間對應(yīng)左、右子樹，子樹的根是各右兩個區(qū)間對應(yīng)左、右子樹，子樹的根是各自區(qū)間的中點，自區(qū)間的中點，n二分查找的判定樹是一棵理想平衡樹，除最二分查找的判定樹是一棵理想平衡樹，除最后一層外，其余層是滿的。后一層外，其余層是滿的。n查找路線：在二叉樹上用虛線標出訪問結(jié)點查找路線：在二叉樹上用虛線標出訪問結(jié)點的順序。的順序。二分查

12、找的判定樹二分查找的判定樹 1 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 96n(a) (b) (c)分別為分別為23、96、58的查找路線的查找路線54237526688260371296null4789653201(a)(b),(c)(c)(b)(b)二分查找二分查找n平均查找次數(shù)：利用二分查找的判定樹，當平均查找次數(shù)：利用二分查找的判定樹，當n足夠大時，有：足夠大時，有： ASLbn2(n+1)-1= log2n +1=hn最大查找次數(shù)為判定樹的高度最大查找次數(shù)為判定樹的高度h6319471025811具有具有11個元素的有序表進行二分查找

13、時，查找成個元素的有序表進行二分查找時，查找成功時的時間復(fù)雜度是什么？功時的時間復(fù)雜度是什么？1133)4*44*32*21 (1111niiibsCPASL9.1.4 索引順序表查找索引順序表查找索引的概念索引的概念n索引查找，分塊查找索引查找，分塊查找Index Search：在線性：在線性表的索引存儲結(jié)構(gòu)的基礎(chǔ)上進行查找。表的索引存儲結(jié)構(gòu)的基礎(chǔ)上進行查找。n把主表按照一定的函數(shù)關(guān)系或條件劃分成若把主表按照一定的函數(shù)關(guān)系或條件劃分成若干個邏輯上的子表，為每個子表建立一個索干個邏輯上的子表，為每個子表建立一個索引項，由這些索引項構(gòu)成主表的一個索引表。引項，由這些索引項構(gòu)成主表的一個索引表。索

14、引的概念索引的概念n索引項通常包括三個域：索引項通常包括三個域：n索引值域索引值域index：存儲對應(yīng)子表的索引值，：存儲對應(yīng)子表的索引值，相當于關(guān)鍵字，唯一標識索引項。相當于關(guān)鍵字，唯一標識索引項。n子表的開始位置域子表的開始位置域start：子表第一個元：子表第一個元素的存儲位置。素的存儲位置。n子表長度域子表長度域length：存儲對應(yīng)子表的元素：存儲對應(yīng)子表的元素個數(shù)。個數(shù)。索引順序表的查找索引順序表的查找 n分塊查找分塊查找、索引順序查找索引順序查找Blocking Search，將主表分成若干個子表將主表分成若干個子表( (塊塊) )，分塊有序，即，分塊有序，即塊間按大小排序，塊內(nèi)

15、不排序。塊間按大小排序，塊內(nèi)不排序。n建立一個塊的最大建立一個塊的最大(或最小或最小)關(guān)鍵字表，稱之關(guān)鍵字表，稱之為為“索引表索引表” 。索引順序表的查找索引順序表的查找 n在處理線性表時，希望能夠快速查找，又要在處理線性表時，希望能夠快速查找，又要經(jīng)常動態(tài)變化，則可以采用分塊查找方法。經(jīng)常動態(tài)變化，則可以采用分塊查找方法。n分塊：分塊：按結(jié)點元素關(guān)鍵字升序方式組織表中按結(jié)點元素關(guān)鍵字升序方式組織表中各塊，則要求第一塊中任一結(jié)點的關(guān)鍵字值各塊，則要求第一塊中任一結(jié)點的關(guān)鍵字值都小于第二塊中所有結(jié)點的關(guān)鍵字值；第二都小于第二塊中所有結(jié)點的關(guān)鍵字值；第二塊中任一結(jié)點的關(guān)鍵字值都小于第三塊中所塊中任

16、一結(jié)點的關(guān)鍵字值都小于第三塊中所有結(jié)點的關(guān)鍵字值；如此類推。有結(jié)點的關(guān)鍵字值；如此類推。n選擇每塊中的最大選擇每塊中的最大(或最小或最小)關(guān)鍵字值組成索關(guān)鍵字值組成索引表。引表。n索引表中的結(jié)點個數(shù)等于被分割的塊數(shù)。索引表中的結(jié)點個數(shù)等于被分割的塊數(shù)。 索引表 22 48 86 1 7 13最大關(guān)鍵字起始地址22 12 13 8920 33 42 44 38 24 48 60 58 74 49 86 53索引順序表的查找算法索引順序表的查找算法n查找關(guān)鍵字為查找關(guān)鍵字為k的元素，分兩步進行：的元素，分兩步進行：n根據(jù)給定的索引值，在索引表上查找出索引根據(jù)給定的索引值，在索引表上查找出索引項，確

17、定對應(yīng)子表在主表中的開始位置和長項，確定對應(yīng)子表在主表中的開始位置和長度。度。n再根據(jù)給定的關(guān)鍵字，在對應(yīng)子表中查找出再根據(jù)給定的關(guān)鍵字，在對應(yīng)子表中查找出元素結(jié)點。元素結(jié)點。1.先用折半查找法由索引表查出先用折半查找法由索引表查出k所在的塊，所在的塊，再用順序查找法在對應(yīng)的塊中找出再用順序查找法在對應(yīng)的塊中找出k。分塊查找分析分塊查找分析n分塊查找的平均查找長度為：分塊查找的平均查找長度為： ASLbs=Lb+Lwn其中：其中：Lb是折半查找的平均查找長度，是折半查找的平均查找長度，Lw是是用順序查找法查塊內(nèi)元素的平均查找長度。用順序查找法查塊內(nèi)元素的平均查找長度。n分塊查找的平均查找長度位

18、于順序查找和折分塊查找的平均查找長度位于順序查找和折半查找之間。半查找之間。分塊查找分析分塊查找分析n以二分查找確定塊：以二分查找確定塊： ASLblk2(n/s+1)+s/2 以順序查找確定塊：以順序查找確定塊： ASLblk=(s2+2s+n)/2s=1/2(n/s+s)+1n時間復(fù)雜度：時間復(fù)雜度：O(n)(1) 平均查找長度：平均查找長度：折半查找最小，分塊查找折半查找最小，分塊查找次之，順序查找最大；次之，順序查找最大；(2) 表的結(jié)構(gòu)：表的結(jié)構(gòu)：順序查找對有序表、無序表均順序查找對有序表、無序表均適用；折半查找僅適用于有序表；分塊查找適用；折半查找僅適用于有序表；分塊查找要求表中元

19、素是塊與塊之間的記錄按關(guān)鍵字要求表中元素是塊與塊之間的記錄按關(guān)鍵字有序；有序；(3) 存儲結(jié)構(gòu)：存儲結(jié)構(gòu)：順序查找和分塊查找對向量和順序查找和分塊查找對向量和線性鏈表結(jié)構(gòu)均適用；折半查找只適用于向線性鏈表結(jié)構(gòu)均適用；折半查找只適用于向量存儲結(jié)構(gòu)的表。量存儲結(jié)構(gòu)的表。 小結(jié)小結(jié)9.2 動態(tài)查找表動態(tài)查找表n表結(jié)構(gòu)在查找過程中動態(tài)生成。表結(jié)構(gòu)在查找過程中動態(tài)生成。n即對于給定值即對于給定值key，若表中存在其關(guān)鍵字等，若表中存在其關(guān)鍵字等于于key的記錄，則查找成功；否則插入關(guān)鍵的記錄，則查找成功；否則插入關(guān)鍵字等于字等于key的記錄。的記錄。動態(tài)查找表的抽象數(shù)據(jù)類型動態(tài)查找表的抽象數(shù)據(jù)類型ADT

20、 DynamicsearchTable 數(shù)據(jù)對象數(shù)據(jù)對象D：具有同一特性和類型的元素的集合、具有同一特性和類型的元素的集合、可唯一標識數(shù)據(jù)元素的關(guān)鍵字。可唯一標識數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：數(shù)據(jù)集合數(shù)據(jù)集合 基本操作基本操作P：InitDSTable(&DT,n) /構(gòu)造查找表構(gòu)造查找表 destroyDSTable(&DT) /銷毀查找表銷毀查找表 searchDSTable(DT,ch) /查找表中指定元素查找表中指定元素 TraverseDSTable(DT,visit() /遍歷表遍歷表 ADT DynamicsearchTable9.2.1 二叉排序樹和平

21、衡二叉樹二叉排序樹和平衡二叉樹二叉排序樹的定義二叉排序樹的定義n二叉排序樹二叉排序樹 Binary Sort Treen二叉查找樹、二叉搜索樹二叉查找樹、二叉搜索樹Binary Search Treen結(jié)點的關(guān)鍵字：結(jié)點的關(guān)鍵字：n簡單類型簡單類型結(jié)點的值結(jié)點的值n記錄類型記錄類型結(jié)點的某一個域的值結(jié)點的某一個域的值n以結(jié)點值域以結(jié)點值域data中關(guān)鍵字域中關(guān)鍵字域key作為結(jié)點作為結(jié)點的關(guān)鍵字。的關(guān)鍵字。二叉排序樹的定義二叉排序樹的定義n二叉排序樹或是一棵空樹，或是具有如下特二叉排序樹或是一棵空樹，或是具有如下特性的非空二叉樹：性的非空二叉樹：1.若它的左子樹非空，則左子樹上所有結(jié)點的若它的

22、左子樹非空，則左子樹上所有結(jié)點的關(guān)鍵字均小于根結(jié)點的關(guān)鍵字；關(guān)鍵字均小于根結(jié)點的關(guān)鍵字；2.若它的右子樹非空，則右子樹上所有結(jié)點的若它的右子樹非空，則右子樹上所有結(jié)點的關(guān)鍵字均大于根結(jié)點的關(guān)鍵字關(guān)鍵字均大于根結(jié)點的關(guān)鍵字3.左、右子樹本身又各是一棵二叉排序樹。左、右子樹本身又各是一棵二叉排序樹。二叉排序樹的抽象數(shù)據(jù)類型二叉排序樹的抽象數(shù)據(jù)類型n結(jié)點類型結(jié)點類型BTreeNode，根結(jié)點指針，根結(jié)點指針BSTint Find(BTreeNode * BST, ElemType& item);查找查找int Update(BTreeNode *BST, const ElemType&

23、; item);更新更新void Insert(BTreeNode * BST, const ElemType& item); 插入插入int Delete(BTreeNode * BST, const ElemType& item);刪除刪除29925603913523118例如中序遍歷序列：中序遍歷序列： 9 13 18 25 29 31 39 52 60 n二叉排序樹的特點：中序遍歷二叉排序樹得到的關(guān)鍵字序列是一個遞增的有序序列。n在二叉排序樹中查找關(guān)鍵字值為29和30的過程。29925603913523118n查找3029925603913523118n基本思路：n若二

24、叉排序樹為空，則查找失敗；n若key等于當前根結(jié)點的值，則查找成功；n若key小于當前根結(jié)點的值，在繼續(xù)在根的左子樹中查找；n若key大于當前根結(jié)點的值，在繼續(xù)在根的右子樹中查找；n如何在二叉排序樹中查找給定關(guān)鍵字值為key的結(jié)點？二叉排序樹的查找二叉排序樹的查找int Find(BTreeNode * BST, ElemType& item); if(BST=NULL) return; else if(item.key=BST-data.key) item=BST-data; return 1; else if(item.keydata.key) return Find(BST-le

25、ft,item); 遞歸算法遞歸算法 else return Find(BST-right,item); 二叉排序樹的查找二叉排序樹的查找int Find(BTreeNode * BST, ElemType& item); while(BST!=NULL) 非遞歸算法非遞歸算法 if(item.key=BST-data.key) item=BST-data; 查找成功，值由查找成功，值由item帶回帶回 return 1; else if(item.keydata.key) BST=BST-left; 查找左子樹查找左子樹 else BST=BST-right; 查找右子樹查找右子樹

26、return 0; 二叉排序樹的查找二叉排序樹的查找n二叉排序樹的查找：與二分查找類似，逐步二叉排序樹的查找：與二分查找類似，逐步縮小查找范圍。縮小查找范圍。n在二叉排序樹上的平均查找長度與二叉樹的在二叉排序樹上的平均查找長度與二叉樹的形態(tài)有關(guān)。樹的形態(tài)比較均衡時，樹的高度形態(tài)有關(guān)。樹的形態(tài)比較均衡時，樹的高度較小，平均查找長度也較小。較小，平均查找長度也較小。二叉排序樹的更新二叉排序樹的更新n與二叉排序樹的算法基本相同與二叉排序樹的算法基本相同n在更新算法中，在查找到待更新元素后，將在更新算法中，在查找到待更新元素后，將item值賦給該元素。值賦給該元素。nitem可為變參，也可為實參?？蔀?/p>

27、變參，也可為實參。二、二叉排序樹的插入和刪除1、二叉排序樹的插入基本思想：n若二叉排序樹為空，則待插結(jié)點作為根結(jié)點插入到空樹中；n若待插結(jié)點的關(guān)鍵字值和根結(jié)點的關(guān)鍵字值相等，則說明樹中已有此結(jié)點，無需插入；n若待插結(jié)點的關(guān)鍵字值小于根結(jié)點的關(guān)鍵字值，則將待插結(jié)點插入到根的左子樹中；n若待插結(jié)點的關(guān)鍵字值大于根結(jié)點的關(guān)鍵字值，則將待插結(jié)點插入到根的右子樹中；n如此進行下去，直到把待插結(jié)點作為一個葉結(jié)點插入到二叉排序樹中，或直到發(fā)現(xiàn)樹中已存在該結(jié)點為止 在二叉排序樹中插入58和3929925603913523118 插入5858 插入392992560391352311858n對給定的關(guān)鍵字序列7

28、,16,4,8,20,9,6,18,5，構(gòu)造一棵二叉排序樹。n二叉排序樹的生成是從空的二叉排序樹開始，每輸入一個數(shù)據(jù)，建立一個新結(jié)點，插入到當前已經(jīng)生成的二叉排序樹中。輸入數(shù)據(jù)：輸入數(shù)據(jù)：7164208918656208416759187二叉排序樹的插入二叉排序樹的插入n例：待建立二叉排序樹的一組元素為例：待建立二叉排序樹的一組元素為n(38,26,62,94,35,50,28,55)3826623555945028n練習(xí)：n輸入一個序列45,24,53,45,12,30,90，構(gòu)造一棵二叉排序樹。123090245345二叉排序樹的插入二叉排序樹的插入n向二叉排序樹插入元素的遞歸過程：向二叉

29、排序樹插入元素的遞歸過程：n若樹為空：由若樹為空：由item生成的結(jié)點為根結(jié)點生成的結(jié)點為根結(jié)點n若若item.key小于根結(jié)點的小于根結(jié)點的key，則，則item插入到插入到左子樹。左子樹。n若若item.key大于根結(jié)點的大于根結(jié)點的key，則，則item插入到插入到右子樹。右子樹。二叉排序樹的插入二叉排序樹的插入int Insert(BTreeNode *& BST, ElemType& item); if(BST=NULL) 遞歸算法遞歸算法 BTreeNode * p=new BTreeNode; p-data=item; p-left=p-right=NULL; B

30、ST=p; else if(item.keydata.key) Insert(BST-left,item); 向左子樹插入向左子樹插入 else Insert(BST-right,item); 向右子樹插入向右子樹插入 二叉排序樹的刪除二叉排序樹的刪除1.刪除葉子結(jié)點：直接刪除，雙親中指向該結(jié)刪除葉子結(jié)點：直接刪除，雙親中指向該結(jié)點的指針域置為點的指針域置為NULL。2.刪除單分支結(jié)點：將雙親與孩子直接連接刪除單分支結(jié)點：將雙親與孩子直接連接3.刪除雙分支結(jié)點：用它的中序后繼替換它，刪除雙分支結(jié)點：用它的中序后繼替換它，并使整棵樹保持并使整棵樹保持BST性質(zhì)。性質(zhì)。29925603913523

31、118刪除刪除3129ps29925603913523118刪除刪除60刪除刪除3939刪除刪除13pf9291825291825s29925603913523118刪除刪除3129psn練習(xí)n依次刪除二叉排序樹中的關(guān)鍵字為13，12，4，8的各結(jié)點后，該二叉排序樹的結(jié)構(gòu)。76141041285111513答案答案176141051115答案答案214106117515n練習(xí)n依次刪除二叉排序樹中的關(guān)鍵字為13，12，4，8的各結(jié)點后，該二叉排序樹的結(jié)構(gòu)。76141041285111513三、二叉排序樹的查找分析 下面兩棵二叉排序樹分別由序列12,24,37,45,53,93和序列45,24,

32、53,12,37,93構(gòu)成，計算其平均查找長度。122437455393452453123793122437455393621)654321 (61ASL452453123793614)333221 (61ASLn由此可見，在二叉排序樹上進行查找時的平均查找長度和二叉樹的形態(tài)有關(guān)。在最壞情況下二叉排序樹是通過把一個有序表的n個結(jié)點依次插入而生成的，此時所得的二叉排序樹退化為深度為n的單支樹，它的平均查找長度和順序查找相同，亦是(n+1)/2；在最好的情況下，二叉排序樹在生成的過程中，樹的形態(tài)比較勻稱，最終得到的是一棵形態(tài)與判定樹相似的二叉排序樹，此時它的平均查找長度大約是log2n。n如果所建

33、二叉排序樹的形態(tài)和折半查找的判定樹相似，平均查找長度和log2n是等數(shù)量級的，尚需在構(gòu)造二叉排序樹的過程中進行平衡化處理，成為平衡二叉樹。n如何構(gòu)造平衡二叉樹？調(diào)用二叉排序樹算法的程序舉例調(diào)用二叉排序樹算法的程序舉例n假定二叉排序樹中元素類型假定二叉排序樹中元素類型ElemType定義定義為為student記錄類型：記錄類型： struct student int key; int rest; void main() 定義數(shù)組，指針等；定義數(shù)組，指針等； 調(diào)用對二叉排序樹操作的各種算法；調(diào)用對二叉排序樹操作的各種算法；n樹表查找是對樹型結(jié)構(gòu)所做的查找樹表查找是對樹型結(jié)構(gòu)所做的查找n樹型存儲結(jié)構(gòu)

34、樹型存儲結(jié)構(gòu)樹表樹表n樹型邏輯結(jié)構(gòu)樹型邏輯結(jié)構(gòu)樹樹n平衡二叉樹平衡二叉樹balanced binary tree平衡樹平衡樹n由于二叉排序樹的結(jié)構(gòu)可能不平衡，導(dǎo)致對由于二叉排序樹的結(jié)構(gòu)可能不平衡，導(dǎo)致對樹的運算的時間復(fù)雜度增加。樹的運算的時間復(fù)雜度增加。n調(diào)整二叉排序樹的結(jié)構(gòu)，使其始終成為平衡調(diào)整二叉排序樹的結(jié)構(gòu)，使其始終成為平衡的狀態(tài)的狀態(tài)平衡二叉樹。平衡二叉樹。平衡二叉樹平衡二叉樹n平衡樹平衡樹 Adelson-Velskii and LandisAVL樹樹n定義：若一棵二叉樹中每個結(jié)點的左、右子定義：若一棵二叉樹中每個結(jié)點的左、右子樹的高度至多相差樹的高度至多相差1，則稱此樹為平衡樹。，

35、則稱此樹為平衡樹。n平衡因子平衡因子balance factor：二叉樹中的每個：二叉樹中的每個結(jié)點的左子樹高度減去右子樹高度。結(jié)點的左子樹高度減去右子樹高度。n平衡樹中的每個結(jié)點的平衡因子只能是：平衡樹中的每個結(jié)點的平衡因子只能是：1，0，-1平衡二叉樹平衡二叉樹299256039135231181-10000000平衡二叉樹平衡二叉樹76141041285111513000000000-1-2非平衡二叉樹非平衡二叉樹n如何構(gòu)造平衡二叉樹呢？n在構(gòu)造平衡二叉樹的過程中，每當插入一個結(jié)點時，首先檢查是否因插入而破壞了樹的平衡性，若是，則找出其中最小不平衡子樹，在保持排序樹特性的前提下，調(diào)整最小

36、不平衡子樹中各結(jié)點之間的鏈接關(guān)系，以達到新的平衡。n如果在平衡樹上插入一個結(jié)點，可能影響到如果在平衡樹上插入一個結(jié)點，可能影響到某一結(jié)點的平衡因子，如果導(dǎo)致破壞了平衡某一結(jié)點的平衡因子，如果導(dǎo)致破壞了平衡樹的限制條件，就需要進行調(diào)整。樹的限制條件，就需要進行調(diào)整。n最小不平衡子樹最小不平衡子樹以離插入結(jié)點最近，且平以離插入結(jié)點最近，且平衡因子絕對值大于衡因子絕對值大于1的結(jié)點作為根的子樹。的結(jié)點作為根的子樹。n對最小不平衡子樹進行調(diào)整對最小不平衡子樹進行調(diào)整平衡樹平衡樹n歸納為四種情況：歸納為四種情況：(1) LL型調(diào)整操作型調(diào)整操作在在A結(jié)點的左孩子的左子結(jié)點的左孩子的左子樹上插入結(jié)點，導(dǎo)致

37、平衡因子變化而引起的樹上插入結(jié)點，導(dǎo)致平衡因子變化而引起的不平衡所進行的調(diào)整操作。不平衡所進行的調(diào)整操作。(2) RR型調(diào)整操作型調(diào)整操作(3) LR型調(diào)整操作型調(diào)整操作(4) RL型調(diào)整操作型調(diào)整操作平衡樹平衡樹1321183529918139352921LL型3492260131822346013918RR型359291318837241628189138352937162428RL型n輸入序列為13,24,37,90,53構(gòu)造平衡二叉排序樹的過程。9037532413133724379053n練習(xí)：對給定的數(shù)列R=7,16,4,8,20,9,6,18,5構(gòu)造一棵平衡二叉樹。4720961

38、685189.2.2 B-樹樹nB-樹是由樹是由R.bayer和和E.Maccreight于于1970 年年提出的，一種特殊的多元樹，一種在外存文提出的，一種特殊的多元樹，一種在外存文件系統(tǒng)中常用的動態(tài)索引技術(shù)。件系統(tǒng)中常用的動態(tài)索引技術(shù)。nB-樹或是一棵空樹，或是一棵具有如下結(jié)點樹或是一棵空樹，或是一棵具有如下結(jié)點結(jié)構(gòu)的樹：結(jié)構(gòu)的樹：nB-樹中的每個結(jié)點的大小相同，樹中的每個結(jié)點的大小相同，m3為為B-樹樹的階，的階，par為指向父結(jié)點的指針域。為指向父結(jié)點的指針域。nparp0k1p1k2p2knpnkmpmB-樹樹1.B-樹的定義樹的定義n 每個結(jié)點至少包含下列數(shù)據(jù)域：每個結(jié)點至少包含下

39、列數(shù)據(jù)域： (j,p0,k1, p1, k2, kj, pj)nJ為關(guān)鍵字總數(shù)，為關(guān)鍵字總數(shù)， ki(1ij)是關(guān)鍵字，是關(guān)鍵字， pi(0ij)是指向孩子的指針，葉子結(jié)點是指向孩子的指針，葉子結(jié)點pi為為空。空。n用用keys(pi)表示子樹表示子樹pi中的所有關(guān)鍵字有：中的所有關(guān)鍵字有：keys(p0)k1keys(p1)k2 kjkeys(pj)B-樹樹(2) 所有的葉子都在同一層上，葉子的所在層所有的葉子都在同一層上，葉子的所在層數(shù)為樹的高度數(shù)為樹的高度h。(3) 每個非根結(jié)點中包含的關(guān)鍵字個數(shù)每個非根結(jié)點中包含的關(guān)鍵字個數(shù)j滿足：滿足： m/2 j m-1 (4) 若樹非空，則根至少

40、有一個關(guān)鍵字，若根若樹非空，則根至少有一個關(guān)鍵字，若根不是葉子，則它至少有兩棵子樹，根至多不是葉子，則它至少有兩棵子樹，根至多有有m-1個關(guān)鍵字，故至多有個關(guān)鍵字，故至多有m棵子樹?？米訕?。B-樹樹2. B-樹的查找：多路平衡查找樹，可用順序樹的查找：多路平衡查找樹，可用順序查找或二叉查找。查找或二叉查找。3. B-樹的插入：先插入到某個葉子，再根據(jù)樹的插入：先插入到某個葉子，再根據(jù)B-樹的性質(zhì)進行調(diào)整。樹的性質(zhì)進行調(diào)整。4. B-樹的刪除：先刪除指定的葉子，再根據(jù)樹的刪除：先刪除指定的葉子，再根據(jù)B-樹的性質(zhì)進行調(diào)整。樹的性質(zhì)進行調(diào)整。B-樹樹nB-樹的階樹的階n一棵度為一棵度為m的的B-樹

41、稱為樹稱為m階階B_樹。樹。n根據(jù)定義，在一棵根據(jù)定義，在一棵5階階B-樹里，根的關(guān)鍵字樹里，根的關(guān)鍵字數(shù)目可以是數(shù)目可以是14，子樹數(shù)可以是，子樹數(shù)可以是25，其它，其它結(jié)點中關(guān)鍵字數(shù)目可以是結(jié)點中關(guān)鍵字數(shù)目可以是24，若該結(jié)點不，若該結(jié)點不是葉子，可以有是葉子，可以有35棵子樹?？米訕洹?.3 哈希表一、基本概念 哈希、哈希查找和哈希表 哈希（Hash）又稱散列，是一種重要的存儲方法。它的基本思想是：以結(jié)點的關(guān)鍵字k為自變量，通過一個確定的函數(shù)H，計算出對應(yīng)的函數(shù)值H(k)，作為結(jié)點的存儲位置，將結(jié)點存入H(k)所指的存儲位置上。 哈希查找是一種常見的查找方法，查找時根據(jù)要查找的關(guān)鍵字用同

42、樣的函數(shù)H計算地址，然后到相應(yīng)的單元去取要找的結(jié)點。順序查找、折半查找、樹表的查找都是建立在比較基礎(chǔ)上的查找，而哈希查找是直接查找。 用哈希法存儲的線性表叫做哈希表。上述的H函數(shù)稱為哈希函數(shù)。H(k)稱為哈希地址。通常哈希表的存儲空間是一個一維數(shù)組，哈希地址是數(shù)組的下標。 沖突和同義詞 若某個哈希函數(shù)H對于不同的關(guān)鍵字key1和key2得到相同的哈希地址，這種現(xiàn)象稱為沖突。而發(fā)生沖突的這兩個關(guān)鍵字則稱為該哈希函數(shù)的同義詞。9.3.2 哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法n構(gòu)造哈希函數(shù)的目標：使哈希地址盡可能構(gòu)造哈希函數(shù)的目標：使哈希地址盡可能地均勻分布在散列空間上，計算要簡單。地均勻分布在散列

43、空間上，計算要簡單。n根據(jù)關(guān)鍵字的結(jié)構(gòu)和分布情況，構(gòu)造出相根據(jù)關(guān)鍵字的結(jié)構(gòu)和分布情況，構(gòu)造出相適應(yīng)的哈希函數(shù)。適應(yīng)的哈希函數(shù)。n假定關(guān)鍵字為整型數(shù)假定關(guān)鍵字為整型數(shù)哈希函數(shù)哈希函數(shù)1.直接定址法直接定址法以關(guān)鍵字以關(guān)鍵字K本身或本身或K加上一個常加上一個常數(shù)數(shù)C，生成散列地址。，生成散列地址。n對應(yīng)的哈希函數(shù)為：對應(yīng)的哈希函數(shù)為：h(K)=K+Cn當當C=0時，為關(guān)鍵字本身。時，為關(guān)鍵字本身。n計算最簡單，一般情況下無沖突。計算最簡單，一般情況下無沖突。n如發(fā)生沖突，則可能是關(guān)鍵字錯誤。如發(fā)生沖突，則可能是關(guān)鍵字錯誤。哈希函數(shù)哈希函數(shù)2.數(shù)字分析法數(shù)字分析法取關(guān)鍵字中某些取值較分散的取關(guān)鍵字中

44、某些取值較分散的數(shù)字位作為散列地址。數(shù)字位作為散列地址。n適合于所有關(guān)鍵字已知，并對關(guān)鍵字中的每適合于所有關(guān)鍵字已知，并對關(guān)鍵字中的每一位的取值分布情況作出了分析。一位的取值分布情況作出了分析。n例如：例如：2004*哈希函數(shù)哈希函數(shù)3.平方取中法平方取中法取關(guān)鍵字平方的中間某些位取關(guān)鍵字平方的中間某些位作為散列地址。作為散列地址。n具體位數(shù)依實際需要而定具體位數(shù)依實際需要而定n一個數(shù)的平方的中間某些位和數(shù)的每一位一個數(shù)的平方的中間某些位和數(shù)的每一位都有關(guān)。都有關(guān)。即：得到散列地址與關(guān)鍵字的每即：得到散列地址與關(guān)鍵字的每一位都有關(guān)，這樣就比較分散。一位都有關(guān)，這樣就比較分散。n適合于每一位都不

45、夠分散或較分散的位數(shù)適合于每一位都不夠分散或較分散的位數(shù)不滿足實際需要的情況。不滿足實際需要的情況。哈希函數(shù)哈希函數(shù)4.折疊法折疊法將關(guān)鍵字分割成位數(shù)相同的若干段，將關(guān)鍵字分割成位數(shù)相同的若干段，然后將各段的疊加和作為散列地址。然后將各段的疊加和作為散列地址。n段的位數(shù)取決于散列地址的位數(shù)，最后一段段的位數(shù)取決于散列地址的位數(shù)，最后一段位數(shù)可少一些。疊加和舍去最高位進位。位數(shù)可少一些。疊加和舍去最高位進位。n例如：例如：K=68242324，散列地址為，散列地址為3位，分成位，分成3段：段：682、423、24，疊加和為，疊加和為129。以此。以此作為該關(guān)鍵字的散列地址。作為該關(guān)鍵字的散列地址

46、。n適合于關(guān)鍵字位數(shù)較多而所需要的散列地址適合于關(guān)鍵字位數(shù)較多而所需要的散列地址的位數(shù)又較少，各個位取值較集中的情況。的位數(shù)又較少，各個位取值較集中的情況。哈希函數(shù)哈希函數(shù)5.除留余數(shù)法除留余數(shù)法關(guān)鍵字關(guān)鍵字K除以哈希表長度除以哈希表長度m所所得的余數(shù)作為散列地址。得的余數(shù)作為散列地址。n哈希函數(shù)為：哈希函數(shù)為：h(K)=k%mn最重要的是選擇模數(shù)最重要的是選擇模數(shù)m，使得：每一個關(guān)鍵，使得：每一個關(guān)鍵字經(jīng)函數(shù)轉(zhuǎn)換后，映射到散列空間上任一地字經(jīng)函數(shù)轉(zhuǎn)換后，映射到散列空間上任一地址的概率都相等。址的概率都相等。n通常選擇通常選擇m為小于或等于線性表長度的最大為小于或等于線性表長度的最大素數(shù)。素數(shù)

47、。哈希函數(shù)哈希函數(shù)6.隨機數(shù)法隨機數(shù)法選擇一個隨機函數(shù)，取關(guān)鍵字的選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)為散列地址。隨機函數(shù)為散列地址。n哈希函數(shù)為：哈希函數(shù)為：H(key)=random(key)n適合于關(guān)鍵字長度不等的情況適合于關(guān)鍵字長度不等的情況9.3.3 處理沖突的方法處理沖突的方法1.開放定址法開放定址法n開放定址法開放定址法從發(fā)生沖突的單元開始，按照從發(fā)生沖突的單元開始，按照一定的次序，在哈希表中確定可以存儲待插一定的次序，在哈希表中確定可以存儲待插入元素的位置。入元素的位置。n空閑單元即向同義詞元素開放，也向非同義空閑單元即向同義詞元素開放，也向非同義詞元素開放。詞元素開放。n開放

48、定址法確定位置有多種方法開放定址法確定位置有多種方法處理沖突的方法處理沖突的方法(1)線性探查法線性探查法線性探測再散列線性探測再散列n線性探查法線性探查法最簡單的方法。最簡單的方法。將哈希表作為將哈希表作為循環(huán)表，從發(fā)生沖突的循環(huán)表，從發(fā)生沖突的d單元開始，依次探單元開始，依次探察下一個單元，直到找出一個空閑單元為止察下一個單元，直到找出一個空閑單元為止n遞推公式：遞推公式： d0=h(K) di=(di-1+1)%m (1im-1)n步長為步長為1處理沖突的方法處理沖突的方法n因為最先找到的空閑單元都是被占用單元的因為最先找到的空閑單元都是被占用單元的下一個單元，因此利用線性探查法處理沖突

49、下一個單元，因此利用線性探查法處理沖突容易造成元素的堆積，增加了查找長度。容易造成元素的堆積，增加了查找長度。n例：在哈希表例：在哈希表H中再插入中再插入31和和58兩個元素。兩個元素。H(K)=k%13 0 1 2 3 4 5 6 7 8 9 10 11 1275604618435490756046184354905831HH處理沖突的方法處理沖突的方法(2)再哈希法再哈希法(雙哈希函數(shù)探查法雙哈希函數(shù)探查法)n使用兩個哈希函數(shù)使用兩個哈希函數(shù)h1和和h2，均以關(guān)鍵字為，均以關(guān)鍵字為自變量，產(chǎn)生一個自變量，產(chǎn)生一個0m-1之間的數(shù)。之間的數(shù)。nh1同前面的同前面的h(K)，產(chǎn)生的數(shù)作為散列地

50、址，產(chǎn)生的數(shù)作為散列地址h2產(chǎn)生的數(shù)不能整除產(chǎn)生的數(shù)不能整除m，作為步長。，作為步長。n遞推公式：遞推公式： d0=h1(K) di=(di-1+h2(K)%m (1im-1)處理沖突的方法處理沖突的方法2.鏈地址法鏈地址法n把發(fā)生沖突的同義詞元素用單鏈表鏈接把發(fā)生沖突的同義詞元素用單鏈表鏈接n哈希表的每個單元作為各個單鏈表的表頭指哈希表的每個單元作為各個單鏈表的表頭指針，單鏈表的結(jié)點動態(tài)產(chǎn)生。針，單鏈表的結(jié)點動態(tài)產(chǎn)生。n首先根據(jù)待插入元素的關(guān)鍵字首先根據(jù)待插入元素的關(guān)鍵字K計算出散列計算出散列地址地址d，并由該元素動態(tài)生成結(jié)點，然后將，并由該元素動態(tài)生成結(jié)點，然后將該結(jié)點插入到地址該結(jié)點插入到地址d單元為表頭的單鏈表中。單元為表頭的單