第9章-查找lianxi 數(shù)據(jù)結(jié)構(gòu)

復(fù)習(xí)最短路徑

求從源點到其余各點的最短路徑的算法的基本思想:依最短路徑的長度遞增的次序求得各條路徑源點v1…其中，從源點到頂點v的最短路徑是所有最短路徑中長度最短者。v2在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。下一條路徑長度次短的最短路徑的特點：路徑長度最短的最短路徑的特點：

它只可能有兩種情況：或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過頂點v1，再到達該頂點(由兩條弧組成)。其余最短路徑的特點：再下一條路徑長度次短的最短路徑的特點:

它可能有三種情況：或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過頂點v1，再到達該頂點(由兩條弧組成)；或者是從源點經(jīng)過頂點v2，再到達該頂點。

它或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過已求得最短路徑的頂點，再到達該頂點。13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點從V0到各終點的最短路徑及其長度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329課堂練習(xí)1試?yán)肈ijkstra算法求圖中從頂點a到其他各頂點間的最短路徑，列表寫出執(zhí)行算法過程中各步的狀態(tài)。解答練習(xí)2試?yán)肈ijkstra算法求圖中從頂點a到其他各頂點間的最短路徑，列表寫出執(zhí)行算法過程中各步的狀態(tài)。15bgdeafc122894510246數(shù)據(jù)結(jié)構(gòu)第9章查找9.1查找的基本概念9.2

線性表的查找9.3

樹表的查找9.4哈希表的查找教學(xué)內(nèi)容1.熟練掌握順序表和有序表（折半查找）的查找算法及其性能分析方法；2.熟練掌握二叉排序樹的構(gòu)造和查找算法及其性能分析方法；3.掌握二叉排序樹的插入算法，了解二叉排序樹的刪除算法；4.熟練掌握哈希函數(shù)（除留余數(shù)法）的構(gòu)造5.熟練掌握哈希函數(shù)解決沖突的方法及其特點

教學(xué)目標(biāo)教學(xué)目的和要求：了解各種查找算法的思想。掌握各種查找算法的寫法。重點和難點：各種查找算法思想。算法的實現(xiàn)及其時間、空間復(fù)雜度分析。授課時間：6課時本章將討論一種在實際中大量使用的數(shù)據(jù)結(jié)構(gòu)——查找表，它或者基于線性結(jié)構(gòu)構(gòu)建，或者基于非線性結(jié)構(gòu)構(gòu)建。查找表的例子：編譯程序中的符號表、網(wǎng)絡(luò)中的路由表、OS中的文件分配表等。幾個概念

查找表：用于查找的數(shù)據(jù)元素集合稱為查找表。查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的數(shù)據(jù)結(jié)構(gòu)。查找表的操作（1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；（2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；（3）在查找表中插入一個數(shù)據(jù)元素；（4）從查找表中刪去某個數(shù)據(jù)元素。靜態(tài)查找表：若對查找表僅作查詢和檢索操作，則稱此類查找表為靜態(tài)查找表（StaticSearchTable）。動態(tài)查找表：若在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素，則稱此類表為動態(tài)查找表（DynamicSearchTable）。關(guān)鍵字：所謂關(guān)鍵字(key)，是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值，用它可以標(biāo)識(或識別)一個數(shù)據(jù)元素。主關(guān)鍵字：若此關(guān)鍵字能唯一標(biāo)識一個數(shù)據(jù)元素，則稱此關(guān)鍵字為主關(guān)鍵字（PrimaryKey）。次關(guān)鍵字：能夠標(biāo)識多個記錄的關(guān)鍵字，稱為次關(guān)鍵字。查找成功：查找表中查找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素。若表中有這樣的元素，則稱查找成功查找不成功：查找表中查找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素。若表中沒有這樣的元素，則稱查找不成功9.1靜態(tài)查找表9.1靜態(tài)查找表 表中數(shù)據(jù)是固定不變的。9.1.1順序表的順序查找 以順序表或鏈表作為靜態(tài)查找表，都可以用順序查找方法來查找元素。我們在這里介紹順序表的順序查找。1、一般的順序查找 思想：從表中最后一個記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比較，若某個記錄的關(guān)鍵字和給定值表角相等，則查找成功，找到所查記錄；反之，若直至第一個記錄，其關(guān)鍵字和給定值比較都不等，則表明表中沒有所查記錄，查找不成功。一般查找算法：#include<iostream>#include<vector>usingnamespacestd;intsearch1(vector<int>v,inte){ inti=v.size()-1;

