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

數(shù)據(jù)結(jié)構(gòu)第9章查找基本概念——若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；——否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找查找成功查找不成功靜態(tài)查找動態(tài)查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字——由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合?！樵?Searching)特定元素是否在表中。——只查找，不改變集合內(nèi)的數(shù)據(jù)元素?！炔檎?，又改變（增減）集合內(nèi)的數(shù)據(jù)元素?！涗浿心硞€數(shù)據(jù)項的值，可用來識別一個記錄

(預(yù)先確定的記錄的某種標(biāo)志)——可以唯一標(biāo)識一個記錄的關(guān)鍵字例如“學(xué)號”例如“女”是一種數(shù)據(jù)結(jié)構(gòu)——識別若干記錄的關(guān)鍵字基本概念（2）對查找表常用的操作有哪些？查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。

（3）

有哪些查找方法？討論：（1）查找的過程是怎樣的？

給定一個值K，在含有n個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。例如查字典“特定的”=關(guān)鍵字

查找的基本方法可以分為兩大類，即比較式查找法和計算式查找法。其中比較式查找法又可以分為靜態(tài)查找表和動態(tài)查找表，而計算式查找法也稱為HASH（哈希）查找法。靜態(tài)查找表：只作前兩種操作。動態(tài)查找表：查找過程中同時插入不存在或刪除已存在的某個元素?；靖拍睿?）如何評估查找方法的優(yōu)劣？明確：查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字項進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度（ASL：averagesearchlength）。其中：n是文件記錄個數(shù)；Pi是查找第i個記錄的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i個記錄時所經(jīng)歷的比較次數(shù)。統(tǒng)計意義上的數(shù)學(xué)期望值物理意義：假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，ASL值越小，時間效率越高。主要內(nèi)容9.1靜態(tài)查找表9.2動態(tài)查找表9.3哈希表9.1靜態(tài)查找表靜態(tài)查找表的抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型靜態(tài)查找表的定義:ADTStaticSearchTable{D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識數(shù)據(jù)元素。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合。數(shù)據(jù)對象D:Create(&ST,n); //構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。

Destroy(&ST); //銷毀表ST。

Search(ST,key);//查找ST中其關(guān)鍵字等于key的數(shù)據(jù)元素。

Traverse(ST,Visit());//按某種次序?qū)T的每個元素調(diào)用函數(shù) Visit()一次且僅一次。}ADTStaticSearchTable基本操作P：針對靜態(tài)查找表的查找算法主要有：

一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┤?、靜態(tài)樹表的查找四、分塊查找（索引順序查找）9.1靜態(tài)查找表順序表的機(jī)內(nèi)存儲結(jié)構(gòu)：typedefstruct{ElemType*elem;//表基址，0號單元留空。表容量為全部元素

intlength;//表長，即表中數(shù)據(jù)元素個數(shù)}SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。對順序結(jié)構(gòu)如何線性查找？對單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易編寫；只要知道頭指針head就可以“順藤摸瓜”；對非線性樹結(jié)構(gòu)如何順序查找?可借助各種遍歷操作！9.1靜態(tài)查找表順序查找以順序表表示靜態(tài)查找表，則Search函數(shù)可用順序查找來實現(xiàn)。其順序存儲結(jié)構(gòu)如下：i01234567891011

513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個元素：1查找第n-1個元素：2……….查找第1個元素：n查找第i個元素：n+1-i查找失?。簄+1查找過程：從表的一端開始逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較。例如：9.1靜態(tài)查找表順序查找9.1靜態(tài)查找表順序查找算法的實現(xiàn)：技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。例：若將待查找的特定值key存入順序表的首部（如0號單元），則順序查找的實現(xiàn)方案為：從后向前逐個比較！intSearch_Seq(SSTableST,KeyTypekey){//在順序表ST中，查找關(guān)鍵字與key相同的元素；若成功，返回其位置信息，否則返回0ST.elem[0].key=key;//設(shè)立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當(dāng)n>1000時，查找時間將減少一半。

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

//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)returni;//若到達(dá)0號單元才結(jié)束循環(huán)，說明不成功，返回0值(i=0)。成功時則返回找到的那個元素的位置i。}//Search_Seq時間復(fù)雜度為O(ST.length)9.1靜態(tài)查找表順序查找順序查找性能分析查找算法的平均查找長度(AverageSearchLength)：

為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值。其中:n為表長

Pi

為查找表中第i個記錄的概率

Ci為找到該記錄時，曾和給定值比較過的 關(guān)鍵字的個數(shù)9.1靜態(tài)查找表順序查找順序表查找的平均查找長度為：對順序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn在等概率查找的情況下，9.1靜態(tài)查找表順序查找在不等概率查找的情況下，ASLss在

Pn≥Pn-1≥···≥P2≥P1時取極小值。表中記錄按查找概率由小到達(dá)重新排列,以提高查找效率。

若查找概率無法事先測定，則查找過程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。9.1靜態(tài)查找表折半查找順序表的查找算法簡單，但平均查找長度較大，不適用于表長較大的查找表。若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。有序表的查找折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半。適用條件：采用順序存儲結(jié)構(gòu)的有序表。1.設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定值。2.初始時，令

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

3.重復(fù)上述操作，直至low>high時，查找失敗。9.1靜態(tài)查找表折半查找折半查找算法實現(xiàn)9.1靜態(tài)查找表折半查找lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例如key=21的查找過程low

指示查找區(qū)間的下界;high

指示查找區(qū)間的上界;mid=(low+high)/2。例key=70的查找過程1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid9.1靜態(tài)查找表折半查找1234567891011513192137566475808892lowhigh當(dāng)下界low大于上界high時，則說明表中沒有關(guān)鍵字等于Key的元素，查找不成功。9.1靜態(tài)查找表折半查找intcount=0;//記錄查找次數(shù)intSearch_Bin(SSTableST,KeyTypekval){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素

intlow=1,mid,high=ST.length;//置區(qū)間初值

while(low<=high) {count++; mid=(low+high)/2;if(kval==ST.elem[mid].key)returnmid;//若找到，則函數(shù)值為該元素在表中的位置

elseif(kval<ST.elem[mid].key)high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找

elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

}return0;//找不到時，i為0}折半查找算法9.1靜態(tài)查找表折半查找折半查找的時間效率為O(log2n)先看一個有11個元素的表的例子：n=116391425781011i1234567891011Ci12233334444折半查找的性能分析判定樹：描述查找過程的二叉樹。有n個結(jié)點的判定樹的深度為log2n+1折半查找法在查找過程中進(jìn)行的比較次數(shù)最多不超過log2n+19.1靜態(tài)查找表折半查找9.1靜態(tài)查找表折半查找假設(shè)有序表的長度n=2h-1,（h=log2(n+1））,則描述折半查找的判定樹是深度為h的滿二叉樹。樹中層次為1的結(jié)點有1個，層次為2的結(jié)點有2個，層次為h的結(jié)點有2h-1個。假設(shè)表中每個記錄的查找概率相等則查找成功時折半查找的平均查找長度9.1靜態(tài)查找表靜態(tài)樹表的查找靜態(tài)最優(yōu)查找樹算法——時間代價高；實用算法：近似最優(yōu)查找樹（次優(yōu)查找樹）（參見教材P222—225）9.1靜態(tài)查找表索引順序表的查找順序表有序表表的特性無序有序存儲結(jié)構(gòu)順序或鏈?zhǔn)巾樞虿鍎h操作易于進(jìn)行需移動元素ASL的值大小順序表和有序表的比較9.1靜態(tài)查找表索引順序表的查找索引順序表在建立順序表的同時，建立一個索引項，包括兩項：關(guān)鍵字項和指針項。索引表按關(guān)鍵字有序，表則為分塊有序索引表……131211109876543210……7810405210索引順序表=索引+順序表順序表……46786152402522333114192108179.1靜態(tài)查找表索引順序表的查找索引順序查找 又稱分塊查找查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實現(xiàn)：用數(shù)組存放待查記錄,每個數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個索引表結(jié)點含有最大關(guān)鍵字域和指向本塊第一個結(jié)點的指針12345678910111213141516171822121389203342443824486058745786532248861713索引表查38例如9.1靜態(tài)查找表索引順序表的查找9.1靜態(tài)查找表索引順序表的查找分塊查找方法評價9.1靜態(tài)查找表查找方法比較ASL最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序查找折半查找

分塊查找9.2動態(tài)查找表動態(tài)查找表的特點:表結(jié)構(gòu)本身是在查找過程中動態(tài)生成。若表中存在其關(guān)鍵字等于給定值key的記錄,表明查找成功；否則插入關(guān)鍵字等于key的記錄。InitDSTable(&DT)//構(gòu)造一個空的動態(tài)查找表DT。DestroyDSTable(&DT)//銷毀動態(tài)查找表DT。SearchDSTable(DT,key);//查找DT中與關(guān)鍵字key等值的元素。InsertDSTable(&DT,e);//若DT中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則插入e到DT。DeleteDSTable(&T,key);//刪除DT中關(guān)鍵字等于key的數(shù)據(jù)元素。TraverseDSTable(DT,Visit());//按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多一次?；静僮鳎簘ADTDynamicSearchTableD是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識數(shù)據(jù)元素。ADTDynamicSearchTable{數(shù)據(jù)對象D：數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合。抽象數(shù)據(jù)類型動態(tài)查找表的定義：9.2動態(tài)查找表9.2動態(tài)查找表(n)(1)(n)(1)(nlogn)幾種查找表的特性查找插入刪除無序順序表無序線性鏈表有序順序表有序線性鏈表靜態(tài)查找樹表(n)(n)(logn)(n)(logn)(1)(1)(n)(1)(nlogn)從查找性能看，最好情況能達(dá)(logn)，此時要求表有序；從插入和刪除的性能看，最好情況能達(dá)(1)，此時要求存儲結(jié)構(gòu)是鏈表。結(jié)論：一、二叉排序樹二、平衡二叉樹三、B樹四、B+樹9.2動態(tài)查找表9.2動態(tài)查找表二叉排序樹又稱二叉查找樹（BinarySortTree）定義二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；它的左、右子樹也都分別是二叉排序樹。二叉排序樹9.2動態(tài)查找表二叉排序樹503080209010854035252388例如:是二叉排序樹。66不9.2動態(tài)查找表二叉排序樹通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)typedefstructBiTNode{//結(jié)點結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;9.2動態(tài)查找表二叉排序樹1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。否則若二叉排序樹為空，則查找不成功；二叉排序樹的查找算法：9.2動態(tài)查找表二叉排序樹50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095,9.2動態(tài)查找表二叉排序樹從上述查找過程可見，在查找過程中，生成了一條查找路徑:

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者

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

——查找成功

——查找不成功9.2動態(tài)查找表二叉排序樹算法描述如下：StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指針T所指二叉排序樹中遞歸地查找其

//關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，

//則返回指針p指向該數(shù)據(jù)元素的結(jié)點，并返回

//函數(shù)值為TRUE;}//SearchBST

…………否則表明查找不成功，返回

//指針p指向查找路徑上訪問的最后一個結(jié)點，

//并返回函數(shù)值為FALSE,指針f指向當(dāng)前訪問

//的結(jié)點的雙親，其初始調(diào)用值為NULL9.2動態(tài)查找表二叉排序樹if(!T)elseif(EQ(key,T->data.key))

elseif(LT(key,T->data.key))

else{p=f;returnFALSE;}//查找不成功{p=T;returnTRUE;}//查找成功SearchBST(T->lchild,key,T,p);//在左子樹中繼續(xù)查找SearchBST(T->rchild,key,T,p);//在右子樹中繼續(xù)查找9.2動態(tài)查找表二叉排序樹T設(shè)key=48fTfT22pTfTTTTfffp302010403525239.2動態(tài)查找表二叉排序樹根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進(jìn)行;若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。二叉排序樹的插入算法9.2動態(tài)查找表二叉排序樹intInsertBST(BiTree&T,ElemTypee){ if(!SearchBST(T,e.key,NULL,p)) {s=newBiTNode;//為新結(jié)點分配空間

s->data=e; s->lchild=s->rchild=NULL; if(!p)T=s;//插入s為新的根結(jié)點

elseif(e.key<p->data.key) p->lchild=s;//插入*s為*p的左孩子

elsep->rchild=s;//插入*s為*p的右孩子

return1;//插入成功

}elsereturn0;}//InsertBST50308020908540358832505050304035505080909.2動態(tài)查找表二叉排序樹一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列每次插入的新結(jié)點都是二叉排序樹上新的葉子結(jié)點插入時不必移動其它結(jié)點，僅需修改某個結(jié)點的指針結(jié)論9.2動態(tài)查找表二叉排序樹二叉排序樹的刪除算法

和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性?？煞秩N情況討論：被刪除的結(jié)點是葉子；被刪除的結(jié)點只有左子樹或者只有右子樹；被刪除的結(jié)點既有左子樹，也有右子樹。9.2動態(tài)查找表二叉排序樹50308020908540358832（1）被刪除的結(jié)點是葉子結(jié)點例如:被刪關(guān)鍵字=2088其雙親結(jié)點中相應(yīng)指針域的值改為“空”9.2動態(tài)查找表二叉排序樹50308020908540358832（2）被刪除的結(jié)點只有左子樹或者只有右子樹

其雙親結(jié)點的相應(yīng)指針域的值改為“指向被刪除結(jié)點的左子樹或右子樹”。被刪關(guān)鍵字=40809.2動態(tài)查找表二叉排序樹50308020908540358832（3）被刪除的結(jié)點既有左子樹，也有右子樹4040以其（中序遍歷）前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點被刪結(jié)點前驅(qū)結(jié)點被刪關(guān)鍵字=509.2動態(tài)查找表二叉排序樹StatusDeleteBST(BiTree&T,KeyTypekey){//若二叉排序樹T中存在其關(guān)鍵字等于key的

//數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點，并返回

//函數(shù)值TRUE，否則返回函數(shù)值FALSEif(!T)returnFALSE; //不存在關(guān)鍵字等于key的數(shù)據(jù)元素

else{}}//DeleteBST算法描述如下：……見下頁9.2動態(tài)查找表二叉排序樹if(EQ(key,T->data.key)) //找到關(guān)鍵字等于key的數(shù)據(jù)元素elseif(LT(key,T->data.key))

else{Delete(T);returnTRUE;} DeleteBST(T->lchild,key);//繼續(xù)在左子樹中進(jìn)行查找DeleteBST(T->rchild,key);//繼續(xù)在右子樹中進(jìn)行查找上頁else{}中內(nèi)容9.2動態(tài)查找表二叉排序樹voidDelete(BiTree&p){//從二叉排序樹中刪除結(jié)點p，

//并重接它的左子樹或右子樹

if(!p->rchild){}elseif(!p->lchild){}else{}}//Delete其中刪除操作過程如下所描述：………………p//右子樹為空樹則只需重接它的左子樹q=p;p=p->lchild;delete(q);pqq9.2動態(tài)查找表二叉排序樹9.2動態(tài)查找表二叉排序樹//左子樹為空樹只需重接它的右子樹q=p;p=p->rchild;delete(q);ppqq9.2動態(tài)查找表二叉排序樹q=p;s=p->lchild;while(!s->rchild){q=s;s=s->rchild;}//s指向被刪結(jié)點的前驅(qū)//左右子樹均不空p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;//重接*q的左子樹delete(s);9.2動態(tài)查找表二叉排序樹q=p;s=p->lchild;while(!s->rchild)

