數(shù)據(jù)結(jié)構(gòu)課程講義9課件

數(shù)據(jù)結(jié)構(gòu)課程講義9ppt課件56、死去何所道，托體同山阿。57、春秋多佳日，登高賦新詩(shī)。58、種豆南山下，草盛豆苗稀。晨興理荒穢，帶月荷鋤歸。道狹草木長(zhǎng)，夕露沾我衣。衣沾不足惜，但使愿無(wú)違。59、相見(jiàn)無(wú)雜言，但道桑麻長(zhǎng)。60、迢迢新秋夕，亭亭月將圓。數(shù)據(jù)結(jié)構(gòu)課程講義9ppt課件數(shù)據(jù)結(jié)構(gòu)課程講義9ppt課件56、死去何所道，托體同山阿。57、春秋多佳日，登高賦新詩(shī)。58、種豆南山下，草盛豆苗稀。晨興理荒穢，帶月荷鋤歸。道狹草木長(zhǎng)，夕露沾我衣。衣沾不足惜，但使愿無(wú)違。59、相見(jiàn)無(wú)雜言，但道桑麻長(zhǎng)。60、迢迢新秋夕，亭亭月將圓。第九章查找這也是線(xiàn)性表的基本運(yùn)算之一。通常稱(chēng)為檢索、查詢(xún)等?！?線(xiàn)性查找1．1順序檢索基本思想：從線(xiàn)性表的一端開(kāi)始，逐個(gè)地將待查找元素的關(guān)鍵字與每個(gè)元素的關(guān)鍵字進(jìn)行比較，若找到，則返回1，否則返回0。該算法的時(shí)間復(fù)雜度為O(n).§1線(xiàn)性查找這是有序表的查找查找對(duì)已排序的查找結(jié)構(gòu)先確定中點(diǎn)，比較待查關(guān)鍵字與中點(diǎn)關(guān)鍵字的大小，反復(fù)直到成功。求n個(gè)數(shù)據(jù)折半查找的等概率成功查找的平均時(shí)間復(fù)雜性1234567891012233334441+2*2+4*3+3*4=29O(29/10)n個(gè)元素的折半查找2k-1≤n<2k+1-1查找成功平均概率時(shí)間復(fù)雜性介于log2(2k)-1和log2(2k+1)-1之間即k-1和k之間k=[log2(n+1)]

n個(gè)元素的折半查找成功平均概率時(shí)間復(fù)雜性log2(n+1)-1/2§1線(xiàn)性查找1．3分塊查找

亦稱(chēng)索引順序查找。也是基于提高查找速度的一種方法。檢索時(shí)要求元素構(gòu)成的塊間是排序的，而塊內(nèi)是未排好序的?；舅枷耄?/p>

將所有元素按關(guān)鍵字值劃分成若干塊，塊之間是排序的，而塊內(nèi)暫時(shí)是無(wú)序的。查找時(shí)候，首先折半查找確定元素所在的塊，然后再在塊內(nèi)進(jìn)行順序查找即可比較。3、索引順序查找

分塊有序后一子表中的關(guān)鍵字都大于前一子表中的關(guān)鍵字22488617132212138920334244382448605874498653最大關(guān)鍵字起始地址索引表索引順序表的查找查找關(guān)鍵字key=381.先檢索索引表確定子表位置2.再在子表中查找22488617132212138920334244382448605874498653索引表分塊查找成功的平均概率時(shí)間復(fù)雜性

索引表查找時(shí)間+子表查找時(shí)間設(shè)索引表長(zhǎng)為s，查找表長(zhǎng)為n,被平均分成s塊，每塊長(zhǎng)n/s,索引表平均查找時(shí)間(s+1)/2子表平均查找時(shí)間(n/s+1)/2?(s+1)+?(n/s+1)=?(s+n/s)+1當(dāng)s=√n時(shí)有最小值√n+1當(dāng)索引順序表已經(jīng)排序時(shí)，子塊查找可以用折半查找。平均查找時(shí)間：(s+1)/2+log2(1+n/s)-1/2=log2(1+n/s)+s/2索引也用折半查找，平均查找時(shí)間log2(s+1)-1/2+log2(1+n/s)-1/2=log2(s+1)(1+n/s)-1當(dāng)s=√n時(shí)2log2(√n+1)-1

§2樹(shù)形結(jié)構(gòu)的查找

2．1二叉排序樹(shù)及其查找過(guò)程

二叉樹(shù)BT是二叉排序樹(shù)，只要BT是滿(mǎn)足如下的條件：（1）若BT的左子樹(shù)非空，則其左子樹(shù)上所有結(jié)點(diǎn)的值均小于其根結(jié)點(diǎn)的值；（2）若其右子樹(shù)上所有結(jié)點(diǎn)的值均大于其根結(jié)點(diǎn)的值；（3）其左右子樹(shù)均為二叉排序樹(shù)。

對(duì)二叉排序樹(shù)的中序遍歷的結(jié)果就是一個(gè)升序序列。二叉排序樹(shù)又稱(chēng)為二叉查找樹(shù)。于是，只要將元素序列組織成二叉排序樹(shù)，在進(jìn)行查找時(shí)，讓待查找元素與根結(jié)點(diǎn)值進(jìn)行比較，若相等，則查找成功，否則，如果比根結(jié)點(diǎn)小，則只需要在左子樹(shù)中查找即可；如果比根結(jié)點(diǎn)大，則只需要在右子樹(shù)中查找即可。