while(1) { if(i==0)return0; if(v[i]==e)returni; i--; }}2、帶“哨兵”的順序查找intsearch2(vector<int>v,inte){ inti=v.size()-1; v[0]=e;//哨兵

while(1) { if(v[i]==e)returni; i--; }}intSearch_Seq(SSTableST,KeyTypekey){

//若成功返回其位置信息，否則返回0

ST.R[0].key=key;

for(i=ST.length;ST.R[i].key!=key;--i);

//不用for(i=n;i>0;--i)或for(i=1;i<=n;i++)

returni;

}比較這兩個算法可以發(fā)現(xiàn)，循環(huán)內(nèi)插了一條比較語句。市價表明，這個改進能使順序查找在表長大于1000時，進行一次查找所需的平均時間幾乎減少一半。3、性能分析平均查找長度的概念：為確定記錄在查找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。①等概率查找246810查找表：現(xiàn)在有100人對表中數(shù)據(jù)進行查詢：20人查找2，從左向右查找，需要表1次20人查找4，從左向右查找，需要表2次20人查找6，從左向右查找，需要表3次20人查找8，從左向右查找，需要表4次20人查找10，從左向右查找，需要表5次那么這100人共需查找多少次，才能各自找到自己需要的數(shù)據(jù)？共需：SL=20*1+20*2+20*3+20*4+20*5平均查找次數(shù)：ASL=SL/100 =20%*1+20%*2+20%*3+20%*4+20%*5那么其中的百分數(shù)可以理解為查找某個元素的概率。所以平均查找長度可以用公式表示為：其中：Pi為查找表中第i個元素的概率Ci為查找表中第i個元素需要比較的次數(shù)根據(jù)上面式子，等概率查找時，P1=P2=P3=…=Pn=1/n②非等概率查找 如某人有很多人的聯(lián)系電話，存放在一個順序表中，他一定會把聯(lián)系得最頻繁的號碼放在最前面，以利于查找。空間復(fù)雜度：一個輔助空間。時間復(fù)雜度：1)查找成功時的平均查找長度設(shè)表中各記錄查找概率相等

ASLs(n)=(1+2+...+n)/n=(n+1)/22)查找不成功時的平均查找長度ASLf

