第9章查找1整理ppt查找表(SearchTable)：是由同一類型的數據元素〔或記錄〕構成的集合。

前面已介紹了各種線性或非線性的數據結構，本章討論另一種在實際應用中大量使用的數據結構---查找表。由于“集合〞中的數據元素之間存在著完全松散的關系，因此查找表是一種非常靈便的數據結構。2整理ppt對查找表經常進行的操作：〔1〕查詢某個“特定的〞數據元素是否在查找表中。〔2〕檢索某個“特定的〞數據元素的各種屬性。〔3〕在查找表中插入一個數據元素。〔4〕從查找表中刪去某個數據元素。3整理ppt查找表可分為兩類：假設對查找表只作查詢和檢索操作，那么稱此類查找表為靜態查找表〔StaticSearchTable)。假設在查找過程中同時插入查找表中不存在的數據元素，或者從查找表中刪除已存在的某個數據元素，那么稱此類查找表為動態查找表〔DynamicSearchTable〕。4整理ppt

在各種系統軟件或應用軟件中，查找表是最常見的結構之一。如編譯程序中符號表、信息處理系統中信息表等。綜上所述，所謂“查找〞即為在一個含有眾多的數據元素〔或記錄〕的查找表中找出某個“特定的〞數據元素〔或記錄〕。關于“特定的〞詞的具體含義：關鍵字〔Key〕：是數據元素〔或記錄〕中某個數據項的值，用它可以標識一個數據元素〔或記錄〕。主關鍵字〔PrimaryKey〕：假設此關鍵字可以惟一地標識一個記錄，那么稱此關鍵字為主關鍵字。對不同的記錄，其主關鍵字均不同。5整理ppt次關鍵字〔SecondaryKey〕：用以識別假設干記錄的關鍵字為次關鍵字。

當數據元素只有一個數據項時，其關鍵字即為該數據元素的值。查找〔Searching)：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素〔或記錄〕。查找成功：假設表中存在這樣的一個記錄，那么查找成功，此時查找的結果為給出整個記錄的信息，或指示該記錄在查找表中的位置。查找不成功：假設表中不存在關鍵字等于給定值的記錄，那么查找不成功，此時查找的結果可給出一個“空〞記錄或“空〞指針。6整理ppt此表為一個查找表。表中每一行為一個記錄，學生的學號為記錄的關鍵字。假設給定值為20010985，那么通過查找可得學生王五的各項信息。此時查找是成功的。假設給定值為20011930，那么由于表中沒有關鍵字為20011930的記錄，那么查找不成功。學號姓名性別入學總分錄取專業┊┊┊┊┊20010983張三女438計算機20010984李四男430計算機20010985王五女445計算機┊┊┊┊┊20010998張三男458計算機┊┊┊┊┊招生錄取登記表例：7整理ppt如何進行查找？在一個結構中查找某個數據元素的過程依賴于這個數據元素在結構中所處的地位。即：對查找表進行查找的方法取決于表中數據元素依何種關系組織在一起。〔這個關系是人為加上的。因為查找表中數據元素之間原本僅存在“同屬于一個集合〞的松散關系〕。例：查英文單詞。字典是按單詞的字母在字母表中的次序編排的，那么查找時不需要從字典中第一個單詞比較起，而只要根據待查單詞中每個字母在字母表中的位置查到該單詞。字典這種查找表的數據元素之間原本僅存在著“同屬于一個集合〞的松散關系，給查找帶來不便。對字典按單詞的字母在字母表中的次序進行編排，就是對字典這種查找表人為加上的一種關系，以便按某種規那么進行查找。8整理ppt

總之：查找的方法取決于查找表的結構。由于查找表中的數據元素之間不存在明顯的組織規律，因此不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關系，換句話說，用另外一種結構來表示查找表。9整理ppt內查找和外查找：假設整個查找過程全部在內存進行，那么稱為內查找；假設在查找過程中還需要訪問外存，那么稱為外查找。本書僅介紹內查找。平均查找長度ASL：查找算法的效率，主要看要查找的值與關鍵字的比較次數，通常用平均查找長度來衡量。10整理ppt

對一個含n個數據元素的表，查找成功時：

其中：Pi為找到表中第i個數據元素的概率，且有：

Ci為查找表中第i個數據元素所用到的比較次數。不同的查找方法有不同的Ci。