§2樹(shù)形結(jié)構(gòu)的查找

其所涉及到的數(shù)據(jù)結(jié)構(gòu)如下：typedefstructbtnode{keytypekey;datatypeother;structbtnode*lchild,*rchild;}BSTNODE;BSTNODE*ptr;則*ptr就表示一棵二叉排序樹(shù)。

§2樹(shù)形結(jié)構(gòu)的查找

2．2二叉排序樹(shù)實(shí)現(xiàn)查找運(yùn)算

根據(jù)二叉排序樹(shù)的定義和性質(zhì)，不難得到其查找算法：intbstsearch(*Pt,x){p<=Pt;while(p!=NULL){if(p->key==x)return(1);if(p->key>x)p<=p->rchild;elsep<=p->lchild;}}

二叉查找樹(shù)的查找分析平均等概率查找時(shí)間(1+2+2+3+3+3)/6=14/6451257820604512820311(1+2+3+4+5+6)/6=7/2隨機(jī)二叉查找樹(shù)等概率平均查找時(shí)間

P(n)≤2(1+1/n)lnn

O(log2n)最壞O(n/2)

特點(diǎn)：用于頻繁進(jìn)行插入、刪除、查找的所謂動(dòng)態(tài)查找表。12225030011020099二叉排序樹(shù)LNPEMCY105230216查找步驟：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，查其左子樹(shù)。 若大于根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹(shù)。 在左右子樹(shù)上的操作類(lèi)似。12225030011020099105230216

§2樹(shù)形結(jié)構(gòu)的查找2.2二叉排序樹(shù)的插入運(yùn)算

由于插入運(yùn)算是二叉樹(shù)的基本運(yùn)算之一，所以利用二叉樹(shù)的插入運(yùn)算就可以實(shí)現(xiàn)在線(xiàn)性升序序列中插入結(jié)點(diǎn)，使之仍然是升序的功能。

其實(shí)現(xiàn)過(guò)程為：若二叉排序樹(shù)為空，則待插入結(jié)點(diǎn)*s就作為根結(jié)點(diǎn)插入到空二叉樹(shù)中；若二叉樹(shù)非空，則比較s->key:p->key,若<，則將*s插入到*p的左子樹(shù)中，若>，就插入到右子樹(shù)中，若=則不必插入。

該過(guò)程是遞歸的，很容易得到遞歸算法，也可以得到非遞歸算法。

§2樹(shù)形結(jié)構(gòu)的查找

voidinsertbst(*pt,*s){p<=pt;while(p!=NULL){f<=p;if(s->key<p->key)p<=p->lchild;elsep<=p->rchild;}if(pt==NULL)pt<=s;if(s->key<f->key)f->lchild<=s;elsef->rchild<=s;}

顯然，插入運(yùn)算是將待插入結(jié)點(diǎn)作為葉子插入的。所以算法的目的就是首先找到插入的位置。2、插入算法：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。e、g：將數(shù)的序列：122、99、250、110、300、280作為二叉排序樹(shù)的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹(shù)。1222、插入算法：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。e、g：將數(shù)的序列：122、99、250、110、300、280作為二叉排序樹(shù)的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹(shù)。122122992、插入算法：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。e、g：將數(shù)的序列：122、99、250、110、300、280作為二叉排序樹(shù)的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹(shù)。12212299122250992、插入算法：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。e、g：將數(shù)的序列：122、99、250、110、300、280作為二叉排序樹(shù)的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹(shù)。1221229912225099122250110992、插入算法：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。e、g：將數(shù)的序列：122、99、250、110、300、280作為二叉排序樹(shù)的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹(shù)。122122991222509912225011099122250300110992、插入算法：首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。若二叉樹(shù)為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。12225030011028099e、g：將數(shù)的序列：122、99、250、110、300、280作為二叉排序樹(shù)的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹(shù)。122122991222509912225011099122250300110992、插入算法：執(zhí)行實(shí)例：插入值為280的結(jié)點(diǎn)12225030011099Tf：null12225030011099fTKey=28012225030011099fTKey=280f12225030011099T:nullKey=280p12225030011099280

1560703020503、二叉排序樹(shù)的查找分析平均情況分析（在成功查找兩種的情況下）e.g:下述兩種情況下的成功的平均查找長(zhǎng)度ASL156070302050ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6

§2樹(shù)形結(jié)構(gòu)的查找

2.3二叉排序樹(shù)的刪除運(yùn)算

由于刪除結(jié)點(diǎn)運(yùn)算也是二叉樹(shù)的基本運(yùn)算之一，所以利用二叉樹(shù)的刪除運(yùn)算就可以實(shí)現(xiàn)在線(xiàn)性升序序列中刪除結(jié)點(diǎn)，使之仍然是升序的序列。其實(shí)現(xiàn)過(guò)程為：

若待刪除結(jié)點(diǎn)不在二叉排序樹(shù)，則不進(jìn)行任何操作；否則，假設(shè)找到的待刪除結(jié)點(diǎn)為*p，fath指向*p的雙親，那么，刪除*p的過(guò)程可以采用如下的方法：*p是否有左（右）子樹(shù)來(lái)分別進(jìn)行處理。

