版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第9章查找1.掌握順序查找、二分查找和分塊查找的方法。2.掌握二叉排序樹(shù)的相關(guān)運(yùn)算和查找過(guò)程。3.理解平衡二叉樹(shù)的建樹(shù)方法。4.掌握哈希表的建立方法和查找過(guò)程。5.掌握各種查找方法在等概率下的平均查找長(zhǎng)度的計(jì)算方法。學(xué)習(xí)要點(diǎn)基本概念
查找表:是由同一類(lèi)型的數(shù)據(jù)元素構(gòu)成的集合,由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系,因此查找表是一種應(yīng)用靈便的數(shù)據(jù)結(jié)構(gòu)。
有關(guān)操作
查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中;
在查找表中插入一個(gè)數(shù)據(jù)元素;
從查找表中刪去某個(gè)數(shù)據(jù)元素。查找表的分類(lèi)靜態(tài)查找表:僅作查詢和檢索操作的查找表。動(dòng)態(tài)查找表:在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素。
關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值,用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。若此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄,則稱(chēng)之謂“主關(guān)鍵字”。若此關(guān)鍵字能識(shí)別若干記錄,則稱(chēng)之謂“次關(guān)鍵字”?;靖拍畈檎腋鶕?jù)給定的某個(gè)值,在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。若查找表中存在這樣一個(gè)記錄,則稱(chēng)“查找成功”,查找結(jié)果:給出整個(gè)記錄的信息,或指示該記錄在查找表中的位置;否則稱(chēng)“查找不成功”,查找結(jié)果:給出“空記錄”或“空指針”?;靖拍顢?shù)據(jù)元素類(lèi)型定義為:typedefstruct{KeyTypekey;//關(guān)鍵字域…//其他域}ElemType;基本概念9.1.1順序表的查找應(yīng)用范圍:以順序表或線性鏈表表示的靜態(tài)查找表,表內(nèi)元素之間無(wú)序。順序查找基本思想:從表中最后一個(gè)記錄開(kāi)始,逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較,若某個(gè)記錄的關(guān)鍵字和給定值比較相等,則查找成功;若直至第一個(gè)記錄,其關(guān)鍵字和給定值比較都不等,則查找不成功。順序存儲(chǔ)結(jié)構(gòu)的表示:
typedef
struct{
ElemType*elem;
intlength;}SSTable;9.1靜態(tài)查找表int
Search_Seq(StableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素
ST.elem[0].key=key;//哨兵
for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;//查找不成功時(shí)i為0}//Search_Seq免去查找過(guò)程中每一步都要檢測(cè)整個(gè)表是否查找完畢順序查找算法int
Search_Seq(StableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素
for(i=0;i<ST.length;++i)
if(ST.elem[i].key==key)returni;return(0);//查找不成功時(shí)i為0}//Search_Seq順序查找算法8012n-3n-2n-1nST.elem
key例1:在下表中查找key=8的結(jié)點(diǎn)?!?00100713iiiiiii查找不成功,i=08012n-3n-2n-1nST.elem
key例2:在下表中查找key=8的結(jié)點(diǎn)?!?00100813iii查找成功,i=n-2
舉例說(shuō)明1n查找成功情況下:設(shè)每個(gè)結(jié)點(diǎn)的查找概率相等ASL=∑(n-i+1)=(n+1)/2i=1n
和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱(chēng)為查找成功時(shí)的平均查找長(zhǎng)度。性能分析折半查找查找方式:每次將待查記錄所在區(qū)間縮小一半。適用條件:采用順序存儲(chǔ)結(jié)構(gòu)的有序表。算法實(shí)現(xiàn):設(shè)表長(zhǎng)為n,low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給定值。
初始時(shí),令low=1,high=n,mid=(low+high)/2。
讓k與mid指向的記錄比較若k==ST.elem[mid].key,查找成功;
若k<ST.elem[mid].key,則high=mid-1;
若k>ST.elem[mid].key,則low=mid+1。重復(fù)上述操作,直至low>high時(shí),查找失敗。9.1.2有序表的查找
舉例說(shuō)明(1)low找key=215113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow找key=705113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhigh
舉例說(shuō)明(2)low5113219321437556664775880988109211midhighlow5113219321437556664775880988109211high
舉例說(shuō)明(2)intSearch_bin(SStableST,KeyTypekey){//在有序表ST中折半查找關(guān)鍵字等于key的數(shù)據(jù)元素low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(EQ(ST.elem[mid].key,key)returnmid;elseif(LT(key,ST.elem[mid].key))high=mid-1;elselow=mid+1;}return0;}//Search_Bin折半查找算法判定樹(shù):描述查找過(guò)程的二叉樹(shù)。有n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度為log2n+1。
折半查找法在查找過(guò)程中進(jìn)行的比較次數(shù)最多不超過(guò)log2n+1。其ASL=log2(n+1)-1。
折半查找的優(yōu)點(diǎn)是比較的次數(shù)少,查找速度快,但前提是該表首先要進(jìn)行排序,而排序是一種很費(fèi)時(shí)運(yùn)算,并且折半查找只適用于順序存儲(chǔ)的有序表,不適用于鏈表存儲(chǔ)的有序表。5619800521886413753792折半查找性能分析5113219321437556664775880988109211索引順序查找(分塊查找)
查找過(guò)程:將表分成幾塊,塊內(nèi)無(wú)序,塊間有序;先確定待查記錄所在塊,再在塊內(nèi)查找。適用條件:分塊有序表假設(shè)按元素關(guān)鍵字升序方式組織表中各塊,則要求第一塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第二塊中所有結(jié)點(diǎn)的關(guān)鍵字值;第二塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第三塊中所有結(jié)點(diǎn)的關(guān)鍵字值;如此類(lèi)推。然后選擇每塊中的最大(或最小)關(guān)鍵字值組成索引表。索引表中的結(jié)點(diǎn)個(gè)數(shù)等于線性表被分割的塊數(shù)。9.1.4索引順序表的查找1234567891011121314151617182212138920
334244382448
6058745786532248861713索引表查38最大關(guān)鍵字起始地址表及其索引表LLASLwbbs+=其中:Lb是查找索引表確定所在塊的平均查找長(zhǎng)度;
Lw是在塊中查找元素的平均查找長(zhǎng)度。若將表長(zhǎng)n為的表平均分成b塊,每塊含s個(gè)記錄,并設(shè)表中每個(gè)記錄的查找概率相等,則:用順序查找確定所在塊用折半查找確定所在塊ASLbs=1)(21ssn++ASLbs=2)1(log2ssn++分塊查找性能分析9.2動(dòng)態(tài)查找表什么是二叉排序樹(shù)?或者是一棵空樹(shù);或者是具有下列性質(zhì)的二叉樹(shù):1.若左子樹(shù)不空,則左子樹(shù)上所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值;2.若右子樹(shù)不空,則右子樹(shù)上所有結(jié)點(diǎn)值均大于根結(jié)點(diǎn)值;3.根結(jié)點(diǎn)的左、右子樹(shù)也分別為二叉排序樹(shù)。45125333710024619078若二叉排序樹(shù)為空,則查找不成功;否則1.若給定值等于根結(jié)點(diǎn)的關(guān)鍵字,則查找成功;2.若給定值小于根結(jié)點(diǎn)的關(guān)鍵字,則繼續(xù)在左子樹(shù)上進(jìn)行查找;3.若給定值大于根結(jié)點(diǎn)的關(guān)鍵字,則繼續(xù)在右子樹(shù)上進(jìn)行查找。具體實(shí)現(xiàn)如下:BiTree
SearchBST(BiTree
T,KeyTypekey){if((!T)||(EQ(key,T->data.key))return(T);elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}二叉排序樹(shù)查找算法例如:在下圖中分別查找關(guān)鍵字值等于37,61和95過(guò)程。45125333710024619078從上述查找過(guò)程可見(jiàn),在查找過(guò)程中,生成了一條查找路徑:1.從根結(jié)點(diǎn)出發(fā),沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn),表明查找成功。2.或者從根結(jié)點(diǎn)出發(fā),沿著左分支或右分支逐層向下直至指針指向空樹(shù)為止,表明查找不成功。二叉排序樹(shù)查找過(guò)程基本思想:在每一步插入過(guò)程中,二叉排序樹(shù)中原有的結(jié)點(diǎn)位置均不動(dòng),只是將待插入的結(jié)點(diǎn)作為一個(gè)葉結(jié)點(diǎn)插入到適當(dāng)?shù)奈恢茫沟脴?shù)中任何結(jié)點(diǎn)與其左、右子樹(shù)結(jié)點(diǎn)之間的關(guān)系仍然滿足二叉排序樹(shù)的性質(zhì),向二叉樹(shù)T插入一個(gè)新結(jié)點(diǎn)s的過(guò)程為:若T為空的二叉樹(shù),則將新結(jié)點(diǎn)作為根結(jié)點(diǎn)插入。若新結(jié)點(diǎn)s的值等于二叉排序樹(shù)的根結(jié)點(diǎn),說(shuō)明該結(jié)點(diǎn)已存在,不需要插入。若將新結(jié)點(diǎn)s的值小于二叉排序樹(shù)T的根結(jié)點(diǎn),則將s插入到T的左子樹(shù)中去。若新結(jié)點(diǎn)s的值大于二叉排序樹(shù)T的根結(jié)點(diǎn),則將s插入到T的右子樹(shù)中去。二叉排序樹(shù)的插入操作是一個(gè)遞歸過(guò)程。二叉排序樹(shù)插入算法思想
StatusSearchBST(BiTree
T,KeyType
key,BiTree
f,BiTree&p)//若查找成功,則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn),返回TRUE,否則p指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)并返回FALSE,f是指向T的雙親
{if(!T){p=f;returnFALSE;}elseif(EQ(key,T->data.key)){p=T;returnTRUE;}elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}具體實(shí)現(xiàn)(1)StatusInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;elseif(LT(e.key,p->data.key))p->lchild=s;elsep->rchild=s;returnTRUE;}elsereturnFALSE;}具體實(shí)現(xiàn)(2)2712從空樹(shù)出發(fā),經(jīng)過(guò)一系列的查找插入操作后,便可生成一棵二叉排序樹(shù)。例對(duì)于關(guān)鍵字序列{10,18,3,8,12,2,7},構(gòu)造一棵BST。101838注意:對(duì)于同樣的數(shù)據(jù),輸入順序不同,建立起來(lái)的二叉排序樹(shù)的形態(tài)也不同。這直接影響到二叉排序樹(shù)的查找性能。如果輸入序列選得不好,會(huì)建立起一棵單支樹(shù),使得二叉排序樹(shù)的高度達(dá)到最大,這樣必然會(huì)降低查找性能。建立二叉排序樹(shù)中序遍歷二叉排序樹(shù)便可得到一個(gè)關(guān)鍵字的有序序列,也就是說(shuō),一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列。對(duì)下圖所示的二叉排序進(jìn)行中序遍歷,結(jié)果為(2,3,7,8,10,12,18)。每次插入的新結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn),不必移動(dòng)其它結(jié)點(diǎn),僅需修改某個(gè)結(jié)點(diǎn)的指針。這相當(dāng)于在一個(gè)有序列上插入一個(gè)記錄而又不需要移動(dòng)其他記錄。二叉排序樹(shù)既擁有折半查找的特性,又采用鏈?zhǔn)酱鎯?chǔ)。7212101838
結(jié)論和插入相反,刪除在查找成功之后進(jìn)行,并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后,仍然保持二叉排序樹(shù)的特性。可分三種情況討論:被刪除的結(jié)點(diǎn)是葉子;被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù);被刪除的結(jié)點(diǎn)既有左子樹(shù),也有右子樹(shù)。二叉排序樹(shù)的刪除刪除葉子結(jié)點(diǎn),只需將其雙親結(jié)點(diǎn)指向它的指針置為空,再釋放它即可。如:刪除關(guān)鍵字值為7的結(jié)點(diǎn)。1018381227刪除葉子結(jié)點(diǎn)刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù),則使其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。如:(1)刪除關(guān)鍵字值為2的結(jié)點(diǎn),它只有右子樹(shù)。(2)刪除關(guān)鍵字值為18的結(jié)點(diǎn),它只有左子樹(shù)。1018581223刪除的結(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)RQD中序遍歷:PL—D—R—Q
刪除后:PL—R—QPLRQPLRDQ中序遍歷:Q—R—PL—D
刪除后:Q—R—PLPLRQPLRQD中序遍歷:D—PR—R—Q
刪除后:PR—R—QPRRQPRRDQ中序遍歷:Q—R—D—PR
刪除后:Q—R—PRPRRQPR
具體解釋刪除葉結(jié)點(diǎn)和刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)這兩種操作,可通過(guò)下面語(yǔ)句實(shí)現(xiàn)。if(!p->rchild){q=p;p=p->lchild;free(q);}elseif(!p->lchild){q=p;p=p->rchild;free(q);}1018581223p
具體實(shí)現(xiàn)方法一:首先將結(jié)點(diǎn)D的右子樹(shù)鏈接到其中序前驅(qū)結(jié)點(diǎn)(結(jié)點(diǎn)D的左子樹(shù)中“最右下”且右指針域?yàn)榭盏慕Y(jié)點(diǎn))的右指針域,然后把結(jié)點(diǎn)R(結(jié)點(diǎn)D的雙親結(jié)點(diǎn))指向結(jié)點(diǎn)D的指針鏈接到結(jié)點(diǎn)D的左子樹(shù)上即可。RDQRRDRCCLQLGLGpfRQRRDRCCLQLGLGf該二叉排序樹(shù)的中序遍歷結(jié)果為:CL→C→QL→Q→GL→G→D→DR→R→RR刪除的結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)方法二:把結(jié)點(diǎn)D的中序前驅(qū)結(jié)點(diǎn)G的值賦給結(jié)點(diǎn)D,因?yàn)樵撝行蚯膀?qū)結(jié)點(diǎn)G只有左子樹(shù)GL,然后將結(jié)點(diǎn)G的雙親結(jié)點(diǎn)的右指針鏈接到GL即可。RDQRRDRCCLQLGLGpfRGQRRDRCCLQLGLpf該二叉排序樹(shù)的中序遍歷結(jié)果為:CL→C→QL→Q→GL→G→D→DR→R→RR刪除的結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)刪除的結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù),可通過(guò)下面語(yǔ)句實(shí)現(xiàn)。q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;free(s);RDQRRDRCCLQLGLGpf
具體實(shí)現(xiàn)
BST上查找過(guò)程,是從根結(jié)點(diǎn)到所找到結(jié)點(diǎn)的一條路徑。與給定值比較次數(shù)等于該路徑長(zhǎng)度+1,最大次數(shù)不超過(guò)樹(shù)的深度。但含有n個(gè)結(jié)點(diǎn)的BST卻不唯一。因此,含有n個(gè)結(jié)點(diǎn)的BST的ASL和樹(shù)的形態(tài)有關(guān)。最差情況是退化為單支樹(shù),ASL=(n+1)/2(同順序查找)。最好情況與折半查找相同,與log2n成正比。12452453123793(45,24,53,12,37,93)2437455393(12,24,37,45,53,93)ASL(a)=(1+2+2+3+3+3)/6=14/6ASL(b)=(1+2+3+4+5+6)/6=21/6
查找分析平衡二叉樹(shù)是二叉排序樹(shù)的另一種形式,其特點(diǎn)為:樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)高度之差的絕對(duì)值不大于1。若平衡因子定義為結(jié)點(diǎn)左子樹(shù)的高度減去右子樹(shù)的高度,則平衡二叉樹(shù)所有結(jié)點(diǎn)的平衡因子只可能是-1、0、1的二叉排序樹(shù)。例如:20210平衡樹(shù)非平衡樹(shù)-2-20-100101平衡二叉樹(shù)
采取的方法是在向平衡二叉樹(shù)插入結(jié)點(diǎn)時(shí)進(jìn)行平衡化旋轉(zhuǎn)?;舅枷霝椋杭俣ㄏ蚱胶鈽?shù)插入一個(gè)結(jié)點(diǎn)后破壞了其平衡性,則首先要找出唯一一棵最小不平衡子樹(shù),然后再調(diào)整該子樹(shù)中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系,使之成為一棵新的平衡二叉樹(shù)。最小不平衡子樹(shù)被調(diào)整為平衡子樹(shù)后,整個(gè)二叉排序樹(shù)又成為一棵平衡樹(shù)。
最小不平衡子樹(shù)是指離插入結(jié)點(diǎn)最近,且平衡因子絕對(duì)值大于1的祖先結(jié)點(diǎn)作為根的子樹(shù)。027511018410-110127511018410-211160構(gòu)造平衡二叉樹(shù)的方法(1)單向右旋平衡處理(LL型):新插入結(jié)點(diǎn)在A的左子樹(shù)根結(jié)點(diǎn)的左子樹(shù)上。A的平衡因子由1增至2,導(dǎo)致失衡。調(diào)整規(guī)則:將結(jié)點(diǎn)A的左孩子B向上旋轉(zhuǎn)成為新二叉樹(shù)的根,將結(jié)點(diǎn)A及其右子樹(shù)向右下旋轉(zhuǎn)成為結(jié)點(diǎn)B的右子樹(shù),而結(jié)點(diǎn)B原來(lái)的右子樹(shù)BR則成為結(jié)點(diǎn)A的左子樹(shù)。(進(jìn)行一次順時(shí)針旋轉(zhuǎn))調(diào)整方法分四種情況h+1h-1ABARBRBLh-10+2+1hh-1ABARBRBL00具體實(shí)現(xiàn):lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;p(2)單向左旋平衡處理(RR型):新插入結(jié)點(diǎn)在A的右子樹(shù)根結(jié)點(diǎn)的右子樹(shù)上。A的平衡因子由-1增至-2,導(dǎo)致失衡。調(diào)整規(guī)則:將結(jié)點(diǎn)A的右孩子B向上旋轉(zhuǎn)成為新二叉樹(shù)的根,將結(jié)點(diǎn)A及其左子樹(shù)向左下旋轉(zhuǎn)成為結(jié)點(diǎn)B的左子樹(shù),而結(jié)點(diǎn)B原來(lái)的左子樹(shù)BL則成為結(jié)點(diǎn)A的右子樹(shù)。(進(jìn)行一次逆時(shí)針旋轉(zhuǎn))調(diào)整方法分四種情況-2hh-1h-1BABRBLAL-10-1h0BABRBLALh-10具體實(shí)現(xiàn):rc=p->rchild;p->rchild=rc->lchild;rc->rchild=p;p=rc;p(3)先左后右平衡處理(LR型):新插入結(jié)點(diǎn)在A的左子樹(shù)根結(jié)點(diǎn)的右子樹(shù)上。A的平衡因子由1增至2,導(dǎo)致失衡。調(diào)整規(guī)則:將A的左孩子的右子樹(shù)的根結(jié)點(diǎn)C旋轉(zhuǎn)到結(jié)點(diǎn)A的位置成為新二叉樹(shù)的根,將結(jié)點(diǎn)B及其左子樹(shù)向左下旋轉(zhuǎn)成為C的左子樹(shù),而C結(jié)點(diǎn)原來(lái)的左子樹(shù)CL則作為結(jié)點(diǎn)B的右子樹(shù);將結(jié)點(diǎn)A及其右子樹(shù)向右下旋轉(zhuǎn)成為結(jié)點(diǎn)C的右子樹(shù),C結(jié)點(diǎn)原來(lái)的右子樹(shù)CR作為結(jié)點(diǎn)A的左子樹(shù)。(需進(jìn)行兩次旋轉(zhuǎn),先逆時(shí)針后順時(shí)針)調(diào)整方法分四種情況+2-1+1h-1ABARCLBLh-10CCRh-20h-1+1+2h-1CBARCLBLh-10CRh-2A+2h-10CBARCLBL0CRA-1將A的左孩子的右子樹(shù)的根結(jié)點(diǎn)C旋轉(zhuǎn)到結(jié)點(diǎn)A的位置成為新二叉樹(shù)的根,將結(jié)點(diǎn)B及其左子樹(shù)向左下旋轉(zhuǎn)成為C的左子樹(shù),而C結(jié)點(diǎn)原來(lái)的左子樹(shù)CL則作為結(jié)點(diǎn)B的右子樹(shù)。(第一次逆時(shí)針旋轉(zhuǎn))將結(jié)點(diǎn)A及其右子樹(shù)向右下旋轉(zhuǎn)成為結(jié)點(diǎn)C的右子樹(shù),C結(jié)點(diǎn)原來(lái)的右子樹(shù)CR作為結(jié)點(diǎn)A的左子樹(shù)。(第二次順時(shí)針旋轉(zhuǎn))調(diào)整過(guò)程調(diào)整方法分四種情況(4)先右后左平衡處理(RL型):新插入結(jié)點(diǎn)在A的右子樹(shù)根結(jié)點(diǎn)的左子樹(shù)上。A的平衡因子由-1增至-2,導(dǎo)致失衡。調(diào)整規(guī)則:它與LR旋轉(zhuǎn)情況正好對(duì)稱(chēng)的。調(diào)整實(shí)例假設(shè)一組數(shù)據(jù)對(duì)象為(40,28,16,56,50,32,30,63),按次序插入每個(gè)對(duì)象生成一棵平衡二叉樹(shù),根據(jù)插入過(guò)程指出每一步的調(diào)整類(lèi)型:“單向左旋轉(zhuǎn)”、“單向右旋轉(zhuǎn)”、“先左后右旋轉(zhuǎn)”、“先右后左旋轉(zhuǎn)”、“無(wú)”。解釋?zhuān)鹤笞訕?shù)的左子樹(shù)上插入→“單向右旋轉(zhuǎn)”右子樹(shù)的右子樹(shù)上插入→“單向左旋轉(zhuǎn)”左子樹(shù)的右子樹(shù)上插入→“先左后右旋轉(zhuǎn)”右子樹(shù)的左子樹(shù)上插入→“先右后左旋轉(zhuǎn)”9.3哈希表9.3.1什么是哈希表?哈希查找:又叫散列查找,利用哈希函數(shù)進(jìn)行查找的過(guò)程。其基本思想是在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系。這樣,不經(jīng)過(guò)比較,一次存取就能得到所查元素的查找方法。哈希函數(shù):在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系。按這種思想建立的表稱(chēng)為哈希表。例假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46,給定散列函數(shù)H(k)=k%13,存貯區(qū)的內(nèi)存地址從0到15,則可以得到每個(gè)關(guān)鍵字的散列地址為:
H(18)=18%13=5,H(75)=75%13=10,H(60)=60%13=8H(43)=43%13=4,H(54)=54%13=2,H(90)=90%13=12H(46)=46%13=7于是,根據(jù)散列地址,可以將上述7個(gè)關(guān)鍵字序列存貯到一個(gè)一維數(shù)組HT(散列表)中,具體表示為:90756046184354151413121110987654321
0HT其中HT就是散列存貯的表,稱(chēng)為散列表。從散列表中查找一個(gè)元素相當(dāng)方便,例如,查找75,只需計(jì)算出H(75)=75%13=10,則可以在HT[10]中找到75。舉例說(shuō)明上面討論的散列表是一種理想的情形,即每一個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)唯一的地址。但是有可能出現(xiàn)這樣的情形,兩個(gè)不同的關(guān)鍵字有可能對(duì)應(yīng)同一個(gè)內(nèi)存地址。這樣,將導(dǎo)致后放的關(guān)鍵字無(wú)法存貯,我們把這種現(xiàn)象叫做沖突(collision)。即key1≠key2,而f(key1)=f(key2)。在散列存貯中,沖突是很難避免的,除非構(gòu)造出的散列函數(shù)為線性函數(shù)。散列函數(shù)選得比較差,則發(fā)生沖突的可能性越大。我們把相互發(fā)生沖突的關(guān)鍵字互稱(chēng)為“同義詞”。
沖突問(wèn)題1.直接定址法
可表示為H(key)=a*key+b,其中a、b均為常數(shù)。這種方法計(jì)算特別簡(jiǎn)單,并且不會(huì)發(fā)生沖突,但當(dāng)關(guān)鍵字分布不連續(xù)時(shí),會(huì)出現(xiàn)很多空閑單元,將造成大量存貯單元的浪費(fèi)。實(shí)際中使用此方法較少。例關(guān)鍵字集合為{100,300,500,700,800,900},選取哈希函數(shù)為H(key)=key/100,則在哈希表中存放如下:
9.3.2哈希函數(shù)的構(gòu)造方法01001230034500567007800890092.數(shù)字選擇法對(duì)關(guān)鍵字序列進(jìn)行分析,取那些位上數(shù)字變化多的、頻率大的作為散列函數(shù)地址。例如,對(duì)如下的關(guān)鍵字序列:
43010
4681015355
43010
1701128352
43010
3720818350
430102690605351
......通過(guò)對(duì)上述關(guān)鍵字序列分析,發(fā)現(xiàn)前5位相同,第6、8、10位上的數(shù)字變化多些,若規(guī)定地址取3位,則散列函數(shù)可取它的第6、8、10位。于是有:
H(430104681015355)=480H(430101701128352)=101H(430103620805351)=328H(430102690605351)=2969.3.2哈希函數(shù)的構(gòu)造方法3.平方取中法取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。在選定散列函數(shù)時(shí)不一定知道關(guān)鍵字的全部信息,取其中哪幾位也不一定合適,而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān),因此,可以使用隨機(jī)分布的關(guān)鍵字得到函數(shù)地址。如圖,隨機(jī)給出一些關(guān)鍵字,并取平方后的第2到4位為函數(shù)地址。9.3.2哈希函數(shù)的構(gòu)造方法關(guān)鍵字0100
(關(guān)鍵字)20010000函數(shù)地址010110012001210000144000021044011602061137040043105413703104.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同),然后取這幾部分的疊加和(舍去進(jìn)位)作為散列函數(shù)地址,稱(chēng)為折疊法。例如:假設(shè)關(guān)鍵字為某人身份證號(hào)碼430104681015355,則可以用4位為一組進(jìn)行疊加,即有5355+8101+1046+430=14932,舍去高位,則有H(430104681015355)=4932為該身份證關(guān)鍵字的散列函數(shù)地址。9.3.2哈希函數(shù)的構(gòu)造方法5.除留余數(shù)法該方法是用關(guān)鍵字序列中的關(guān)鍵字k除以p(p是小于等于散列表長(zhǎng)度m)所得余數(shù)作為散列函數(shù)的地址,即有H(k)=k%p。
除留余數(shù)法計(jì)算簡(jiǎn)單,適用范圍廣,是一種最常使用的方法。這種方法的關(guān)鍵是選取較理想的p值,使得每一個(gè)關(guān)鍵字通過(guò)該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址的概率都相等,從而盡可能減少發(fā)生沖突的可能性。
一般情形下,設(shè)散列表中允許的地址數(shù)為m,取一個(gè)不大于m,但最接近于或等于m的質(zhì)數(shù)p。9.3.2哈希函數(shù)的構(gòu)造方法由于散列存貯中選取的散列函數(shù)不是線性函數(shù),故不可避免地會(huì)產(chǎn)生沖突,下面給出常見(jiàn)的解決沖突方法。1.開(kāi)放定址法開(kāi)放定址法就是從發(fā)生沖突的那個(gè)單元開(kāi)始,按照一定的次序,從散列表中找出一個(gè)空閑的存儲(chǔ)單元,把發(fā)生沖突的待插入關(guān)鍵字存儲(chǔ)到該單元中,從而解決沖突的發(fā)生。9.3.3解決沖突的方法假設(shè)散列表的地址為0∽m-1,則散列表的長(zhǎng)度為m。若一個(gè)關(guān)鍵字在地址d處發(fā)生沖突,則依次探查d+1,d+2,…,m-1(當(dāng)達(dá)到表尾m-1時(shí),又從0,1,2,….開(kāi)始探查)等地址,直到找到一個(gè)空閑位置來(lái)裝沖突處的關(guān)鍵字,將這一種方法稱(chēng)為線性探查法。探查下一位置的公式為di=(di-1+1)%m(1≤i≤m-1),最后將沖突位置的關(guān)鍵字存入di地址中。線性探查法例給定序列為19,14,23,1,68,20,84,27,55,11,10,79,散到函數(shù)H(k)=k%13,散列表空間地址為0∽12,用線性探查法建立散列存貯結(jié)構(gòu)。得到的散列表如下圖所示。
H(19)=19%13=6;H(14)=14%13=1;H(23)=23%13=10;H(1)=1%13=1;H(68)=68%13=3;H(20)=20%13=7;H(84)=84%13=6;H(27)=27%13=1;H(55)=55%13=3;H(11)=11%13=11;H(10)=10%13=10;H(79)=79%13=1;線性探查法012345678910111219142316820842755111079方法:構(gòu)造若干個(gè)哈希函數(shù),當(dāng)發(fā)生沖突時(shí),計(jì)算下一個(gè)哈希地址,直到?jīng)_突不再發(fā)生。即:Hi=Rhi(key)i=1,2,……,k其中:Rhi——不同的哈希函數(shù)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- DB37T 4791-2024煤礦井下超大斷面硐室施工技術(shù)規(guī)范
- 江西省豐城市第九中學(xué)2025屆高三(復(fù)讀班)上學(xué)期第三次段考政治試卷(含答案)
- 讀書(shū)社團(tuán)活動(dòng)策劃(9篇)
- 歌頌教師主題演講稿三分鐘歌頌教師的主題集合4篇
- 光船租賃合同(2篇)
- 《職場(chǎng)溝通》電子教案 項(xiàng)目五 職場(chǎng)溝通中的禮儀準(zhǔn)備
- 2025年紫外光固化油墨合作協(xié)議書(shū)
- 2025年付里葉紅外分光光度計(jì)項(xiàng)目合作計(jì)劃書(shū)
- 2025年低溫超導(dǎo)材料項(xiàng)目發(fā)展計(jì)劃
- 賣(mài)車(chē)場(chǎng)地租賃協(xié)議
- 危險(xiǎn)源辨識(shí)及分級(jí)管控管理制度
- GB/T 19752-2024混合動(dòng)力電動(dòng)汽車(chē)動(dòng)力性能試驗(yàn)方法
- 和員工簽股權(quán)合同范本
- 07FD02 防空地下室電氣設(shè)備安裝
- 《工程倫理》題集
- 江蘇2024年江蘇省新聞出版學(xué)校招聘人員筆試歷年典型考題及考點(diǎn)附答案解析
- 四川省成都市2023-2024學(xué)年高二歷史上學(xué)期期末聯(lián)考試題
- 河北省2024屆高三大數(shù)據(jù)應(yīng)用調(diào)研聯(lián)合測(cè)評(píng)(Ⅵ)英語(yǔ)試題含答案
- 成人手術(shù)后疼痛評(píng)估與護(hù)理-中華護(hù)理學(xué)會(huì)團(tuán)體標(biāo)準(zhǔn)(2023)課件
- 《金屬基增容導(dǎo)線技術(shù)條件+第2部分:鋁包殷鋼芯耐熱鋁合金絞線》
- 園藝植物栽培學(xué)智慧樹(shù)知到期末考試答案章節(jié)答案2024年浙江農(nóng)林大學(xué)
評(píng)論
0/150
提交評(píng)論