查找是許多程序中最消耗時間的一部分。因而，一個好的查找方法會大大提高運行速度。11整理ppt9.1

靜態查找表9.2動態查找表9.3

哈希表本章內容：12整理ppt9.1

靜態查找表13整理ppt1.順序表的查找靜態查找表的存儲結構可用順序表或線性鏈表表示。本節只討論在順序存儲結構中查找的實現。順序查找的根本思想：從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，假設某個記錄的關鍵字和給定值比較相等，那么查找成功，找到所查記錄；反之，假設直至第一個記錄，其關鍵字和給定值比較都不等，那么說明表中沒有所查記錄，查找不成功。14整理ppti例

012

34567891011

513192137566475808892找6464監視哨iiii比較次數=5比較次數：查找第n個元素：1查找第n-1個元素：2……….查找第1個元素：n查找第i個元素：n-i+1查找失敗：n+115整理ppt例01234567891011

513192137566475808892找6464監視哨#defineM500typedefstruct{intkey;floatinfo;}JD;intseqsrch(JDr[],intn,intk){inti=n;r[0].key=k;while(r[i].key!=k)i--;return(i);}16整理ppt監測哨的作用：〔1〕省去判定循環中下標越界的條件，從而節約比較時間。〔2〕保存查找值的副本，查找時假設遇到它，那么表示查找不成功。這樣在從后向前查找失敗時，不必判斷查找表是否檢測完，從而到達算法統一。上述算法中，對于有n個數據元素的表，給定值k與表中第i個元素的關鍵字相等，即定位第i個記錄時，需進行：ni+1次關鍵字比較，即Ci=ni+1。那么查找成功時，順序查找的平均查找長度為：順序查找性能分析：對一個含有n個數據元素的表，查找成功時有：17整理ppt設每個數據元素的查找概率相等，即Pi=，那么等概率情況下有：查找不成功時，關鍵字的比較次數總是n+1次。算法中的根本工作就是關鍵字的比較，因此，查找長度的量級就是查找算法的時間復雜度為O(n)。順序查找缺點是當n很大時，平均查找長度較大，效率低；優點是對表中數據元素的存儲沒有特殊要求。18整理ppt2.有序表的查找以有序表表示靜態查找表時，可用折半查找法來實現查找。折半查找的根本思想：在有序表中，取中間元素作為比較對象，假設給定值與中間元素的關鍵字相等，那么查找成功；假設給定值小于中間元素的關鍵字，那么在中間元素的左半區繼續查找；假設給定值大于中間元素的關鍵字，那么在中間元素的右半區繼續查找。不斷重復上述查找過程，直到查找成功，或所查找的區域無數據元素，查找失敗。折半查找也叫二分查找，是一種效率較高的查找方法，但前提是表中元素必須按關鍵字有序〔按關鍵字遞增或遞減〕排列。19整理ppt算法實現：設表長為n，low，high和mid分別指向待查元素所在區間的上界、下界和中點,k為給定值。初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較：假設k==r[mid].key，那么查找成功假設k<r[mid].key，那么high=mid-1假設k>r[mid].key，那么low=mid+1重復上述操作，直至low>high時，查找失敗20整理ppt算法描述：lowhighmid例