§2樹(shù)形結(jié)構(gòu)的查找

（1）若*p沒(méi)有左子樹(shù)，則只需要將*p的右子樹(shù)按照二叉排序樹(shù)的特性，連接到合適的位置即可。若*p沒(méi)有根結(jié)點(diǎn)，則只需要將*p的右子樹(shù)的根作為新的根結(jié)點(diǎn)；若*p不是根，則必須將它與其雙親*fath之間的連接斷開(kāi)，可以采用將將連接到*p的右子樹(shù)連接到*fath的左（右）鏈域上。當(dāng)然，若*p的右子樹(shù)也為空，則*p就是葉子結(jié)點(diǎn)，即p->rchild=NULL,則就相當(dāng)于將空樹(shù)連接到*fath的左（右）鏈域中。

§2樹(shù)形結(jié)構(gòu)的查找

（2）若*p有左子樹(shù)，則*p也可能有右子樹(shù)，需要將*p的左、右子樹(shù)按照二叉排序樹(shù)的特性，連接到合適的位置。此時(shí)可以采用兩種處理方法：一種是令p的左子樹(shù)直接連接到*p的雙親*fath的左（右）鏈域上，而*p的右子樹(shù)下接到*p的中序前趨結(jié)點(diǎn)*s的右鏈域上。（這里*s是*p的左子樹(shù)中最右下的結(jié)點(diǎn)，其右鏈域肯定為空）。

另外一種處理方法是：采用以*p的中序前趨*s頂替*p(相當(dāng)于將*s的內(nèi)容復(fù)制到*p中)，將*s的左子樹(shù)直接上接到*s的雙親*q左（右）鏈域上，再刪去*s。

葉子結(jié)點(diǎn)：直接刪除，更改它的父親結(jié)點(diǎn)的相應(yīng)指針域?yàn)榭?。如：刪除關(guān)鍵字為15、70的結(jié)點(diǎn)。15607030205060302050子樹(shù)的根結(jié)點(diǎn)：通常的做法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰(shuí)哪？左子樹(shù)中最大的結(jié)點(diǎn)或右子樹(shù)中最小的結(jié)點(diǎn)，參看圖。 要點(diǎn)：維持二叉排序樹(shù)的特性不變。在中序周游中緊靠著被刪結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”。12225030011020099105230216400450500子樹(shù)的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。如下圖所示，刪除結(jié)點(diǎn)的關(guān)鍵字為99、200的結(jié)點(diǎn)。被刪結(jié)點(diǎn)122250300200230216400450500110105刪除9912225030011020099105230216400450500被刪結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。如下圖所示，刪除結(jié)點(diǎn)的關(guān)鍵字為99、200的結(jié)點(diǎn)。122250300230216400450500刪除20011099105

12225030011020099105230216400450500被刪結(jié)點(diǎn)子樹(shù)的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。如下圖所示，刪除結(jié)點(diǎn)的關(guān)鍵字為99、200的結(jié)點(diǎn)。結(jié)論：·將被刪結(jié)點(diǎn)的另一兒子作為它的父親結(jié)點(diǎn)的兒子，究竟是作為左兒子還是右兒子依原替身結(jié)點(diǎn)和其父親結(jié)點(diǎn)的關(guān)系而定?！め尫疟粍h結(jié)點(diǎn)的空間。被刪結(jié)點(diǎn)

子樹(shù)的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左、右子樹(shù)皆不空，通常的做法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰(shuí)哪？左子樹(shù)中最大的結(jié)點(diǎn)(被刪結(jié)點(diǎn)的左子樹(shù)中的最右的結(jié)點(diǎn)，其右兒子指針域?yàn)榭?或右子樹(shù)中最小的結(jié)點(diǎn)(被刪結(jié)點(diǎn)的右子樹(shù)中的最左的結(jié)點(diǎn)，其左兒子指針域?yàn)榭?，參看下圖。 要點(diǎn)：維持二叉排序樹(shù)的特性不變。在中序周游中緊靠著被刪結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”。12225030011020099105230216400450500被刪結(jié)點(diǎn)替身替身11025030010520099230216400450500做法：將替身的關(guān)鍵字復(fù)制到被刪結(jié)點(diǎn)的關(guān)鍵字。將結(jié)點(diǎn)的左兒子作為的父結(jié)點(diǎn)的右兒子。11011099注意：結(jié)點(diǎn)右兒子必為空結(jié)點(diǎn)的父結(jié)點(diǎn)為11011099

12225030011020099105230216400450500被刪結(jié)點(diǎn)替身替身20025030011099105230216400450500做法：將替身的關(guān)鍵字復(fù)制到被刪結(jié)點(diǎn)的關(guān)鍵字。將結(jié)點(diǎn)的右兒子作為的父結(jié)點(diǎn)的左兒子。注意：結(jié)點(diǎn)左兒子必為空結(jié)點(diǎn)的父結(jié)點(diǎn)為200200200200250