=n+1順序查找的性能分析算法簡單，對表結(jié)構(gòu)無任何要求（順序和鏈?zhǔn)剑﹏很大時查找效率較低改進措施：非等概率查找時，可按照查找概率進行排序。順序查找算法有特點9.1若對大小均為n的有序順序表和無序順序表分別進行順序查找，試在下列三種情況下分別討論兩者在等概率時平均查找長度是否相同？（1）查找不成功，即表中沒有關(guān)鍵字等于給的值K的記錄；(1)相同，有序n+1;無序n+1（2）查找成功，且表中只有一個關(guān)鍵字等于給定值K的記錄；(2)相同，有序(n+1)/2；無序(n+1)/2（3）查找成功，且表中有若干關(guān)鍵字等于給定值K的記錄，要求找出所有這些記錄。(3)不相同，對于有序表，找到了第一個與K相同的元素后，只要再找到與K不同的元素，即可停止查找；對于無序表，則要一直查找到最后一個元素。9.1.2有序表的查找——折半查找一、折半查找的前提條件必須是順序表順序表中元素必須是有序的二、折半查找算法演示1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowv1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowmidmid=（low+high）/2=(1+11)/2=6v1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowmidkey=21<v[mid]=56。所以key應(yīng)該處于區(qū)間[low，mid-1]中v1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowv1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(1+5)/2=31、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidkey=21>v[mid]=19。所以key應(yīng)該處于區(qū)間[mid+1，high]中1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowv1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(4+5)/2=4取不大于小數(shù)的整數(shù)1、查找成功的演示(查找key=21)12345678910110513192137566475808892highlowvmidkey=21==v[mid]=21。查找成功，返回。2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(1+11)/2=62、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidkey=85>v[mid]=56。所以key應(yīng)該處于區(qū)間[mid+1,high]中2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(7+11)/2=92、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidkey=85>v[mid]=80。所以key應(yīng)該處于區(qū)間[mid+1,high]中2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidmid=（low+high）/2=(10+11)/2=102、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowvmidkey=85<v[mid]=88。所以key應(yīng)該處于區(qū)間[low,mid-1]中2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv2、查找不成功的演示（查找key=85）12345678910110513192137566475808892highlowv因為high<low，查找失敗3、算法實現(xiàn)intBinSearch(vector<ElemType>ST,ElemTypeelem){ intlow=1; inthigh=ST.size()-1; while(low<high) { intmid=(low+high)/2; if(ST[mid]==elem)returnmid; elseif(ST[mid]>elem)high=mid-1; elselow=mid+1; } return0;}4、算法分析12345678910110513192137566475808892v12345678910110513192137566475808892v5605，13，19，21，3764，75，80，88，924、算法分析12345678910110513192137566475808892v5605，13，64，75，198021，3788，924、算法分析12345678910110513192137566475808892v56198051352137647592884、算法分析如上面演示過程，按照折半查找過程，可以相應(yīng)的畫出一棵二叉樹，稱為折半查找對應(yīng)的判定樹。所以，折半查找實際上就是其判定樹的查找。而每次查找所要比較的次數(shù)均不會超過樹的高度。結(jié)論:對于n個數(shù)據(jù)（n>50）,進行折半查找時，平均查找長度近似為：-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外結(jié)點內(nèi)結(jié)點><=ASL＝1/11*(1*1＋2×2＋4×3+4*4)＝33/11=3練習(xí):假定每個元素的查找概率相等，求查找成功時的平均查找長度。查找成功時比較次數(shù)：為該結(jié)點在判定樹上的層次數(shù)，不超過樹的深度d=log2n+1查找不成功的過程就是走了一條從根結(jié)點到外部結(jié)點的路徑d或d-1。-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外結(jié)點內(nèi)結(jié)點><=查找過程：每次將待查記錄所在區(qū)間縮小一半，比順序查找效率高,時間復(fù)雜度O(log2n)適用條件：采用順序存儲結(jié)構(gòu)的有序表，不宜用于鏈?zhǔn)浇Y(jié)構(gòu)折半查找的性能分析9.1.4索引順序表的查找1、索引順序表思想演示 對于索引的概念，最典型的就是字典。1234567891011121314151617182212138920334244382448605874498653

對于順序表，如果表中數(shù)據(jù)分塊有序，則可進行索引順序查找。1234567891011121314151617182212138920334244382448605874498653

如上圖，其中的數(shù)據(jù)總體上可以平均劃分成3部分，后面一部分中的數(shù)據(jù)均比前面一部分中最大數(shù)據(jù)大1234567891011121314151617182212138920334244382448605874498653

可以為每一塊建立一個索引項，包括兩個域：一個是該塊中最大的關(guān)鍵字的值；一個是該塊的起始位置。1234567891011121314151617182212138920334244382448605874498653最大關(guān)鍵字起始地址1234567891011121314151617182212138920334244382448605874498653最大關(guān)鍵字22起始地址11234567891011121314151617182212138920334244382448605874498653最大關(guān)鍵字2248起始地址171234567891011121314151617182212138920334244382448605874498653最大關(guān)鍵字224886起始地址17132、查找方法演示(1)查找381234567891011121314151617182212138920334244382448605874498653最大關(guān)鍵字224886起始地址17131234567891011121314151617182212138920334244382448605874498653最大關(guān)鍵字224886起始地址1713先從索引表中查找，可以采取順序查找，也可以采取折半查找。發(fā)現(xiàn)22<38<48,可以判定38如果存在，就應(yīng)該在第二塊中。根據(jù)第二塊的起始地址和第三塊的起始地址，我們可以確定38的范圍[7，13）之間。1234567891011121314151617182212138920334244382448605874498653最大關(guān)鍵字224886起始地址1713在確定的范圍內(nèi)進行順序查找，如果能找到，則查找成功；否則，查找失敗。3、算法分析從總體上可以知道，查找時間可以分為兩部分：索引表的查找塊的查找假設(shè)有n個數(shù)據(jù)，被均勻的分成b塊，則每塊有s=n/b個數(shù)據(jù)那么索引表應(yīng)該有b項對索引表進行折半查找，近似為在塊中進行順序查找，為：所以，索引順序表的平均查找長度近似為：靜態(tài)查找表與動態(tài)查找表的根本區(qū)別在于

。A)它們的邏輯結(jié)構(gòu)不一樣