{q=s;s=s->rchild;}//s指向被刪結(jié)點的前驅(qū)//左右子樹均不空p->data=s->data;if(q!=p)q->rchild=s->lchild;//重接*q的右子樹

elseq->lchild=s->lchild;//重接*q的左子樹delete(s);PCpFPRfCLQSLQLSqsfCpFPRSCLQQLSLqfLpFPRPCLqsfpFPRLCLq9.2動態(tài)查找表二叉排序樹二叉排序樹查找性能的分析

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。9.2動態(tài)查找表二叉排序樹由關(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+2+3+2+3）/5=2.29.2動態(tài)查找表平衡二叉樹平衡二叉樹又稱AVL樹，是具有如下性質(zhì)的二叉樹：

為了方便起見，給每個結(jié)點附加一個數(shù)字，給出該結(jié)點左子樹與右子樹的高度差。這個數(shù)字稱為結(jié)點的平衡因子balance。這樣，可以得到AVL樹的其它性質(zhì)：即|左子樹深度-右子樹深度|≤1左、右子樹是平衡二叉樹；所有結(jié)點的左、右子樹深度之差的絕對值≤1任一結(jié)點的平衡因子只能取：-1、0或1；如果樹中任意一個結(jié)點的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對于一棵有n個結(jié)點的AVL樹，其高度保持在O(log2n)數(shù)量級，ASL也保持在O(log2n)量級。9.2動態(tài)查找表平衡二叉樹(a)平衡樹(b)不平衡樹例：判斷下列二叉樹是否AVL樹？00011-1-120001-19.2動態(tài)查找表平衡二叉樹如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)?，F(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：

LL平衡旋轉(zhuǎn)

RR平衡旋轉(zhuǎn)

LR平衡旋轉(zhuǎn)

RL平衡旋轉(zhuǎn)9.2動態(tài)查找表平衡二叉樹若在A的左子樹的左子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要進(jìn)行一次順時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC1）LL平衡旋轉(zhuǎn)：9.2動態(tài)查找表平衡二叉樹

在一般二叉排序樹的結(jié)點中增加一個存放平衡因子的域bf，就可以用來表示平衡二叉排序樹。在下面的討論中，我們約定：用來表示結(jié)點的字母，同時也用來表示指向該結(jié)點的指針。因此，LL型失衡的特點是：A->bf=2，B->bf=1。相應(yīng)調(diào)整操作可用如下語句完成：B=A->lchild；

A->lchild=B->rchild；

B->rchild=A；

A->bf=0；B->bf=0；9.2動態(tài)查找表平衡二叉樹

最后，將調(diào)整后二叉樹的根結(jié)點B“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用B代替A做FA的左子或右子；否則原來A就是根結(jié)點，此時應(yīng)令根指針t指向B：if(FA==NULL)t=B;elseif(A==FA->lchild)FA->lchild=B;elseFA->rchild=B；ABC9.2動態(tài)查找表平衡二叉樹若在A的右子樹的右子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABCRR型失衡的特點是：A->bf=-2，B->bf=-1。相應(yīng)調(diào)整操作可用如下語句完成：B=A->rchild；A->rchild=B->lchild；B->lchild=A；A->bf=0；B->bf=0；9.2動態(tài)查找表平衡二叉樹9.2動態(tài)查找表平衡二叉樹

最后，將調(diào)整后二叉樹的根結(jié)點B“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用B代替A做FA的左子或右子；否則，原來A就是根結(jié)點，此時應(yīng)令根指針t指向B：if(FA==NULL)t=B;elseif(A==FA->lchild)FA->lchild=B;elseFA->rchild=B；ABC9.2動態(tài)查找表平衡二叉樹若在A的左子樹的右子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要先進(jìn)行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：9.2動態(tài)查找表平衡二叉樹LR型失衡的特點是：A->bf=2，B->bf=-1。相應(yīng)調(diào)整操作可用如下語句完成：B=A->lchild；C=B->rchild；B->rchild=C->lchild；A->lchild=C->rchild；C->lchild=B；C->rchild=A；9.2動態(tài)查找表平衡二叉樹然后針對上述三種不同情況，修改A、B、C的平衡因子：if(S->key<C->key)/*在CL下插入S*/{A->bf=-1；B->bf=0；C->bf=0；}if(S->key>C->key)/*在CR下插入S*/{A->bf=0；B->bf=1；C->bf=0；}if(S->key==C->key)/*C本身就是插入的新結(jié)點S*/{A->bf=0；B->bf=0；}9.2動態(tài)查找表平衡二叉樹

最后，將調(diào)整后的二叉樹的根結(jié)點C“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用C代替A做FA的左子或右子；否則，原來A就是根結(jié)點，此時應(yīng)令根指針t指向C：if(FA==NULL)t=C;elseif(A==FA->lchild)FA->lchild=C;elseFA->rchild=C；ABC9.2動態(tài)查找表平衡二叉樹若在A的右子樹的左子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC9.2動態(tài)查找表平衡二叉樹RL型失衡的特點是：A->bf=-2，B->bf=1。相應(yīng)調(diào)整操作可用如下語句完成：B=A->rchild；C=B->lchild；B->lchild=C->rchild；A->rchild=C->lchild；C->lchild=A；C->rchild=B；然后針對上述三種不同情況，修改A、B、C的平衡因子：if(S->key<C->key)/*在CL下插入S*/{A->bf=0；B->bf=-1；C->bf=0；}if(S->key>C->key)/*在CR下插入S*/{A->bf=1；B->bf=0；C->bf=0；}if(S->key==C->key)/*C本身就是插入的新結(jié)點S*/{A->bf=0；B->bf=0；}9.2動態(tài)查找表平衡二叉樹

最后，將調(diào)整后的二叉樹的根結(jié)點C“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用C代替A做FA的左子或右子；否則，原來A就是根結(jié)點，此時應(yīng)令根指針t指向C：

if(FA==NULL)t=C;elseif(A==FA->lchild)FA->lchild=C;elseFA->rchild=C；ABC9.2動態(tài)查找表平衡二叉樹

綜上所述，在一個平衡二叉排序樹上插入一個新結(jié)點S時，主要包括以下三步：（1）查找應(yīng)插位置，同時記錄離插入位置最近的可能失衡結(jié)點A（A的平衡因子不等于0）。（2）插入新結(jié)點S，并修改從A到S路徑上各結(jié)點的平衡因子。（3）根據(jù)A、B的平衡因子，判斷是否失衡以及失衡類型，并做相應(yīng)處理。9.2動態(tài)查找表平衡二叉樹9.2動態(tài)查找表平衡二叉樹013037024例：請將下面序列構(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

9.2動態(tài)查找表B樹B樹的定義

空樹或m叉樹每個結(jié)點至多有m棵子樹，如根結(jié)點不是葉，至少有兩棵子樹，除根之外，所有非終端結(jié)點至少有m/2棵子樹。所有的非終端結(jié)點含有信息

(n,A0,K1,A1,K2,······,Kn,An)5)所有葉結(jié)點都在同一層次，叫做失敗結(jié)點。9.2動態(tài)查找表B樹所有的非終端結(jié)點含有信息n:有n+1棵子樹，K1≤K2≤······≤Kn關(guān)鍵字有序序列,指針Ai指向子樹中結(jié)點的關(guān)鍵字小于Ki,

nA0K1A1K2·····KnAn9.2動態(tài)查找表B樹

1·35·1·18·2·43·78·1·11·1·27·1·39·1·99·3·47·53·FFFFFFFFFFF

在B樹中的“失敗”結(jié)點(F)是當(dāng)搜索值x不在樹中時才能到達(dá)的結(jié)點。

根據(jù)m階B_樹的定義，結(jié)點的類型定義如下：#defineM5/*根據(jù)實際需要定義B_樹的階數(shù)*/typedefstructBTNode{intkeynum;/*結(jié)點中關(guān)鍵字的個數(shù)*/structBTNode*parent;/*指向父結(jié)點的指針*/KeyTypekey[M+1];/*關(guān)鍵字向量,key[0]未用*/structBTNode*ptr[M+1];/*子樹指針向量*/RecType*recptr[M+1];/*記錄指針向量,recptr[0]未用*/}BTNode;9.2動態(tài)查找表B樹9.2動態(tài)查找表B樹1·35·1·18·2·43·78·1·11·1·27·1·39·1·99·3·47·53·FFFFFFFFFFFB樹的搜索過程檢索結(jié)點53B樹的搜索過程是一個在結(jié)點內(nèi)搜索和循某一條路徑向下一層搜索交替進(jìn)行的過程。9.2動態(tài)查找表B樹30一棵B樹是平衡的m

路搜索樹，但一棵平衡的m

路搜索樹不一定是B樹。352040253010154550root4550354020root101525非B樹 B樹9.2動態(tài)查找表B樹設(shè)在m階B樹中每層結(jié)點個數(shù)達(dá)到最少,則B樹的高度可能達(dá)到最大。設(shè)樹中關(guān)鍵字個數(shù)為N，從B樹的定義知：

1層1個結(jié)點

2層至少2個結(jié)點

3層至少2m/2

個結(jié)點

4層至少2m/2

2個結(jié)點如此類推，

h

層至少有2m/2

h-2個結(jié)點。所有這些結(jié)點都不是失敗結(jié)點。h+1層至少有2m/2

h-1

個結(jié)點。這一層是葉子結(jié)點，不是失敗結(jié)點。高度h與關(guān)鍵字個數(shù)N之間的關(guān)系9.2動態(tài)查找表B樹若樹中關(guān)鍵碼有N個,則失敗結(jié)點數(shù)為N+1。這是因為失敗數(shù)據(jù)一般與已有關(guān)鍵碼交錯排列。因此，有

N

+1=失敗結(jié)點數(shù)=位于第h層的結(jié)點數(shù)

2m/2

h-1

N2m/2

h-1-1

h-1log

m/2

((N

+1)/2)

hlog

m/2

((N

+1)/2)+1所有的非失敗結(jié)點所在層次為1h。示例：若B樹的階數(shù)m=199,關(guān)鍵碼總數(shù)N=1999999，則B樹的高度h不超過

log1001000000+1=4查找的比較次數(shù)與樹的深度有關(guān)9.2動態(tài)查找表B樹m值的選擇如果提高B樹的階數(shù)

m,可以減少樹的高度,從而減少讀入結(jié)點的次數(shù),因而可減少讀磁盤的次數(shù)。事實上，m

受到內(nèi)存可使用空間的限制。當(dāng)m很大超出內(nèi)存工作區(qū)容量時,結(jié)點不能一次讀入到內(nèi)存,增加了讀盤次數(shù),也增加了結(jié)點內(nèi)搜索的難度。B樹的插入B樹是從空樹起,逐個插入關(guān)鍵碼而生成的。在B樹，每個非失敗結(jié)點的關(guān)鍵碼個數(shù)都在

[m/2-1,m-1]

之間。插入在某個葉結(jié)點開始。如果在關(guān)鍵碼插入后結(jié)點中的關(guān)鍵碼個數(shù)超出了上界m-1，則結(jié)點需要“分裂”，否則可以直接插入。9.2動態(tài)查找表B樹實現(xiàn)結(jié)點“分裂”的原則是：設(shè)結(jié)點p中已經(jīng)有m-1個關(guān)鍵碼，當(dāng)再插入一個關(guān)鍵碼后結(jié)點中的狀態(tài)為(m,P0,K1,P1,K2,P2,……,Km,Pm)

其中Ki<Ki+1,1

i<m這時必須把結(jié)點p分裂成兩個結(jié)點p和q，它們包含的信息分別為：結(jié)點p：(m/2-1,P0,K1,P1,……,Km/2-1,Pm/2-1)

結(jié)點q：(m-m/2,Pm/2,Km/2+1,Pm/2+1,……,Km,Pm)位于中間的關(guān)鍵碼Km/2

與指向新結(jié)點q的指針形成一個二元組(Km/2,q)，插入到這兩個結(jié)點的雙親結(jié)點中去。見教材242頁例9.2動態(tài)查找表B樹fhmb(a)一棵2-3樹fhmbd(b)插入d后fhmpbd分裂(c)插入p后并進(jìn)行分裂hfmbdphlfmbdp(d)插入l后分裂ghlfmbdp(e)插入g后并進(jìn)行分裂lfhmbdpp分裂在3階B樹中進(jìn)行插入的過程lfhmbdpglbdpghfm(f)繼續(xù)進(jìn)行分裂9.2動態(tài)查找表B樹9.2動態(tài)查找表B樹B樹的刪除先找到這個關(guān)鍵碼所在的結(jié)點,從中刪去這個關(guān)鍵碼。若該結(jié)點是最下層非終端結(jié)點,且關(guān)鍵字?jǐn)?shù)目不小于m/2