12225030011020099105230216400450500被刪結(jié)點(diǎn)替身替身結(jié)論：·先將替身的關(guān)鍵字復(fù)制到被刪結(jié)點(diǎn)·將原替身的另一兒子作為它的父親結(jié)點(diǎn)的兒子，究竟是作為左兒子還是右兒子依原替身結(jié)點(diǎn)和其父親結(jié)點(diǎn)的關(guān)系而定。·釋放原替身結(jié)點(diǎn)的空間。FP被刪結(jié)點(diǎn)PRPLFP被刪結(jié)點(diǎn)CCLPRQQLSSLFSCCLPRQQLSLFCCLPRQQLSSLFPRPL、PR皆空，直接刪除。PL或PR為空，PL為空，刪除后的情況。1.刪除法2.刪除法

§2樹(shù)形結(jié)構(gòu)的查找

2．4平衡二叉樹(shù)簡(jiǎn)介由于二叉排序樹(shù)的結(jié)構(gòu)形態(tài)直接影響到查找的效率，所以必須構(gòu)造出平衡二叉樹(shù)。只要滿(mǎn)足平衡因子（即任何兩個(gè)子樹(shù)的高度之差）只能是-1，0，1的，則稱(chēng)為平衡二叉樹(shù)。通常情況下，平衡二叉樹(shù)的深度是很低的，所以其查找效率是最高的。DGEDABCFEGBA平衡二叉排序樹(shù)

起因：提高查找速度，避免最壞情況出現(xiàn)。如右圖情況的出現(xiàn)。 雖然完全樹(shù)的樹(shù)型最好，但構(gòu)造困難。常使用平衡樹(shù)。

CF

平衡因子（平衡度）：結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹(shù)的高度－右子樹(shù)的高度。平衡二叉樹(shù)：每個(gè)結(jié)點(diǎn)的平衡因子都為＋1、－1、0的二叉樹(shù)?；蛘哒f(shuō)每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度最多差一的二叉樹(shù)。注意：完全樹(shù)必為平衡樹(shù)，平衡樹(shù)不一定是完全樹(shù)。

平衡樹(shù)的

Adelson

算法的本質(zhì)特點(diǎn)：

以插入為例：在左圖所示的平衡樹(shù)中插入關(guān)鍵字為2的結(jié)點(diǎn)。插入之后仍應(yīng)保持平衡排序二叉樹(shù)的性質(zhì)不變。141253928635360501718730+1+1-1-1-100000000平衡樹(shù)141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡排序二叉樹(shù)的性質(zhì)不變？

平衡樹(shù)的

Adelson

算法的本質(zhì)特點(diǎn)：

以插入為例：在左圖所示的平衡樹(shù)中插入關(guān)鍵字為2的結(jié)點(diǎn)。插入之后仍應(yīng)保持平衡排序二叉樹(shù)的性質(zhì)不變。141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡排序二叉樹(shù)的性質(zhì)不變？解決方案：不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹(shù)的高度應(yīng)保持不變（左圖為3）。新結(jié)點(diǎn)插入后，找到第一個(gè)平衡度不為0的結(jié)點(diǎn)（如左圖結(jié)點(diǎn)

）即可。新插入的結(jié)點(diǎn)和第一個(gè)平衡度不為0的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為0在調(diào)整中，僅調(diào)整那些在平衡度變化的路徑上的結(jié)點(diǎn)（如：），其它結(jié)點(diǎn)不予調(diào)整。仍應(yīng)保持排序二叉樹(shù)的性質(zhì)不變。9359141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡排序二叉樹(shù)的性質(zhì)不變？23597122359712不可以以結(jié)點(diǎn)為子樹(shù)的根結(jié)點(diǎn)??！雖然，對(duì)本例來(lái)說(shuō)是可以行得通的。7141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)關(guān)鍵：將導(dǎo)致出現(xiàn)危機(jī)結(jié)點(diǎn)的情況全部分析清除，就可以使得平衡排序二叉樹(shù)的性質(zhì)保持不變！！14932528635360501718730+1+1-1-1-1000000012002.5非平衡二叉樹(shù)的平衡處理方法

若一棵二叉排序樹(shù)是平衡二叉樹(shù)，插入某個(gè)結(jié)點(diǎn)后，可能會(huì)變成非平衡二叉樹(shù)，這時(shí)，就可以對(duì)該二叉樹(shù)進(jìn)行平衡處理，使其變成一棵平衡二叉樹(shù)。處理的原則應(yīng)該是處理與插入點(diǎn)最近的、而平衡因子又比1大或比-1小的結(jié)點(diǎn)。我們分四種情況討論平衡處理。

1、LL型的處理(左左型)

如下圖所示，在A的左孩子B上插入一個(gè)左孩子結(jié)點(diǎn)C，使A的平衡因子由1變成了2，成為不平衡的二叉樹(shù)序樹(shù)。這時(shí)的平衡處理為：將A順時(shí)針旋轉(zhuǎn)，成為B的右子樹(shù)，而原來(lái)B的右子樹(shù)則變成A的左子樹(shù)，待插入結(jié)點(diǎn)C作為B的左子樹(shù)。(注：圖中結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)的平衡因子)，即左改組。

左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析：1、LL情況：（LL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)的左子樹(shù)上）AB+1h-10+2+1hh-1h-1LL改組BLBRARBA0h0h-1h-1BLBRAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1