B)施加于其上的操作不同

C)所包含的數(shù)據(jù)元素的類型不一樣

D)存儲實現(xiàn)不一樣采用二分查找的方法查找長度為n的有序表時，查找每個元素時平均比較次數(shù)與對應(yīng)判定樹的的高度（假定高度不小于2）的關(guān)系為

。A)前者小于后者

B)前者大于后者

C)前者等于后者

D)前者大于等于后者對線性表進行二分法查找，其前提條件是

。A)線性表以順序方式存儲，并且按關(guān)鍵碼值排好序

B)線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序C)線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序

D)線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序

設(shè)有100個元素，用折半查找法進行查找時，最大比較次數(shù)是_____。A.25 B.50 C.10 D.79.2動態(tài)查找表

動態(tài)查找表的特點是：表結(jié)構(gòu)本身是在查找過程中生成的，即對于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。 動態(tài)查找表也可以有不同的表示方法，本節(jié)將討論以各種樹結(jié)構(gòu)表示時的實現(xiàn)方法。9.2.1二叉排序樹和平衡二叉樹

1、二叉排序樹及其查找過程

二叉排序樹的概念： 二叉排序樹(BinarySortTree)又稱二叉查找(搜索)樹(BinarySearchTree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹：（1）若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；（2）若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；（3）左、右子樹本身又各是一棵二叉排序樹。

234578234578兩棵二叉排序樹

（a）（b）二叉排序樹的形態(tài)：練習(xí)下列圖形中，哪個不是二叉排序樹？451253337241006190783，12，24，37，45，53，61，78，90，100遞增得到一個關(guān)鍵字的遞增有序序列練習(xí)中序遍歷二叉排序樹后的結(jié)果有什么規(guī)律？若查找的關(guān)鍵字等于根結(jié)點，成功否則若小于根結(jié)點，查其左子樹若大于根結(jié)點，查其右子樹在左右子樹上的操作類似12225030011020099105230216二叉排序樹的操作－查找（1）若二叉排序樹為空，則查找失敗，返回空指針。（2）若二叉排序樹非空，將給定值key與根結(jié)點的關(guān)鍵字T->data.key進行比較：①若key等于T->data.key，則查找成功，返回根結(jié)點地址；②若key小于T->data.key，則進一步查找左子樹；③若key大于T->data.key，則進一步查找右子樹?！舅惴ㄋ枷搿緽STreeSearchBST(BSTreeT,KeyTypekey){if((!T)||key==T->data.key)returnT; elseif(key<T->data.key)returnSearchBST(T->lchild,key); //在左子樹中繼續(xù)查找

elsereturnSearchBST(T->rchild,key); //在右子樹中繼續(xù)查找}//SearchBST【算法描述】二叉排序樹的操作－插入插入的元素一定在葉結(jié)點上若二叉排序樹為空，則插入結(jié)點應(yīng)為根結(jié)點否則，繼續(xù)在其左、右子樹上查找樹中已有，不再插入樹中沒有，查找直至某個葉子結(jié)點的左子樹或右子樹為空為止，則插入結(jié)點應(yīng)為該葉子結(jié)點的左孩子或右孩子4512533372410061907820插入結(jié)點20二叉排序樹的操作－插入{10，18，3，8，12，2，7}10101810183101838101838121018381221018381227從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹二叉排序樹的操作－生成二叉排序樹的手工構(gòu)造過程設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}初始情況下，為空樹。45在樹中不存在，應(yīng)該插入。設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}4524在樹中不存在，應(yīng)該插入，且插入位置為45的左孩子。二叉排序樹的手工構(gòu)造過程設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}4553在樹中不存在，應(yīng)該插入，且插入位置為45的右孩子。24二叉排序樹的手工構(gòu)造過程設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}4545在樹中存在，忽略。2453二叉排序樹的手工構(gòu)造過程設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}45245312在樹中不存在，應(yīng)該插入，且插入位置為24的左孩子。二叉排序樹的手工構(gòu)造過程設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}4524531224在樹中存在，忽略。二叉排序樹的手工構(gòu)造過程設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}4524531290在樹中不存在，應(yīng)該插入，且插入位置為53的右孩子。二叉排序樹的手工構(gòu)造過程設(shè)關(guān)鍵字序列為{45，24，53，45，12，24，90}45245312完畢！?。?0二叉排序樹的手工構(gòu)造過程4524531290中序序列為：12，24，45，53，90中序遍歷二叉排序樹得到一個關(guān)鍵字的有序序列：不同插入次序的序列生成不同形態(tài)的二叉排序樹4024551237122437405540，24，12，37，5512，24，37，40，55二叉排序樹的操作－生成作業(yè)3、二叉排序樹的刪除 怎樣從二叉排序樹中刪除一個結(jié)點呢？假設(shè)在二叉排序樹上被刪結(jié)點為p，其雙親結(jié)點為f，設(shè)p是f的左孩子（不失一般性，p是f的右孩子時，方法一樣）。下面分3種情況進行討論：

（1）若p是葉子結(jié)點，由于刪去葉子結(jié)點不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親結(jié)點指向其的指針為空即可。（2）若p結(jié)點只有左子樹PL或者只有右子樹PR，此時只要令PL或者PR直接成為其雙親結(jié)點f的左子樹即可。（因為前提是p是f的左孩子）

（3）若p結(jié)點的左子樹和右子樹均不空，處理起來有些復(fù)雜。可以有兩種處理方法，我們結(jié)合圖來說明。

2023/2/3SQPLP中序遍歷：QSPLPSQP中序遍歷：QSP(2)SPPLQ中序遍歷：PLPSQSPQ中序遍歷：PSQ(1)（1）若p是葉子結(jié)點，由于刪去葉子結(jié)點不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親結(jié)點指向其的指針為空即可。（2）若p結(jié)點只有左子樹PL或者只有右子樹PR，此時只要令PL或者PR直接成為其雙親結(jié)點f的左子樹即可。（因為前提是p是f的左孩子）

（3）若p結(jié)點的左子樹和右子樹均不空，處理起來有些復(fù)雜。可以有兩種處理方法，我們結(jié)合圖來說明。

2023/2/3SQPLP中序遍歷：QSPLPSQPL中序遍歷：QSPL(2)SPPLQ中序遍歷：PLPSQSPLQ中序遍歷：PLSQ(1)2023/2/3中序遍歷：PPRSQSPRQ中序遍歷：PRSQ(3)SPPRQ中序遍歷：QSPPRSQPR中序遍歷：QSPR(4)SQPRP（1）若p是葉子結(jié)點，由于刪去葉子結(jié)點不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親結(jié)點指向其的指針為空即可。（2）若p結(jié)點只有左子樹PL或者只有右子樹PR，此時只要令PL或者PR直接成為其雙親結(jié)點f的左子樹即可。（因為前提是p是f的左孩子）

（3）若p結(jié)點的左子樹和右子樹均不空，處理起來有些復(fù)雜?？梢杂袃煞N處理方法，我們結(jié)合圖來說明。

2023/2/3例805012060110150557053刪除508060120110150557053刪除60805512011015053701032581354刪除1083255134刪除58325413第一種方式：FPCQSPRCLQLSLfpcqs刪除結(jié)點p前的二叉樹FCQSPRCLQLSLfcqs（a）刪除p，以PR作為S的右子樹的情形第二種方式FPCQSPRCLQLSLfpcqs刪除結(jié)點p前的二叉樹FSCQPRCLQLfpcqSL（b）刪除p，以S替代P的情形4、二叉排序樹的查找分析（1）同樣的n個關(guān)鍵字，輸入順序不同，構(gòu)造出的二叉排序樹不同。①輸入序列為{45，24，53，12，37，93}①輸入序列為{45，24，53，12，37，93}45①輸入序列為{45，24，53，12，37，93}4524①輸入序列為{45，24，53，12，37，93}452453①輸入序列為{45，24，53，12，37，93}45245312①輸入序列為{45，24，53，12，37，93}4524531237①輸入序列為{45，24，53，12，37，93}452453123793②輸入序列為{12，24，37，45，53，93}②輸入序列為{12，24，37，45，53，93}12②輸入序列為{12，24，37，45，53，93}1224②輸入序列為{12，24，37，45，53，93}122437②輸入序列為{12，24，37，45，53，93}12243745②輸入序列為{12，24，37，45，53，93}1224374553②輸入序列為{12，24，37，45，53，93}122437455393退化成了單鏈表結(jié)構(gòu)。第i層結(jié)點需比較i次。在等概率的前提下，上述兩圖的平均查找長度為：40245512371224374055查找的性能分析平均查找長度和二叉樹的形態(tài)有關(guān)，即，最好：log2n（形態(tài)勻稱，與二分查找的判定樹相似）最壞:（n+1)/2（單支樹）查找的性能分析40245512371224374055問題：如何提高二叉排序樹的查找效率？

盡量讓二叉樹的形狀均衡左、右子樹是平衡二叉樹；所有結(jié)點的左、右子樹深度之差的絕對值≤1平衡二叉樹平衡因子:該結(jié)點左子樹與右子樹的高度差任一結(jié)點的平衡因子只能?。?1、0或1；如果樹中任意一個結(jié)點的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對于一棵有n個結(jié)點的AVL樹，其高度保持在O(log2n)數(shù)量級，ASL也保持在O(log2n)量級。(a)平衡樹(b)不平衡樹練習(xí)：判斷下列二叉樹是否AVL樹？00011-1-120001-15261374一棵平衡二叉樹43821756一棵非平衡二叉樹（2）平衡化處理①單向右旋平衡化處理：如果在結(jié)點p的左孩子的左子樹上插入一個新結(jié)點而導(dǎo)致p結(jié)點失衡的話，那么就需要一個單向右旋的操作。1087ppvoidR_Rotate(Node*&p){Node*LC=p->lchild;p->lchild=LC->rchild;LC->rchild=p;p=LC;}691110876911LC右旋（2）平衡化處理②單向左旋平衡化處理：如果在結(jié)點p的右孩子的右子樹上插入一個新結(jié)點而導(dǎo)致p結(jié)點失衡的話，那么就需要一個單向左旋的操作。101213pvoidL_Rotate(Node*&p){Node*RC=p->rchild;p->rchild=RC->lchild;RC->lchild=p;p=RC;}14911RC101213p14911左旋（2）平衡化處理③先左旋后右旋：如果在結(jié)點p的左孩子的右子樹上插入一個新結(jié)點而導(dǎo)致p結(jié)點失衡的話，那么就需要一個先左旋后右旋的操作。10118p976左旋10119p68710119p687voidLR_Rotate(Node*&p){L_Rotate(p->lchild);R_Rotate(p);}右旋（2）平衡化處理③先右旋后左旋：如果在結(jié)點p的右孩子的左子樹上插入一個新結(jié)點而導(dǎo)致p結(jié)點失衡的話，那么就需要一個先右旋后左旋的操作。101213p14911RC101213p14911右旋左旋101213p14911voidRL_Rotate(Node*&p){R_Rotate(p->rchild);L_Rotate(p);}013037024練習(xí)：請將下面序列構(gòu)成一棵平衡二叉排序樹

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053

6、平衡二叉樹的查找分析(1)高度為h的平衡二叉樹至少有幾個結(jié)點？N0=0N1=1N2=2N3=4N4=7…Nh=Nh-1+Nh-2+16、平衡二叉樹的查找分析(2)含有n個結(jié)點的平衡二叉樹最大深度為多少？ 由（1）倒著推導(dǎo)。(3)平衡二叉樹查找的時間復(fù)雜度O（log2n），與樹高同一數(shù)量級。2023/2/3如：輸入關(guān)鍵字序列{16,3,7,11,9,26,18,14,15},給出構(gòu)造一棵AVL樹的步驟。2023/2/37.3哈希表的查找基本思想：記錄的存儲位置與關(guān)鍵字之間存在對應(yīng)關(guān)系，Loc(i)=H(keyi)

優(yōu)點：查找速度極快O(1),查找效率與元素個數(shù)n無關(guān)哈希函數(shù)關(guān)鍵字集合存儲地址集合hash若將學(xué)生信息按如下方式存入計算機，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。查找2001011810216的信息，可直接訪問V[16]！例1數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結(jié)構(gòu)圖?！?4…11…9…內(nèi)容地址…39…25242314119232539例2根據(jù)哈希函數(shù)H（k）＝k

查找key=9,則訪問H(9)=9號地址，若內(nèi)容為9則成功；若查不到，則返回一個特殊值，如空指針或空記錄。如何查找…14…11…9…內(nèi)容地址…39…25242314119232539哈希方法(雜湊法)選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值k計算地址，將k與地址單元中元素關(guān)鍵碼進行比較，確定查找是否成功。哈希函數(shù)(雜湊函數(shù))：哈希方法中使用的轉(zhuǎn)換函數(shù)有關(guān)術(shù)語沖突：不同的關(guān)鍵碼映射到同一個哈希地址哈希表(雜湊表)：按上述思想構(gòu)造的表有關(guān)術(shù)語…14…11…9…內(nèi)容地址…39…25242314119232539同義詞：具有相同函數(shù)值的兩個關(guān)鍵字key1key2，但H(key1)=H(key2)（14，23，39，9，25，11）哈希函數(shù)：H(k)=kmod72539239146個元素用7個地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4同義詞有沖突0123456沖突現(xiàn)象舉例沖突是不可能避免的如何減少沖突構(gòu)造好的哈希函數(shù)制定一個好的解決沖突方案哈希函數(shù)的構(gòu)造方法根據(jù)元素集合的特性構(gòu)造地址空間盡量小均勻直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機數(shù)法Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點：以關(guān)鍵碼key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突。缺點：要占用連續(xù)地址空間，空間效率低。直接定址法

例：

{100，300，500，700，800，900}，哈希函數(shù)Hash(key)=key/1000123456789900800700500300100直接定址法2023/2/3數(shù)字分析法方法：對關(guān)鍵字進行分析，取關(guān)鍵字的若干位或其組合作哈希地址適用于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且關(guān)鍵字事先知道的情況例：有80個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：位只取8位只取1位只取3、4位只取2、7、5位數(shù)字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址2023/2/3平方取中法方法：取關(guān)鍵字平方后中間幾位作哈希地址適用于不知道全部關(guān)鍵字情況折疊法方法：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加Hash(key)=keymodp(p是一個整數(shù))關(guān)鍵：如何選取合適的p？技巧：設(shè)表長為m，取p≤m且為質(zhì)數(shù)

除留余數(shù)法

（最常用重點掌握）①執(zhí)行速度（即計算哈希函數(shù)所需時間）；②關(guān)鍵字的長度；③哈希表的大小；④關(guān)鍵字的分布情況；⑤查找頻率。構(gòu)造哈希函數(shù)考慮的因素1.開放定址法處理沖突的方法2.鏈地址法基本思想：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。1.開放定址法（開地址法）線性探測法二次探測法偽隨機探測法Hi=(Hash(key)+di)modm(1≤i<m)

其中：m為哈希表長度

di

為增量序列1，2，…m-1，且di=i一旦沖突，就找下一個空地址存入線性探測法關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長為m=11；哈希函數(shù)為Hash(key)=keymod11

012345678910477△▲△△291116922283①

47、7、11、16、92沒有沖突②Hash(29)=7，有沖突，由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入③

3

連續(xù)移動了兩次線性探測法線性探測法的特點優(yōu)點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素。缺點：可能使第i個哈希地址的同義詞存入第i+1個地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，……，產(chǎn)生“聚集”現(xiàn)象，降低查找效率。解決方案：二次探測法二次探測法關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希函數(shù)為Hash(key)=keymod11

Hi=(Hash(key)±di)modm其中：m為哈希表長度，m要求是某個4k+3的質(zhì)數(shù)；

di為增量序列

12，-12，22，-22，…，q2

012345678910829716924732211△▲