，刪除完成若該結(jié)點不是最下層非終端結(jié)點,且被刪關(guān)鍵碼為Ki,1in,則在刪去該關(guān)鍵碼之后,應(yīng)以該結(jié)點Pi所指示子樹中的最小關(guān)鍵碼x來代替被刪關(guān)鍵碼Ki所在的位置,然后在x

所在的結(jié)點中刪除x。例：教材245頁圖9.17(a)刪除53簡單刪除58758010406560703050acbdefgh5558刪除557580m=3刪除5510406560703050acbdefgh9.2動態(tài)查找表B樹9.2動態(tài)查找表B樹刪除最下層非終端結(jié)點中的關(guān)鍵字的情形：⑴若結(jié)點N中的關(guān)鍵字個數(shù)>m/2-1：在結(jié)點中直接刪除關(guān)鍵字K，如后圖(b)∽(c)所示。⑵若結(jié)點N中的關(guān)鍵字個數(shù)=m/2-1：若結(jié)點N的左(右)兄弟結(jié)點中的關(guān)鍵字個數(shù)>m/2-1，則將結(jié)點N的左(或右)兄弟結(jié)點中的最大(或最小)關(guān)鍵字上移到其父結(jié)點中，而父結(jié)點中大于(或小于)且緊靠上移關(guān)鍵字的關(guān)鍵字下移到結(jié)點N，如后圖(a)。⑶若結(jié)點N和其兄弟結(jié)點中的關(guān)鍵字?jǐn)?shù)=m/2-1：刪除結(jié)點N中的關(guān)鍵字，再將結(jié)點N中的關(guān)鍵字、指針與其兄弟結(jié)點以及分割二者的父結(jié)點中的某個關(guān)鍵字Ki，合并為一個結(jié)點，若因此使父結(jié)點中的關(guān)鍵字個數(shù)<m/2-1，則依此類推，如后圖(d)。在B_樹中進(jìn)行刪除的過程刪除qlmbdqeghfplbdpeghfm刪除h(a)刪除elbdpegfmlbpegfm刪除dlpgmbf(b)(c)(d)9.2動態(tài)查找表B樹9.2動態(tài)查找表B+樹B-樹的變形根結(jié)點(非葉時)至少有兩個結(jié)點除根外，非葉結(jié)點至少有[m/2]棵子樹,最多有m棵子樹,非葉結(jié)點都是索引，含有子樹中的最大或最小關(guān)鍵字含有n個關(guān)鍵字的非葉結(jié)點有n棵子樹所有的葉子結(jié)點都在同一個層次上，葉子結(jié)點中包含全部關(guān)鍵字，以及指向這些關(guān)鍵字的指針?biāo)械姆墙K端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹（根結(jié)點）中的最大（或最?。╆P(guān)鍵字9.2動態(tài)查找表B+樹59971544597297101521374451598591976372根葉B+樹兩種查找：從根開始，從葉起始9.2動態(tài)查找表B+樹B樹(上圖)與B+樹（下圖）比較B樹與B+樹的隨機(jī)查找、插入、刪除的過程基本上與B樹類似。只是在查找時，若非終端結(jié)點的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)向下直到葉子結(jié)點。9.3哈希表哈希表的相關(guān)定義哈希查找:又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程?；舅枷耄涸谟涗浀拇鎯Φ刂泛退年P(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。哈希函數(shù):在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系。哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲地址空間的一種映象。 可寫成，addr(ai)=H(ki)

其中：ai是表中的一個元素

addr(ai)是ai的存儲地址

ki是ai的關(guān)鍵字9.3哈希表哈希表的相關(guān)定義哈希表根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表”。9.3哈希表哈希表的相關(guān)定義98例30個地區(qū)的各民族人口統(tǒng)計表編號地區(qū)總?cè)丝跐h族回族…1北京2上?！?..…...以編號作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)名作關(guān)鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=199.3哈希表哈希表的相關(guān)定義從例子可見：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可。沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象9.3哈希表哈希函數(shù)構(gòu)造的方法哈希函數(shù)構(gòu)造的方法直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機(jī)數(shù)法9.3哈希表哈希函數(shù)構(gòu)造的方法哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key或者H(key)=akey+b此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小其中a和b為常數(shù)直接定址法優(yōu)點：以關(guān)鍵碼key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突.缺點：要占用連續(xù)地址空間，空間效率低。