中序序列：ABBLBRAR改組后：高度為h+1

中序序列：ABBLBRAR注意：改組后平衡度為0AB2、LR型的處理(左右型)如下圖所示，在A的左孩子B上插入一個(gè)右孩子C，使的A的平衡因子由1變成了2，成為不平衡的二叉排序樹(shù)。這是的平衡處理為：將C變到B與A之間，使之成為L(zhǎng)L型，然后按第(1)種情形LL型處理。此LR型又存在下列三種情形：

左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析：2、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)上）情形1：AB+1h-10+2-1h-1LR改組BLAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1

中序序列：注意：改組后平衡度為0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改組后：高度為h+1

中序序列：ABBLARCCLCRA

左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析：2、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)上）情形2：AB+1h-10+2-1h-1LR改組BLAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1

中序序列：注意：改組后平衡度為+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACRh-1CLh-2+10ABBLARCCRCL改組后：高度為h+1

中序序列：AABBLARCCRCL

左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析：2、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)上）情形3：AB+10+2-1LR改組危機(jī)結(jié)點(diǎn)改組前：高度為2中序序列：注意：改組后平衡度為0,0,0CBC0ABCA新插入結(jié)點(diǎn)ABC改組后：高度為2中序序列：CB0A00

四種情況的區(qū)分：

如果的平衡度為＋1則為L(zhǎng)L型改組；

否則為L(zhǎng)R型改組：若的平衡度為＋1、－1、0；則分別為L(zhǎng)RA、LRB、LRC型改組。BC3、RR型的處理(右右型)

如圖下所示，在A的右孩子B上插入一個(gè)右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹(shù)。這時(shí)的平衡處理為：將A逆時(shí)針旋轉(zhuǎn)，成為B的左子樹(shù)，而原來(lái)B的左子樹(shù)則變成A的右子樹(shù)，待插入結(jié)點(diǎn)C成為B的右子樹(shù)。4、RL型的處理(右左型)如下圖所示，在A的右孩子B上插入一個(gè)左孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹(shù)。這時(shí)的平衡處理為：將C變到A與B之間，使之成為RR型，然后按第3種情形RR型處理。

這里的右改組方法（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的右子樹(shù)上進(jìn)行的調(diào)整）的情況分析：1、RR情況：（RR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子樹(shù)的右子樹(shù)上） 處理圖形和LL鏡象相似2、RL情況：（RL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子樹(shù)的左子樹(shù)上）

1、處理圖形和LRA鏡象相似2、處理圖形和LRB鏡象相似

3、處理圖形和LRC鏡象相似。例2，給定一個(gè)關(guān)鍵字序列4,5,7,2,1,3,6，試生成一棵平衡二叉樹(shù)。

分析：平衡二叉樹(shù)實(shí)際上也是一棵二叉排序樹(shù)，故可以按建立二叉排序樹(shù)的思想建立，在建立的過(guò)程中，若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹(shù)。具體生成過(guò)程見(jiàn)下圖。2．6平衡二叉樹(shù)的查找及性能分析

平衡二叉樹(shù)本身就是一棵二叉排序樹(shù)，故它的查找與二叉排序樹(shù)完全相同。但它的查找性能優(yōu)于二叉排序樹(shù)，不像二叉排序樹(shù)一樣，會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度O(n)，它的時(shí)間復(fù)雜度與二叉排序樹(shù)的最好時(shí)間復(fù)雜相同，都為O(log2n)。例3對(duì)例2給定的關(guān)鍵字序列4,5,7,2,1,3,6，試用二叉排序樹(shù)和平衡二叉樹(shù)兩種方法查找，給出查找6的次數(shù)及成功的平均查找長(zhǎng)度。

分析：由于關(guān)鍵字序列的順序己經(jīng)確定，故得到的二叉排序樹(shù)和平衡二叉樹(shù)都是唯一的,得到的平衡二叉樹(shù)見(jiàn)上圖，得到的二叉排序樹(shù)見(jiàn)下圖。從上圖的二叉排序樹(shù)可知，查找6需4次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+4)/7=18/7≈2.57。從圖8-14的平衡二叉樹(shù)可知，查找6需2次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+3)=17/7≈2.43。從結(jié)果可知，平衡二叉樹(shù)的查找性能優(yōu)于二叉排序樹(shù)。

1、為什么采用B_樹(shù)和B+樹(shù)：大量數(shù)據(jù)存放在外存中，通常存放在硬盤(pán)中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次訪(fǎng)問(wèn)外存。但硬盤(pán)的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪(fǎng)外次數(shù)。在1970年由Rbayer和Emacreight提出用B_樹(shù)作為索引組織文件。提高訪(fǎng)問(wèn)速度、減少時(shí)間。 內(nèi)存E.G:用二叉樹(shù)組織文件，當(dāng)文件的記錄個(gè)數(shù)為100，000時(shí)，要找到給定關(guān)鍵字的記錄，需訪(fǎng)問(wèn)外存17次（log100,000）,太長(zhǎng)了！502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭，可常駐內(nèi)存文件訪(fǎng)問(wèn)示意圖：索引文件、數(shù)據(jù)文件存在盤(pán)上8.2.2B_樹(shù)和B+樹(shù)2、B_樹(shù)是一種多分支數(shù)，首先介紹m階B_樹(shù)：定義：m階B_樹(shù)滿(mǎn)足或空，或：