1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid21整理ppt例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid22整理ppt1234567891011513192137566475808892lowhighintbinsrch(JDr[],intn,intk){intlow,high,mid,found;low=1;high=n;found=0;//found為找到標志。值為0表示未找到。while((low<=high)&&(found==0)){mid=(low+high)/2;if(k>r[mid].key)low=mid+1;elseif(k==r[mid].key)found=1;elsehigh=mid-1;}if(found==1)//如果已找到return(mid);//找到的記錄的下標肯定為midelsereturn(0);}#defineM500typedefstruct{intkey;floatinfo;}JD;23整理ppt折半查找的性能分析：從折半查找的過程看，每次查找都是以表的中點為比較對象，并以中點將表分割為兩個子表，對定位到的子表繼續作同樣的操作。所以，對表中每個數據元素的查找過程，可用二叉樹來描述，稱這個描述查找過程的二叉樹稱為判定樹。判定樹中每一結點對應表中一個記錄，但結點值不是某個記錄的關鍵字，而是某個記錄在表中的位置序號。根結點對應當前區間的中間記錄，左子樹對應前一子表，右子樹對應后一子表。24整理ppt1185210741936判定樹：1234567891011513192137566475808892從上面判定樹可看到，查找第一層的根結點56，一次比較即可找到；查找第二層的結點19和80，二次比較即可找到；查找第三層的結點5、21、64、88，三次比較即可找到；查找第四層的結點13，37、75、92，四次比較即可找到。25整理pptn個結點的判定樹，樹高為k，那么有2k-1-1<n≤2k-1，即k-1<log2(n+1)≤k，所以k=log2(n+1)。因此，二分查找在查找成功時，進行的關鍵字比較次數至多為log2(n+1)。查找表中任一元素的過程，即是判定樹中從根到該元素結點路徑上各結點關鍵字的比較次數，也即該元素結點在樹中的層次數。以樹高為k的滿二叉樹(n=2k-1)為例。假設表中每個元素的查找是等概率的，即Pi=，那么樹的第i層有2i-1個結點。二分查找的平均查找長度為：26整理ppt所以，二分查找的時間復雜度為：O(log2n)。二分查找的優點：效率高。二分查找的缺點：必須按關鍵字排序，有時排序也很費時；只適用順序存儲結構，所以進行插入、刪除操作必須移動大量的結點。二分查找適用于一經建立就很少改動，而又經常需要查找的線性表。對于經常需要改動的線性表，可采用鏈表存儲結構，進行順序查找。27整理ppt3.索引順序表的查找假設以索引順序表表示靜態查找表，可用分塊查找法實現查找。分塊查找又稱索引順序查找，是順序查找的一種改進方法。查找過程：將表分成幾塊，塊內無序，塊間有序；先確定待查記錄所在塊，再在塊內查找。算法實現：用數組存放待查記錄，每個數據元素至少含有關鍵字域。建立索引表，每個索引表結點含有最大關鍵字域和指向本塊第一個結點的指針。28整理ppt12345678910111213141516171822121389203342443824486058745786532248861713索引表查38typedefstruct{intkey;intlink;}SD;typedefstruct{intkey;floatinfo;}JD;29整理pptintblocksrch(JDr[],SDd[],intb,intk,intn){inti=1,j;while((k>d[i].key)&&(i<=b))//確定要比較的值k在哪一塊i++;//k<=d[i].key時的i就確定了k所在塊的索引結點下標序號if(i>b){printf("\nNotfound");return(0);}j=d[i].link;//要比較的值k在以d[i].link為起點下標的塊中while((j<n)&&(k!=r[j].key)&&(r[j].key<=d[i].key))j++;//在所在塊中進行順序查找if(k!=r[j].key){j=0;printf("\nNotfound");}return(j);}索引表長順序表長30整理ppt分塊查找方法評價:31整理pptASL最大最小兩者之間表結構有序表、無序表有序表分塊有序表存儲結構順序存儲結構線性鏈表順序存儲結構順序存儲結構線性鏈表查找方法比較順序查找折半查找分塊查找32整理ppt9.2

動態查找表33整理ppt動態查找表特點：動態查找表用于頻繁進行插入、刪除、查找。表結構本身是在查找過程中動態生成的，即對于給定值key，假設表中存在其關鍵字等于key的記錄，那么查找成功返回，否那么插入關鍵字等于key的記錄。本節討論以各種樹結構表示動態查找表時的插入、刪除、查找的實現方法。34整理ppt1.二叉排序樹〔1〕二叉排序樹的定義二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：1〕假設它的左子樹不空，那么左子樹上所有結點的值均小于根結點的值；2〕假設它的右子樹不空，那么右子樹上所有結點的值均大于根結點的值；3〕它的左、右子樹也都分別是二叉排序樹。35整理ppt503080209010854035252388例如:是二叉排序樹。66不36整理ppt45125333724100619078按中序遍歷：3，12，24，37，45，53，61，78，90，100遞增中序遍歷二叉排序樹可得到一個關鍵字的有序序列。37整理ppttypedefstructBiTNode{//

結點結構

TElemTypedata;structBiTNode*lchild,*rchild;//左、右指針

}BiTNode,

*BiTree;通常，以二叉鏈表作為二叉排序樹的存儲結構：38整理ppt〔2〕二叉排序樹的查找算法假設二叉排序樹為空，那么查找不成功；否那么：1〕假設給定值等于根結點的關鍵字，那么查找成功；2〕假設給定值小于根結點的關鍵字，那么繼續在左子樹上進行查找；3〕假設給定值大于根結點的關鍵字，那么繼續在右子樹上進行查找。39整理ppt50308020908540358832例如:二叉排序樹查找關鍵字==

50

,505035

,503040355090

,50809095,40整理ppt從上述查找過程可見，在查找過程中，生成了一條查找路徑：

從根結點出發，沿著左分支或右分支逐層向下直至關鍵字等于給定值的結點;或者

從根結點出發，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功

——查找不成功41整理pptStatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指針T所指二叉排序樹中遞歸地查找其關鍵字等于key的數據元素，假設查找成功，那么返回指針p指向該數據元素的結點，并返回函數值為TRUE;否那么，說明查找不成功，返回指針p指向查找路徑上訪問的最后一個結點，并返回函數值為FALSE,指針f指向當前訪問的結點的雙親，其初始調用值為NULLif(!T){p=f;returnFALSE;}//查找不成功elseif(EQ(key,T->data.key)){p=T;returnTRUE;}//查找成功elseif(LT(key,T->data.key))SearchBST(T->lchild,key,T,p);//在左子樹中繼續查找elseSearchBST(T->rchild,key,T,p);//在右子樹中繼續查找}42整理ppt30201040352523fT設

key=48fTfT22pfTfTTTTfffp43整理ppt二叉排序樹的查找分析：

在二叉排序樹上查找其關鍵字等于給定值結點的過程，恰是走了一條從根結點到該結點的路徑的過程。含有n個結點的二叉樹是不唯一的，如何來進行查找分析呢？44整理ppt例如：上圖兩棵二叉排序樹中，結點的個數和值均相同。但〔a〕的深度為3，而〔b〕的深度為6。其等概率平均查找長度分別為：ASL(a)=(1*1+2*2+3*3)/6=14/6ASL(b)=(1*1+2*1+3*1+4*1+5*1+6*1)/6=21/6因此，二叉排序樹的平均查找長度和二叉樹的形態有關。最好情況下，二叉排序樹在生成過程中，樹的形態比較均勻，其最終得到的是一顆形態與二分查找的判定樹相似的二叉排序樹，如圖(a)所示。最壞情況下，二叉排序樹通過一個有序表的n個結點依次插入生成的，此時所得的二叉排序樹為一顆深度為n的單支樹，如圖(b)所示。它的平均查找長度和單鏈表的順序查找相同，也是〔n+1〕/2。對均勻的二叉排序樹進行插入或刪除結點后，應對其進行調整，使其依然保持均勻。45整理ppt(3)二叉排序樹的插入算法根據動態查找表的定義，插入操作在查找不成功時才進行。假設二叉排序樹為空樹，那么新插入的結點為新的根結點；否那么，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。4512533372410061907820例如：在右圖給定的二叉排序樹中插入結點2046整理pptStatusInsertBST(BiTree&T,ElemTypee){//當二叉排序樹中不存在關鍵字等于e.key的數據元素時，插入元素值為e的結點，并返回TRUE;否那么，不進行插入并返回FALSE。if(!SearchBST(T,e.key,NULL,p))//如果查找不成功，才進行插入{……}else//如果查找成功，那么不進行插入returnFALSE;}

47整理ppts=(BiTree)malloc(sizeof(BiTNode));

//

為新結點分配空間s->data=e;

s->lchild=s->rchild=NULL;

if(!p)T=s;//插入s為新的根結點elseif(LT(e.key,p->data.key))p->lchild=s;//插入*s為*p的左孩子elsep->rchild=s;//插入*s為*p的右孩子returnTRUE;//插入成功48整理ppt(4)二叉排序樹的刪除算法

和插入相反，刪除在查找成功之后進行，并且要求刪除二叉排序樹上某個結點之后，仍然保持二叉排序樹的特性。可分三種情況討論：1〕被刪除的結點是葉子；2〕被刪除的結點只有左子樹或者只有右子樹；3〕被刪除的結點既有左子樹，也有右子樹。49整理ppt50308020908540358832被刪除的結點是葉子結點。例如:被刪關鍵字=2088其雙親結點中相應指針域的值改為“空〞50整理ppt50308020908540358832被刪除的結點只有左子樹或者只有右子樹其雙親結點的相應指針域的值改為“指向被刪除結點的左子樹或右子樹〞。被刪關鍵字=408051整理ppt50308020908540358832被刪除的結點既有左子樹，也有右子樹。4040以其前驅替代之，然后再刪除該前驅結點。被刪結點前驅結點被刪關鍵字=5052整理pptStatusDeleteBST(BiTree&T,KeyTypekey){//假設二叉排序樹T中存在其關鍵字等于key的數據元素，那么刪除該數據元素結點，并返回函數值TRUE，否那么返回函數值FALSE。if(!T)//假設T為空returnFALSE;//不存在關鍵字等于key的數據元素else{if(EQ(key,T->data.key)){Delete(T);returnTRUE;}//找到關鍵字等于key的數據元素elseif(LT(key,T->data.key))DeleteBST(T->lchild,key);//繼續在左子樹中進行查找，刪除elseDeleteBST(T->rchild,key);//繼續在右子樹中進行查找，刪除}}53整理pptvoidDelete(BiTree&p){//從二叉排序樹中刪除結點p，并重接它的左子樹或右子樹

if(!p->rchild){……}elseif(!p->lchild){……}else{……}}其中刪除操作過程如下所描述：54整理ppt//右子樹為空樹那么只需重接它的左子樹q=p;p=p->lchild;free(q);pp55整理ppt//左子樹為空樹只需重接它的右子樹q=p;p=p->rchild;free(q);pp56整理pptq=p;s=p->lchild;//轉左while(s->rchild)//轉左后，到右盡頭{q=s;s=s->rchild;}

//q

指向s

的雙親，s指向被刪結點的前驅p->data=s->data;//以前驅結點的數據替換被刪結點的數據if(q!=p)q->rchild=s->lchild;//重接*q的右子樹

elseq->lchild=s->lchild;//重接*q的左子樹free(s);//左右子樹均不空pqs57整理ppt(5)二叉排序樹的構造過程例：記錄的關鍵字序列為：33，50，42，18，39，9，77，44，2，11，24，那么構造一棵二叉排序樹的過程如下：從空樹開始建立二叉排序樹的過程圖示58整理ppt一個無序序列可以通過構造二叉排序樹而成為一個有序序列。每次插入新結點都是二叉排序樹上新的葉子結點，不必移動其它結點，僅需改動某個結點指針，由空變為非空即可。59整理ppt#include<stdio.h>typedefintTElemType;typedefstructBiTNode{//結點結構

TElemTypedata;structBiTNode*lchild,*rchild;//左、右指針

}BiTNode,*BiTree;生成二叉排序樹的算法：60整理pptvoidInsBST(BiTree&T,TElemTypeK){BiTNode*f,*p;p=T;while(p)//當p為空時，即左孩子或右孩子為空時，p不再往下指//即從根結點開始找插入的位置，找到后，f為要插入位置的雙親結點的地址{if(p->data==K){printf("樹中已有%d，不需插入\n",K);return;}f=p;p=(K<p->data)?p->lchild:p->rchild;//p指向自己的左孩子或右孩子，f指向左右孩子的雙親}p=newBiTNode;//申請一個新結點，把輸入的值放入新結點p->data=K;p->lchild=p->rchild=NULL;if(T==NULL)//如果根結點為空，新結點為根結點T=p;elseif(K<f->data)//如果輸入值小于它的根結點，那么作為此根結點的左孩子f->lchild=p;elsef->rchild=p;//如果輸入值大于它的根結點，那么作為此根結點的右孩子}61整理pptBiTreeCreateBST(){BiTreeT;//T是一個指針變量，指向二叉排序樹的根結點

TElemTypeK;T=NULL;printf("請輸入一個整數關鍵字(輸入0時結束輸入)：");scanf("%d",&K);while(K){InsBST(T,K);printf(“請輸入下一個整數關鍵字(輸入0時結束輸入)：");scanf("%d",&K);}returnT;}voidmain(){CreateBST();}62整理ppt例如:548254821是平衡樹不是平衡樹平衡二叉樹的定義：又稱AVL樹。它或者是一棵空樹，或者是具有以下性質的二叉樹：1〕它的左子樹和右子樹高度之差的絕對值不超過1；2〕它的左子樹和右子樹都是平衡二叉樹。2.二叉平衡樹63整理ppt二叉樹上結點的平衡因子：為該結點的左子樹的深度減去它的右子樹的深度。平衡二叉樹上所有結點的平衡因子只可能是：-1、0、1

64整理ppt65整理ppt在插入過程中，采用平衡旋轉技術。例如：依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉一次先向右旋轉再向左旋轉構造二叉平衡樹的方法：66整理ppt426589642895向左旋轉一次67整理ppt當平衡的二叉排序樹因插入結點而失去平衡時，僅需對離插入結點最近的最小不平衡子樹進行平衡旋轉處理即可。平衡旋轉處理可分為以下4種情況：〔1〕單向右旋〔順時針〕〔2〕單向左旋〔逆時針〕〔3〕先左后右雙向旋轉〔4〕先右后左雙向旋轉68整理ppt例：一棵平衡二叉排序樹如圖〔a〕所示。在A的左子樹的左子樹上插入15后，導致失衡，如圖〔b〕所示。為恢復平衡并保持二叉排序樹的特性，可將A改為B的右子，B原來的右子改為A的左子，如圖〔c〕所示。這相當于以B為軸，對A做了一次順時針旋轉。

不平衡二叉樹的調整(1)

69整理ppt例：一棵平衡二叉排序樹如圖〔a〕所示。在A的右子樹B的右子樹上插入70后，導致失衡，如圖〔b〕所示。為恢復平衡并保持二叉排序樹的特性，可將A改為B的左子，B原來的左子改為A的右子，如圖〔c〕所示。這相當于以B為軸，對A做了一次逆時針旋轉。不平衡二叉樹的調整(2)

70整理ppt例：一棵平衡二叉排序樹如圖〔a〕所示。在A的左子樹B的右子樹上插入45后，導致失衡，如圖〔b〕所示。為恢復平衡并保持二叉排序樹的特性，可首先將B改為C的左子，而C原來的左子改為B的右子；然后將A改為C的右子，C原來的右子改為A的左子，如圖〔c〕所示。這相當于對C做了一次逆時針旋轉，對A做了一次順時針旋轉。71整理ppt不平衡二叉樹的調整(3)72整理ppt例：一棵平衡二叉排序樹如圖〔a〕所示。在A的右子樹的左子樹上插入55后，導致失衡，如圖〔b〕所示。為恢復平衡并保持二叉排序樹的特性，可首先將B改為C的右子，而C原來的右子改為B的左子；然后將A改為C的左子，C原來的左子改為A的右子，如圖〔c〕所示。這相當于對C做了一次順時針旋轉，對A做了一次逆時針旋轉。73整理ppt不平衡二叉樹的調整(4)74整理ppt在二叉平衡樹上進行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進行比較的關鍵字的個數不超過平衡樹的深度。二叉平衡樹的查找性能分析：問，含n個關鍵字的二叉平衡樹可能到達的最大深度是多少？75整理pptn=0空樹最大深度為

0n=1最大深度為

1n=2最大深度為

2n=4最大深度為

3n=7最大深度為

4先看幾個具體情況:76整理ppt反過來問，深度為

h的二叉平衡樹中所含結點的最小值Nh

是多少？h=0N0=0h=1h=2h=3一般情況下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用歸納法可證得Nh=Fh+2-177整理ppt因此，在二叉平衡樹上進行查找時，查找過程中和給定值進行比較的關鍵字的個數和log(n)相當。即：在二叉平衡樹上進行查找的時間復雜度為Olog(n)。由此推得，深度為

h的二叉平衡樹中所含結點的最小值Nh=

h+2/5-1。反之，含有n

個結點的二叉平衡樹能達到的最大深度為：hn=log

(5(n+1))-2。78整理ppt9.3

哈希表79整理ppt1.什么是哈希表以上討論的查找方法，由于數據元素的存儲位置與關鍵字之間不存在確定的關系，因此，查找時，需要進行一系列對關鍵字的查找比較，即查找算法是建立在比較的根底上的，查找效率由比較一次縮小的查找范圍決定。理想的情況是依據關鍵字直接得到其對應的數據元素位置，即要求關鍵字與數據元素間存在一一對應關系，通過這個關系，能很快地由關鍵字得到對應的數據元素位置。80整理ppt例：11個元素的關鍵字分別為18，27，1，20，22，6，10，13，41，15，25。選取關鍵字與元素位置間的函數為：f(key)=keymod111.通過這個函數對11個元素建立查找表如下：

01234567891010204118627152513122查找時，對給定值kx通過這個函數計算出地址，再將kx與該地址單元中元素的關鍵字比較，假設相等，查找成功。81整理ppt哈希表與哈希方法：選取某個函數，依據該函數按關鍵字計算數據元素的存儲地址，并按此地址存放數據元素；查找時，由同一個函數對給定值kx計算出地址，將kx與該地址單元中數據元素的關鍵字進行比較，確定查找是否成功，這就是哈希方法。哈希方法中使用的轉換函數稱為哈希函數。哈希方法中計算的存儲地址稱為哈希地址或散列地址。按這個思想構造的查找表稱為哈希表。82整理ppt對于n個數據元素的集合，總能找到關鍵字與存放地址一一對應的函數。假設最大關鍵字為m，可以分配m個數據元素存放單元，選取函數f(key)=key即可，但這樣會造成存儲空間的很大浪費，甚至不可能分配這么大的存儲空間。通常關鍵字的集合比哈希地址集合大得多，因而經過哈希函數變換后，可能將不同的關鍵字映射到同一個哈希地址上，這種現象稱為沖突。83整理ppt沖突不可能防止，只能盡可能減少。所以，哈希方法需要解決以下兩個問題：1〕構造好的哈希函數a.所選函數盡可能簡單，以便提高轉換速度。b.所選函數對關鍵字計算出的地址，應在哈希地址集中大致均勻分布，以減少空間的浪費。2〕制定解決沖突的方案。換句話說，就是使關鍵字經過哈希函數得到一個隨機的地址，以便使一組關鍵字的哈希地址均勻分布在整個地址區間中，從而減少沖突。84整理ppt2.哈希函數的構造方法〔1〕直接定址法Hash(key)=a·key+b(a、b為常數)即：取關鍵字的某個線性函數值為哈希地址。這類函數是一一對應函數，不會產生沖突，但要求地址集合與關鍵字集合大小相同，因此，對于較大的關鍵字集合不適用。實際中能使用這種哈希函數的情況很少。例：關鍵字集合為{20，30，50，60，80，90}，選取哈希函數為：Hash(key)=key/10，那么存放如下：0123456789關鍵字存放地址圖示80605030209085整理ppt〔2〕除留余數法Hash(key)=keymodp(p是一個整數)即：取關鍵字除以p的余數作為哈希地址。使用除留余數法，選取適宜的p很重要，假設哈希表表長為m，那么要求p≤m，且接近m或等于m。p一般選取質數，也可以是不包含小于20質因子的合數。這是一種最簡單，也最常用的構造哈希函數的方法。86整理ppt〔3〕平方取中法對關鍵字平方后，按哈希表大小，取中間的假設干位作為哈希地址。例：假設存儲區域可存100個記錄，關鍵字=4731那么4731×4731=22382361 取地址82例：假設存儲區域可存10000個記錄，關鍵字=14625那么14625×14625=213890625 取地址8906取的位數由表長決定，這是一種較常用的構造哈希函數的方法。87整理ppt3.處理沖突的方法〔1〕開放定址法所謂開放定址法，即是由關鍵字得到的哈希地址一旦產生了沖突，也就是說，該地址已經存放了數據元素，就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數據元素存入。1〕線性探測法Hi=(Hash(key)+di)modm(1≤i<m)其中：Hash(key)為哈希函數m為哈希表長度di=i； i=1，2，3，…，m-188整理ppt例：關鍵字集為{47，7，29，11，16，92，22，8，3}，哈希表表長為11，Hash(key)=keymod11。用線性探測法處理沖突，建表如下：

01234

5

6

78

910829731692472211△△△▲

用線性探測法處理沖突的哈希表圖示47、7、11、16、92均是由哈希函數得到的沒有沖突的哈希地址而直接存入的；

Hash(29)=7，哈希地址上沖突，需尋找下一個空的哈希地址。由H1=(Hash(29)+1)mod11=8，哈希地址8為空，將29存入。另外，22、8同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的；89整理ppt而Hash(3)=3，哈希地址上沖突，由

H1=(Hash(3)+1)mod11=4仍然沖突；

H2=(Hash(3)+2)mod11=5仍然沖突；

H3=(Hash(3)+3)mod11=6找到空的哈希地址，存入。線性探測法可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，……，因此，可能出現很多元素在相鄰的哈希地址上“堆積〞起來，大大降低了查找效率。為此，可采用二次探測法，或雙哈希函數探測法，以改善“堆積〞問題。90整理ppt2〕二次探測法〔平方探測法〕

Hi=(Hash(key)±di)modm

其中：Hash(key)為哈希函數

m為哈希表長度，m要求是