例：關(guān)鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則存儲結(jié)構(gòu)（哈希表）如下：01234567899008007005003001009.3哈希表哈希函數(shù)構(gòu)造的方法數(shù)字分析法

假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。此法適于能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。例有80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位與另兩位的疊加作哈希地址9.3哈希表哈希函數(shù)構(gòu)造的方法9.3哈希表哈希函數(shù)構(gòu)造的方法

以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。平方取中法9.3哈希表哈希函數(shù)構(gòu)造的方法將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。兩種疊加處理的方法：移位疊加:將分割后的幾部分低位對齊相加間界疊加:從一端沿分割界來回折送，然后對齊相加(此法適于關(guān)鍵字的數(shù)字位數(shù)特別多)

折疊法

例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加58640224046092H(key)=6092間界疊加除留余數(shù)法

設(shè)定哈希函數(shù)為:H(key)=keyMODp(p≤m)

其中，m為表長

p為不大于m的質(zhì)數(shù)或是不含20以下的質(zhì)因子9.3哈希表哈希函數(shù)構(gòu)造的方法9.3哈希表哈希函數(shù)構(gòu)造的方法

給定一組關(guān)鍵字為:12,39,18,24,33,21，若取p=9,則他們對應(yīng)的哈希函數(shù)值將為:3,3,0,6,6,3可見，若p中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能例如：為什么要對p加限制？9.3哈希表哈希函數(shù)構(gòu)造的方法隨機(jī)數(shù)法設(shè)定哈希函數(shù)為:H(key)=Random(key)其中，Random為偽隨機(jī)函數(shù)此法用于構(gòu)造關(guān)鍵字長度不等的哈希函數(shù)。選取哈希函數(shù)考慮的因素：計算哈希函數(shù)所需時間關(guān)鍵字長度哈希表長度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率