A、根結(jié)點(diǎn)要么是葉子，要么至少有兩個(gè)兒子B、除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)為:m/2<=s<=mC、有s個(gè)兒子的非葉結(jié)點(diǎn)具有n=s－1個(gè)關(guān)鍵字，即:s=n+1

這些結(jié)點(diǎn)的數(shù)據(jù)信息為： （n,A0,K1,R1,A1,K2,R2,A2,………Kn,Rn,An）

這里：n:關(guān)鍵字的個(gè)數(shù)

A0：<K1的結(jié)點(diǎn)的地址（指在該B_樹(shù)中）

K1：關(guān)鍵字

R1：關(guān)鍵字=K1的數(shù)據(jù)記錄在硬盤(pán)中的地址

A2：>K1且<K2的結(jié)點(diǎn)的地址（指在該B_樹(shù)中） 余類(lèi)推………

An：>Kn的結(jié)點(diǎn)的地址（指在該B_樹(shù)中） 注意：K1<=K2<=…...<=KnD、所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，不帶信息（可認(rèn)為外部結(jié)點(diǎn)或失敗結(jié)點(diǎn)）。例如：m=4階B_樹(shù)。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù) 至少為m/2=2個(gè)；結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為1。該B_樹(shù)的深度為4。 葉子結(jié)點(diǎn)都在第4層上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第1層第2層第3層(L層)第4層(L＋1層)3、B_樹(shù)的查找代價(jià)分析：查找過(guò)程，類(lèi)似于二叉樹(shù)的查找。如查找關(guān)鍵字為KEY的記錄。

從根開(kāi)始查找，如果Ki=KEY則查找成功，Ri為關(guān)鍵字為KEY的記錄的地址。 若Ki<KEY<Ki+1;查找Ai指向的結(jié)點(diǎn) 若KEY<K1;查找A0指向的結(jié)點(diǎn) 若KEY>Kn;查找An指向的結(jié)點(diǎn) 若找到葉子，則查找失敗。注意：每次查找將去掉（s-1）/s個(gè)分支，比二分查找快得多。

設(shè)關(guān)鍵字的總數(shù)為N，求m階B_樹(shù)的最大層次L。

層次 結(jié)點(diǎn)數(shù) 關(guān)鍵字的個(gè)數(shù)（最少） 1 1 1 2 2 2（m/2-1）

3 2（m/2）

2（m/2）（m/2-1）

4 2（m/2）2 2（m/2）2

（m/2-1）

L 2（m/2）L-2 2（m/2）L-2

（m/2-1）

L+1 2（m/2）L-1所以，N=1＋2（m/2-1）+……...+2（m/2）L-2

（m/2-1）=2m/2L-1-1故：L＝log（（N+1）/2）+13、B_樹(shù)的查找代價(jià)分析：

設(shè)關(guān)鍵字的總數(shù)為N，求m階B_樹(shù)的最大層次L。

故：L＝logm/2（（N+1）/2）+1設(shè)N＝1000，000且m＝256，則L<=3；最多3次訪(fǎng)問(wèn)外存可找到所有的記錄。4、B_樹(shù)的插入操作 1、確定插入位置，將結(jié)點(diǎn)插入到第L層（注意：第L+1層為葉子結(jié)點(diǎn)） 2、找到插入位置，將關(guān)鍵字和其它信息按序插入。

3、若被插入結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)>m-1,則該結(jié)點(diǎn)滿(mǎn)。必須分裂成兩個(gè)結(jié)點(diǎn)。否則不滿(mǎn)結(jié)束。 如結(jié)點(diǎn)原為： （m-1,A0,(K1,A1),(K2,A2),………(Km-1,Am-1)）

插入一個(gè)關(guān)鍵字之后變?yōu)椋?（m,A0,(K1,A1),(K2,A2),………(Km,Am)）

該結(jié)點(diǎn)將進(jìn)行分裂： …………... (Km/2,p‘

)…………...（m/2-1,A0,(K1,A1),………(Km/2,Am/2)）（m-m/2,Am/2,………(Km,Am)）

生成新結(jié)點(diǎn)p‘,將原結(jié)點(diǎn)的后半部分復(fù)制過(guò)去。若分裂一直進(jìn)行到根結(jié)點(diǎn)，樹(shù)可能長(zhǎng)高一層。P’P(Km/2,p‘

)數(shù)據(jù)項(xiàng)插入上層結(jié)點(diǎn)之中B-樹(shù)的插入方法

設(shè)要插入關(guān)鍵值為k的記錄，指向k所在記錄的指針為p。首先找到k應(yīng)插入的葉子結(jié)點(diǎn)，將k和p插入。然后，判斷被插入結(jié)點(diǎn)是否滿(mǎn)足m叉B-樹(shù)的定義，即插入后結(jié)點(diǎn)的分支數(shù)是否大于m（結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)是否大于m-1)，若不大于，則插入結(jié)束；否則，要把該結(jié)點(diǎn)分裂成兩個(gè)。方法是：申請(qǐng)一個(gè)新結(jié)點(diǎn)，由指針p’指向，將插入后的結(jié)點(diǎn)按照關(guān)鍵字的值大小分成左、中、右三部分，中間只含一項(xiàng)，左邊的留在原結(jié)點(diǎn)，右邊的移入新結(jié)點(diǎn)，中間的構(gòu)成新的插入項(xiàng)，插入到它們的雙親結(jié)點(diǎn)中，若雙親結(jié)點(diǎn)在插入后也要分裂，則在分裂后再往上插入。例如：3階B_樹(shù)的插入操作。m=3,m/2-1=1;至少1個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。3，127243024，3045，7053902610039506185345，70539026100395061851230324457053902610039506185127303245390261003950618512745707插入5、B_樹(shù)的刪除操作 1、查找具有給定鍵值的關(guān)鍵字Ki

2、如果在第L層，可直接刪除（注意：第L+1層為葉子結(jié)點(diǎn)），轉(zhuǎn)4。 3、否則，則首先生成“替身”。用的右子樹(shù)中的最左面的結(jié)點(diǎn)的關(guān)鍵字值，即處于第L層上的最小 關(guān)鍵字值取代。然后，刪除第L層上的該關(guān)鍵字。

4、從第L層開(kāi)始進(jìn)行刪除。 A、不動(dòng)：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)仍處于m/2-1和m-1之間。則結(jié)束。 B、借：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)原為m/2-1。而它們的左或右鄰居結(jié) 點(diǎn)的關(guān)鍵字的個(gè)數(shù)>m/2-1;則借一個(gè)關(guān)鍵字過(guò)來(lái)。處理結(jié)束。 C、并：若該結(jié)點(diǎn)的左或右鄰居結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)為m/2-1;則執(zhí)行合并結(jié)點(diǎn)的操作。如結(jié)點(diǎn)原為： （………….(Ki,Ai),(Ki+1,Ai+1),………….）

（A0’,(K1’,A1’)………）

（A0’‘,(K1’‘,A1’‘)………）

……K1L………第L層：找到了被刪結(jié)點(diǎn)的替身。例如：3階B_樹(shù)的刪除操作。m=3,m/2-1=1;至少1個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。324455390371005061，70被刪關(guān)鍵字324456190371005370借：向被刪結(jié)點(diǎn)方向旋轉(zhuǎn)假定再刪除該關(guān)鍵字32445903710061，70假定再刪除該關(guān)鍵字3，24459010061，703，24459010061，70并并并并：和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及鄰居合并。有可能進(jìn)行到根，使B_樹(shù)的深度降低一層！

§3散列查找由于前兩種查找方法中，記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的，和其關(guān)鍵碼值之間沒(méi)有直接的聯(lián)系，因此在進(jìn)行檢索時(shí)，必須采用“比較”手段來(lái)實(shí)現(xiàn)，顯然，查找的效率依賴(lài)于檢索過(guò)程中進(jìn)行比較的次數(shù)。

于是，理想的查找是不經(jīng)過(guò)任何比較或少經(jīng)過(guò)比較就能夠得到所查找的元素，則必須在記錄與其關(guān)鍵字值之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系h，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中的一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)，這樣在檢索時(shí)，找到給定值K的影象H（K），若記錄中存在關(guān)鍵碼和k相等的記錄，則必然存儲(chǔ)在h(k)的存儲(chǔ)位置上，因此不需要進(jìn)行比較即可直接得到所查找的記錄。通常稱(chēng)這個(gè)對(duì)應(yīng)關(guān)系h為散列函數(shù)，采用該散列函數(shù)所建立的表稱(chēng)為散列表。

§3散列查找

實(shí)踐表明：

（1）如果散列表是一一對(duì)應(yīng)的函數(shù)，則根據(jù)散列函數(shù)對(duì)給定的值進(jìn)行某種運(yùn)算，即可得到待查找元素的位置；

（2）散列表占用的空間可能比結(jié)點(diǎn)空間多；

（3）散列函數(shù)的構(gòu)造原則：運(yùn)算盡量簡(jiǎn)單，而且所占用空間均勻分布；

（4）不同的關(guān)鍵字值可能得到相同的函數(shù)值，即可能有沖突產(chǎn)生。

§3散列查找由此可見(jiàn)：散列查找必須解決兩個(gè)問(wèn)題：

（1）構(gòu)造一個(gè)盡量簡(jiǎn)單但沖突少、“均勻”的“好”散列函數(shù)；（2）正視而且必須解決面臨的“地址沖突”問(wèn)題。可見(jiàn)：實(shí)際上第一個(gè)問(wèn)題包容了第二個(gè)問(wèn)題。因?yàn)橐粋€(gè)“優(yōu)秀的”散列函數(shù)必須解決地址沖突問(wèn)題。

所以只要解決了第一個(gè)問(wèn)題即可解決第二個(gè)問(wèn)題。給出較好的散列函數(shù)是由HASH給出的，故散列查找又稱(chēng)HASH查找。

§3散列查找

【例】11個(gè)元素的關(guān)鍵碼分別為18，27，1，20，22，6，10，13，41，15，25。選取關(guān)鍵碼與元素位置間的函數(shù)為f(key)=keymod111.通過(guò)這個(gè)函數(shù)對(duì)11個(gè)元素建立查找表如下：012345678910