9.3哈希表處理沖突的方法處理沖突的方法“處理沖突”的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。開放定址法鏈地址法為產(chǎn)生沖突的地址H(key)求得一個地址序列：H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm其中：i=1,2,…,s H(key)為哈希函數(shù);m為哈希表長;di為增量序列,有下列三種取法:開放定址法9.3哈希表處理沖突的方法對增量di

的三種取法：1)線性探測再散列

di=ci最簡單的情況c=12)二次探測再散列

di=12,-12,22,-22,…,3)隨機(jī)探測再散列

di

是一組偽隨機(jī)數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測)9.3哈希表處理沖突的方法注意：增量di應(yīng)具有“完備性”即：產(chǎn)生的Hi

均不相同，且所產(chǎn)生的

s(m-1)個Hi值能覆蓋哈希表中所有地址。則要求：※平方探測時的表長m必為形如4j+3

的素數(shù)（如:7,11,19,23,…等）；※隨機(jī)探測時的m和di沒有公因子。9.3哈希表處理沖突的方法9.3哈希表處理沖突的方法例表長為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，H(key)=keyMOD11,現(xiàn)有第4個記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中(1)H(38)=38MOD11=5沖突

H1=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6沖突

H2=(5-12)MOD11=4不沖突(3)H(38)=38MOD11=5沖突設(shè)偽隨機(jī)數(shù)序列為9，則：

H1=(5+9)MOD11=3不沖突0123456789106017293838389.3哈希表處理沖突的方法例如:給定關(guān)鍵字集合構(gòu)造哈希表

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)