2.查找時(shí)，對(duì)給定值kx依然通過(guò)這個(gè)函數(shù)計(jì)算出地址，再將kx與該地址單元中元素的關(guān)鍵碼比較，若相等，查找成功。22|1|13|25|15|27|6|18|41|20|10

哈希表與哈希方法：選取某個(gè)函數(shù)H，依該函數(shù)按關(guān)鍵碼計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值kx計(jì)算地址，將kx與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功，這就是哈希方法(雜湊法)；

哈希方法中使用的轉(zhuǎn)換函數(shù)稱(chēng)為哈希函數(shù)(雜湊函數(shù))；

按這個(gè)思想構(gòu)造的表稱(chēng)為哈希表(雜湊表)。哈希查找的基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，不經(jīng)過(guò)比較，一次存取就能得到所查元素的查找方法定義哈希函數(shù)——在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系叫~哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象哈希函數(shù)可寫(xiě)成：addr(ai)=H(ki)ai是表中的一個(gè)元素addr(ai)是ai的存儲(chǔ)地址ki是ai的關(guān)鍵字關(guān)鍵字集合存儲(chǔ)地址集合hash哈希表——應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫~哈希查找——又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過(guò)程叫~例30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表編號(hào)地區(qū)別總?cè)丝跐h族回族…...1北京2上?！?..…...以編號(hào)作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱(chēng)第一個(gè)拼音字母的序號(hào)作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19從例子可見(jiàn)：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫~同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字，叫該哈希函數(shù)的~哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時(shí)，沖突發(fā)生后，應(yīng)該有處理沖突的方法哈希函數(shù)的構(gòu)造方法1、直接定址法構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線(xiàn)性函數(shù)作哈希地址，即H(key)=key或H(key)=a·key+b特點(diǎn)直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突實(shí)際中能用這種哈希函數(shù)的情況很少2、數(shù)字分析法構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位與另兩位的疊加作哈希地址3、平方取中法構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址適于不知道全部關(guān)鍵字情況折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址種類(lèi)移位疊加：將分割后的幾部分低位對(duì)齊相加間界疊加：從一端沿分割界來(lái)回折送，然后對(duì)齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加4、除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=keyMODp，pm特點(diǎn)簡(jiǎn)單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞5、隨機(jī)數(shù)法構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即H(key)=random(key)適于關(guān)鍵字長(zhǎng)度不等的情況選取哈希函數(shù)，考慮以下因素：計(jì)算哈希函數(shù)所需時(shí)間關(guān)鍵字長(zhǎng)度哈希表長(zhǎng)度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率3.2處理沖突的方法開(kāi)放定址法方法：當(dāng)沖突發(fā)生時(shí)，形成一個(gè)探查序列；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開(kāi)放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)MODm，i=1,2,……k(km-1)其中：H(key)——哈希函數(shù)m——哈希表表長(zhǎng)di——增量序列分類(lèi)線(xiàn)性探測(cè)再散列：di=1,2,3,……m-1二次探測(cè)再散列：di=12,-12,22,-22,32,……±k2(km/2)偽隨機(jī)探測(cè)再散列：di=偽隨機(jī)數(shù)序列例表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，H(key)=keyMOD11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突H1=(5+1)MOD11=6沖突H2=(5+2)MOD11=7沖突H3=(5+3)MOD11=8不沖突38(2)H(38)=38MOD11=5沖突H1=(5+12)MOD11=6沖突H2=(5-12)MOD11=4不沖突38(3)H(38)=38MOD11=5沖突設(shè)偽隨機(jī)數(shù)序列為9，則：H1=(5+9)MOD11=3不沖突38再哈希法方法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，計(jì)算下一個(gè)哈希地址，即：Hi=Rhi(key)i=1,2,……k其中：Rhi——不同的哈希函數(shù)特點(diǎn)：計(jì)算時(shí)間增加鏈地址法方法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，并用一維數(shù)組存放頭指針例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=keyMOD13,

用鏈地址法處理沖突012345678910111214^127796855198420231011^^^^^^^^^^^^3.3哈希查找過(guò)程及分析哈希查找過(guò)程給定k值計(jì)算H(k)此地址為空關(guān)鍵字==k查找失敗查找成功按處理沖突方法計(jì)算HiYNYN哈希查找分析哈希查找過(guò)程仍是一個(gè)給定值與關(guān)鍵字進(jìn)行比較的過(guò)程評(píng)價(jià)哈希查找效率仍要用ASL哈希查找過(guò)程與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于：哈希函數(shù)處理沖突的方法哈希表的填滿(mǎn)因子=表中填入的記錄數(shù)/哈希表長(zhǎng)度例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=keyMOD13,哈希表長(zhǎng)為m=16，設(shè)每個(gè)記錄的查找概率相等(1)用線(xiàn)性探測(cè)再散列處理沖突，即Hi=(H(key)+di)MODmH(55)=3沖突，H1=(3+1)MOD16=4沖突，H2=(3+2)MOD16=5H(79)=1沖突，H1=(1+1)MOD16=2沖突，H2=(1+2)MOD16=3沖突，H3=(1+3)MOD16=4沖突，H4=(1+4)MOD16=5沖突，H5=(1+5)MOD16=6沖突，H6=(1+6)MOD16=7