版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
第六章查找查找的概念順序查找折半查找靜態(tài)查找樹索引結(jié)構(gòu)與B樹散列法內(nèi)容提要查找(Search)的概念所謂查找,就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素。查找的結(jié)果通常有兩種可能:
查找成功,即找到滿足條件的數(shù)據(jù)元素。這時,作為結(jié)果,可報告該元素在結(jié)構(gòu)中的位置,還可給出該元素中的具體信息。
查找不成功,或查找失敗。作為結(jié)果,應(yīng)報告一些信息,如失敗標(biāo)志、位置等。通常稱用于查找的數(shù)據(jù)集合為查找結(jié)構(gòu),它是由同一數(shù)據(jù)類型的元素(或記錄)組成。在每個元素中其值可唯一地標(biāo)識這個元素的屬性稱為關(guān)鍵字(key)。使用基于關(guān)鍵字的查找,查找結(jié)果是唯一的。查找還可以使用基于其他屬性的查找方法,但查找結(jié)果可能不唯一。衡量一個查找算法的時間效率的標(biāo)準(zhǔn)是查找過程中關(guān)鍵字的平均比較次數(shù),也稱為平均查找長度ASL(AverageSearchLength)。其中:n為表長,Pi為查找第i個記錄的概率,且
Ci為找到該記錄時,曾和給定值比較過的關(guān)鍵字的個數(shù)靜態(tài)查找表結(jié)構(gòu)的定義#definemaxSize100//查找表最大尺寸typedefintElemType;//查找數(shù)據(jù)的類型
typedefstruct{//查找表結(jié)點定義
ElemTypekey;//關(guān)鍵字域
other;//其他數(shù)據(jù)信息}ListNode;typedefstructdataList
{//查找表結(jié)點定義
ListNodedata[maxSize];//數(shù)據(jù)存儲數(shù)組
intn; //數(shù)組當(dāng)前長度}順序查找(SequentialSearch)所謂順序查找,又稱線性查找,主要用于在線性結(jié)構(gòu)中進行查找。設(shè)若表中有n個元素,則順序查找從表的先端(或后端)
開始,依次用各元素的關(guān)鍵字與給定值x進行比較,直到找到與其值相等的元素,則查找成功;給出該元素在表中的位置。若整個表都已檢測完仍未找到關(guān)鍵字與x相等的元素,則查找失敗。給出失敗信息。intlocation(SqListL,DataType&x){i=0;while(i<=L.length&&L.data[i].key!=x.key)i++;if(i<=L.length)returni;elsereturn0;}//locationi<=L.lengthL.data[i].key!=x.keyST.elemiST.elemi60ikval=64kval=60i64設(shè)置“監(jiān)視哨”的順序查找算法intLinearSearch(dataList&L,ElemTypex){//在數(shù)據(jù)表L.data[0]..L.data[n-1]
中順序查找關(guān)鍵字//值與給定值x相等的數(shù)據(jù)元素,
L.data[n].key
作為//控制搜索自動結(jié)束的“監(jiān)視哨”使用
L.data[L.n].key=x;
inti=0;
//將
x
送表尾的下一個位置設(shè)置監(jiān)視哨
while(L.data[i].key!=x)i++;
//從前向后順序查找
returni;}每次循環(huán)減少了一次控制循環(huán)結(jié)束的條件判斷i<L.length()。當(dāng)n很大時,可節(jié)省很多時間設(shè)查找第i
個元素的概率為
pi,查找到第i
個元素所需比較次數(shù)為
ci,則查找成功的平均查找長度為:在順序查找并設(shè)置“監(jiān)視哨”情形,ci=i+1,i=0,1,,n-1,因此算法分析設(shè)查找概率相等,即pi=1/n,i=1,2,,n。則查找成功的平均查找長度為:而查找不成功時,一定把表中所有元素檢測了一遍,一直到監(jiān)視哨。所以查找不成功的平均查找長度為:ASLunsucc=
n+1。順序查找可以用遞歸方法實現(xiàn)。當(dāng)查找表中第一個元素即為所求,查找成功;否則對除第一個元素外的后續(xù)表元素構(gòu)成的查找表使用相同方法遞歸查找。當(dāng)后續(xù)查找表為空,則查找失敗。順序查找的遞歸算法int
SeqSearch(dataList&L,ElemTypex,intloc){//在數(shù)據(jù)表L.data[0]..L.data[n-1]中查找其關(guān)鍵字值//與給定值x匹配的元素,函數(shù)返回其表中位置。//參數(shù)
loc
是在表中開始查找位置
if(loc>=L.n)return
-1;//查找失敗
elseif(L.data[loc].key==x)returnloc;
//查找成功
elsereturnSeqSearch(L,x,loc+1);
//遞歸查找}基于有序順序表的順序查找有序順序表限定表中的元素按照其關(guān)鍵字值從小到大或從大到小依次排列。在這類表中進行查找比表中元素任意存放,查找速度會有所提高。在有序順序表中做順序查找時,若查找不成功,不必檢測到表尾才停止,只要發(fā)現(xiàn)有比它的關(guān)鍵字值大的即可停止查找?;谟行蝽樞虮淼捻樞虿檎宜惴╥ntSeqSearch(dataList&L,ElemTypex){//在數(shù)據(jù)表L.data[0]..L.dada[n-1]
中順序查找關(guān)鍵字//值為x
的數(shù)據(jù)元素
for(inti=0;i<L.n;i++)
if(L.data[i].key==x)returni;//成功成功
elseif(L.data[i].key>x)break;//查找失敗return
-1;
//順序查找失敗,返回失敗信息}折半查找折半查找只適用于有序順序表。做折半查找時,先求位于查找區(qū)間正中的元素的下標(biāo)mid,用其關(guān)鍵字值與給定值x比較:A.data[mid].key==x,查找成功;A.data[mid].key>x,把查找區(qū)間縮小到表的前半部分,繼續(xù)折半查找;A.data[mid].key<x,把查找區(qū)間縮小到表的后半部分,繼續(xù)折半查找。如果查找區(qū)間已縮小到一個元素,仍未找到想要查找的元素,則查找失敗。查找成功的例子-101346810126012345678查找lowmidhigh6
6810125678lowmidhigh665lowmidhigh6low
指示查找區(qū)間的下界;high
指示查找區(qū)間的上界;mid=(low+high)/2。查找失敗的例子-101346810125012345678查找lowmidhigh5
6810125678lowmidhigh655lowmidhigh5折半查找的算法intBinSearch(dataList&L,ElemTypex){
inthigh=L.n-1,low=0,mid;
while(low<=high){ //low>high表明失敗mid=(low+high)/2;
if(L.data[mid].key<x)low=mid+1; //右縮查找區(qū)間
else
if(L.data[mid].key>x)high=mid-1;//左縮查找區(qū)間
elsereturnmid;//查找成功
}
return
-1;//查找失敗}遞歸的折半查找算法intBinSearch(dataList&L,ElemTypex,
intlow,
inthigh){intmid=-1;if(low<=high){
mid=(low+high)/2;
if(L.data[mid].key<x)mid=BinSearch(L,x,mid+1,high);
elseif(L.data[mid].key>x) mid=BinSearch(L,x,low,mid-1);}returnmid;}//調(diào)用方式
BinSearch(L,x,0,L.n-1);有序順序表的折半查找的判定樹
(10,20,30,40,50,60)50(20,30)(-∞,10)(10,20)(30,40)(40,50)(50,60)(60,70)======30<<<<<<>>>>>>204060ASLunsucc=(2*1+3*6)/7=20/7ASLsucc
=(1+2*2+3*3)/6=14/6
10表示有序表中已有的結(jié)點,樹的根結(jié)點是查找序列的第一個數(shù)據(jù)元素失敗結(jié)點,表示表中兩個相鄰元素之間的不在表中的數(shù)據(jù)值的集合折半查找性能分析若設(shè)
n=2h-1,則描述折半查找的判定樹是高度為
h
的滿二叉樹。
2h=n+1,h=log2(n+1)第1層結(jié)點有1個,查找第1層結(jié)點要比較1次;第2層結(jié)點有2個,查找第2層結(jié)點要比較2次;…,
第i(1
i
h)
層結(jié)點有2i-1個,查找第i層結(jié)點要比較i
次,…。假定每個結(jié)點的查找概率相等,即pi=1/n,則查找成功的平均查找長度為可以用歸納法證明:這樣索引結(jié)構(gòu)與B樹當(dāng)數(shù)據(jù)元素個數(shù)很多,n很大時,可采用索引方法來實現(xiàn)存儲和查找。示例:有一個存放職工信息的數(shù)據(jù)表,每一個職工元素有近1k字節(jié)的信息,正好占據(jù)一個頁塊的存儲空間。假設(shè)內(nèi)存工作區(qū)僅能容納64k字節(jié)的數(shù)據(jù),在某一時刻內(nèi)存最多可容納64個元素以供查找。線性索引(LinearIndexList)
01k2k3k4k5k6k7k職工號
姓名
性別
職務(wù)
婚否
83
林達
女
教師已婚
…
08
陳洱
男
教師已婚...
03
張珊
男
教務(wù)員已婚...
95
李斯
女
實驗員未婚...
24
何武
男
教師已婚...
47
王璐
男
教師已婚...
17
劉淇
男
實驗員未婚...
51
岳跋
女
教師未婚...
索引表數(shù)據(jù)表keyaddr032k081k176k244k475k517k830953k如果元素總數(shù)有
14400
個,不可能把所有元素的數(shù)據(jù)一次都讀入內(nèi)存。無論是順序查找或折半查找,都需要多次讀取外存記錄。如果在索引表中每一個索引項占4個字節(jié),索引項給出一個職工元素的關(guān)鍵字及其存儲地址,用以索引一個職工元素,則14400
個索引項需要56.25k字節(jié),在內(nèi)存中可以容納所有的索引項。這樣只需從外存中把索引表讀入內(nèi)存,經(jīng)過查找索引后確定了職工元素的存儲地址,再經(jīng)過1次讀取元素操作就可以完成查找。只需2次讀盤即可。所以,采用索引結(jié)構(gòu)可以加速查找速度,特別是在有大量內(nèi)外存交換的情形。索引可分為2種:稠密索引:一個索引項對應(yīng)數(shù)據(jù)表中一個元素。當(dāng)元素在外存中按加入順序存放而不是按關(guān)鍵字值有序存放時必須采用稠密索引,這時的索引結(jié)構(gòu)叫做索引非順序結(jié)構(gòu)。稀疏索引:當(dāng)元素在外存中有序存放時,可以把所有n個元素分為b個子表存放,一個索引項對應(yīng)數(shù)據(jù)表中一組元素(子表)。第i個索引項是第i個子表的索引項,i=0,1,…,n-1。這種索引結(jié)構(gòu)叫做索引順序結(jié)構(gòu)。對索引順序結(jié)構(gòu)進行查找時,采用分塊查找:先在索引表ID
中查找給定值K,確定滿足
ID[i-1].max_key<K
ID[i].max_key 的
i
值,即待查元素可能在的子表的序號。2212133029333642444839406074567980669282889894子表1子表2子表3子表4數(shù)據(jù)區(qū)33488098索引表1234max_max_keyaddr再在第i個子表中按給定值查找要求的元素。索引表是按max_key有序的,且長度也不大,可以折半查找,也可以順序查找。各子表內(nèi)各個元素如果也按元素關(guān)鍵字值有序,可以采用折半查找或順序查找;如果不是按元素關(guān)鍵字值有序,只能順序查找。索引順序查找的查找成功時的平均查找長度
ASLIndexSeq=ASLIndex
+ASLSubList 其中,
ASLIndex
是在索引表中查找子表位置的平均查找長度,ASLSubList是在子表內(nèi)查找元素位置的查找成功的平均查找長度。用數(shù)學(xué)方法可導(dǎo)出,當(dāng)s=
時,ASLIndexSeq取極小值+1。這個值比順序查找強,但比折半查找差。但如果子表存放在外存時,還要受到頁塊大小的制約。若采用折半查找確定元素所在的子表,則查找成功時的平均查找長度為
ASLIndexSeq=ASLIndex
+ASLSubList
log2(b+1)-1+(s+1)/2
log2(1+n/s)+s/2m
路查找樹當(dāng)數(shù)據(jù)元素數(shù)目特別大,索引表本身很大,在內(nèi)存中放不下,需要分批多次讀取外存才能把索引表查找一遍。此時,可以建立索引的索引(二級索引)。二級索引中一個索引項對應(yīng)一個索引塊,登記該索引塊的最大關(guān)鍵字及該索引塊的存儲地址。如果二級索引在內(nèi)存中也放不下,需要分為許多塊多次從外存讀入??梢越⒍壦饕乃饕ㄈ壦饕?。這時,訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取元素。必要時,還可以有4級索引,5級索引,…。這種多級索引結(jié)構(gòu)形成一種m叉樹。樹中每一個分支結(jié)點表示一個索引塊,每個索引項給出各子樹結(jié)點的最大關(guān)鍵字和結(jié)點地址。02061115182329323841454952607795(06,)(15,)(23,)(32,)(41,)(49,)(60,)(95,)(23,)(49,)(95,)roothead多級索引結(jié)構(gòu)形成m路查找樹數(shù)據(jù)區(qū)一級索引(葉結(jié)點)二級索引三級索引四級索引樹的葉結(jié)點中各索引項給出在數(shù)據(jù)表中存放的元素的關(guān)鍵字和存放地址。這種m叉樹用來作為多級索引,就是m路查找樹。B
樹B樹的定義: 一棵m
階B樹是一棵平衡的
m路查找樹,它或者是空樹,或者是滿足下列性質(zhì)的樹:每個結(jié)點最多有m
棵子樹,并具有如下結(jié)構(gòu):
n,P0,(K1,P1),(K2,P2),……,(Kn,Pn)。其中,Pi是指向子樹的指針,0≤i≤n<m;Ki是關(guān)鍵字,
1≤i≤n<m。Ki<Ki+1,1≤i<n。根結(jié)點至少有2個子女;除根結(jié)點外的所有結(jié)點至少有m/2
個子女。所有失敗結(jié)點都位于同一層,它們是查找失敗時查找指針到達的結(jié)點。所有失敗結(jié)點都是空結(jié)點,指向它們的指針都為空。除失敗結(jié)點外,其他結(jié)點
在子樹Pi中所有的關(guān)鍵字都小于
Ki+1,且大于Ki,0<i<n。在子樹Pn中所有的關(guān)鍵字都大于Kn;在子樹P0
中的所有關(guān)鍵字都小于K1。子樹Pi也是m路查找樹,0≤i≤n。事實上,在B樹的每個結(jié)點中還包含有一組 指針D[m],指向?qū)嶋H元素的存放地址。K[i]與D[i](1≤i≤n<m)形成一個索引項(K[i],D[i])。下面左圖不是B樹。右圖是B樹。302040253010154550root4550354020root101525非B樹 B樹35B樹的定義和B樹結(jié)點的定義typedefintBTreeData;//關(guān)鍵字的數(shù)據(jù)類型typedefstructnode{//B樹結(jié)點的定義
intn;//結(jié)點中關(guān)鍵字個數(shù)
structnode
*parent;//雙親指針
BTreeDatakey[m+1];//關(guān)鍵字?jǐn)?shù)組
1m-1
structnode*ptr[m+1];//子樹指針數(shù)組0m-1}BTreeNode,*BTree;//B樹定義
nptr0key1ptr1key2ptr2…ptrn-1keynptrn
B樹的查找算法B樹的查找過程是從根開始的一個在結(jié)點內(nèi)查找和循某一條路徑向下一層查找交替進行的過程。B樹的查找時間與B樹的階數(shù)m
和B樹的高度h
直接有關(guān)。304550354020root101525查找15查找43在查找不成功之后,需進行插入。有下列幾種情況:1)插入后,該結(jié)點的關(guān)鍵字個數(shù)n<m,不修改指針;B樹的插入2)插入后,該結(jié)點的關(guān)鍵字個數(shù)n=m,則需進行“結(jié)點分裂”,令s=m/2,在原結(jié)點中保留
(P0,K1,。。。,Ks-1,Ps-1);建新結(jié)點(Ps,Ks+1,。。。,Kn,Pn);
將(Ks,p)插入雙親結(jié)點;3)若雙親為空,則建新的根結(jié)點。例如:下列為3階B-樹每個結(jié)點最少3/2-1=1個Key,最多3-1=2個key50204080插入關(guān)鍵字=60,
608090,60809090
50806030,40203050808030
50從空樹開始加入關(guān)鍵字(53,75,139,49,145,36)建立3階B樹4975n=1加入5353n=2加入755375n=3加入1397513953n=5加入49,145751391454953n=6加入361391455336在插入新關(guān)鍵字時,需要自底向上分裂結(jié)點,最壞情況下從被插關(guān)鍵字所在葉結(jié)點到根的路徑上的所有結(jié)點都要分裂。若設(shè)B樹的高度為h,
那么在自頂向下查找到葉結(jié)點的過程中需要進行h
次讀盤。n=7加入10149533613914510175
和插入的考慮相反,刪除首先必須找到待刪關(guān)鍵字所在結(jié)點,并且要求刪除之后,結(jié)點中關(guān)鍵字的個數(shù)不能小于m/2-1,否則,要從其左(或右)兄弟結(jié)點“借調(diào)”關(guān)鍵字,若其左和右兄弟結(jié)點均無關(guān)鍵字可借(結(jié)點中只有最少量的關(guān)鍵字),則必須進行結(jié)點的“合并”。B樹的刪除B樹的刪除刪除關(guān)鍵字Ki分為在葉子結(jié)點上刪除和在非葉子結(jié)點上刪除:若Ki不在葉子結(jié)點上,則在刪去Ki之后,應(yīng)以該結(jié)點Pi指針?biāo)甘咀訕渲械淖钚£P(guān)鍵字x來代替被刪關(guān)鍵字Ki所在的位置。在x所在的葉結(jié)點中刪除x。在葉結(jié)點上的刪除有4種情況。情況1被刪關(guān)鍵字所在葉結(jié)點同時又是根結(jié)點且刪除前該結(jié)點中關(guān)鍵字個數(shù)n
2,則直接刪去該關(guān)鍵字并將修改后的結(jié)點寫回磁盤。3649m=3刪除3649情況2被刪關(guān)鍵字所在葉結(jié)點不是根結(jié)點且刪除前該結(jié)點中關(guān)鍵字個數(shù)n
m/2
,則直接刪去該關(guān)鍵字并將修改后的結(jié)點寫回磁盤,刪除結(jié)束。5558刪除55簡單刪除7580m=3刪除5510406560703050acbdefgh58758010406560703050acbdefgh被刪關(guān)鍵字所在葉結(jié)點在刪除前結(jié)點的關(guān)鍵字個數(shù)
n=m/2
-1,若這時與該結(jié)點相鄰的右兄弟(或左兄弟)
結(jié)點的關(guān)鍵字個數(shù)
n
m/2,則調(diào)整:該結(jié)點右兄弟
(或左兄弟)
結(jié)點其雙親結(jié)點以達到新的平衡。情況3結(jié)點聯(lián)合調(diào)整55587580m=3刪除6510406560703050acbdefgh55588010407060753050acbdefgh調(diào)整g,c,h刪除65被刪關(guān)鍵字所在葉結(jié)點在刪除前的關(guān)鍵字個數(shù)n=m/2
-1,若這時與該結(jié)點相鄰的右兄弟(或左兄弟)結(jié)點的關(guān)鍵字個數(shù)n=m/2
-1,則必須合并這兩個結(jié)點。情況455刪除55結(jié)點合并80m=3刪除5510406058753050acbdefgh合并f,g5860801040753050acbdefh8055刪除80結(jié)點合并m=3刪除8010406058753050acbdefgh合并g,h6075551040583050acbdefg1.首先需要找到這個關(guān)鍵字Ki所在的結(jié)點,從中刪去這個關(guān)鍵字。2.若該結(jié)點不是葉結(jié)點,則在刪去Ki之后,應(yīng)以該結(jié)點Pi所指示子樹中的最小關(guān)鍵字x來代替被刪關(guān)鍵字Ki所在的位置。3.在x所在的葉結(jié)點中刪除x。在非葉子結(jié)點上刪除55刪除50刪除5555587580m=3刪除5010406560703050acbdefgh587580刪除55104065607030acbdefgh用55取代用58取代587580104065607030acbdefgh合并f,g587580104060657030acbdefh結(jié)點合并與調(diào)整刪除70刪除55用58取代5880104060657530acbdefh刪除70用75取代刪除7558104060658030acbdefh刪除75用80取代調(diào)整f,c,h58801040606530acbdefh刪除1080304060fh5865dbB+樹一棵m階B+樹是B樹的特殊情形,它與B樹的不同之處在于:所有關(guān)鍵字都存放在葉結(jié)點中,上層的非葉結(jié)點的關(guān)鍵字是其子樹中最大關(guān)鍵字的復(fù)寫。葉結(jié)點包含了全部關(guān)鍵字及指向相應(yīng)數(shù)據(jù)記錄存放地址的指針,且葉結(jié)點本身按關(guān)鍵字從小到大順序鏈接(一級稠密索引)。一棵m階B+樹的結(jié)構(gòu)定義如下:每個結(jié)點最多有m棵子樹;根結(jié)點最少有1棵子樹,除根結(jié)點外,其他結(jié)點至少有m/2棵子樹;有m棵子樹的結(jié)點有m個關(guān)鍵字。所有非葉結(jié)點可以看成是葉結(jié)點的索引,結(jié)點中關(guān)鍵字Ki
與指向子樹的指針Pi
構(gòu)成對子樹的索引項(Ki,Pi),Ki
是子樹中最大的關(guān)鍵字。所有葉結(jié)點在同一層,按從小到大的順序存放全部關(guān)鍵字,各個葉結(jié)點順序鏈接。葉結(jié)點中存放的是對實際數(shù)據(jù)記錄的索引,每個索引項(Ki,Pi)給出記錄的存儲地址。在一棵4階B+樹中,除根結(jié)點外,所有非葉結(jié)點中的子樹棵數(shù)4/2
≤n≤4,其所有的關(guān)鍵字都出現(xiàn)在葉結(jié)點中,且在葉結(jié)點中關(guān)鍵字有序地排列。上面各層結(jié)點中的關(guān)鍵字都是其子樹上最大關(guān)鍵字的副本。m=41015
18222734
404447
5467
727478
8184
15344767
7884
6784
root通常在B+樹中有兩個頭指針:一個指向B+樹的根結(jié)點,一個指向關(guān)鍵字最小的葉結(jié)點。因此,可以對B+樹進行兩種搜索運算:循葉結(jié)點自己拉起的鏈表順序搜索;從根開始進行自頂向下直到葉結(jié)點的隨機搜索。B+樹的插入僅在葉結(jié)點上進行。每插入一個(關(guān)鍵字-指針)索引項后都要判斷結(jié)點中的索引項個數(shù)是否超出范圍m。
當(dāng)插入后葉結(jié)點中的關(guān)鍵字個數(shù)n>m
時,需要將葉結(jié)點分裂為兩個結(jié)點:它們包含的關(guān)鍵字個數(shù)分別為
(m+1)/2
和
(m+1)/2。并且它們的雙親結(jié)點中應(yīng)同時包含這兩個結(jié)點的最大關(guān)鍵字和結(jié)點地址。在非葉結(jié)點中關(guān)鍵字的插入與葉結(jié)點的插入情況類似,但在做根結(jié)點分裂時,必須創(chuàng)建新的父結(jié)點,作為樹的新根。B+樹的插入例如,在一棵4階B+樹中的插入過程如下。連續(xù)插入24,72,01,39的B+樹01243972加入53,結(jié)點分裂01243953723972加入63,90,88,15的B+樹011524395363723972908890加入10,44,68,74的B+樹0110154453631539632439687274889072907290B+樹的刪除B+樹的刪除僅在葉結(jié)點上進行。當(dāng)在葉結(jié)點上刪除一個(關(guān)鍵字-指針)索引項后,結(jié)點中的索引項個數(shù)仍然不少于m/2,這屬于簡單刪除,其上層索引可以不改變。如果刪除結(jié)點的最大關(guān)鍵字,但因在其上層的副本只起了一個引導(dǎo)搜索的“分界關(guān)鍵字”的作用,所以即使樹中已經(jīng)刪除了關(guān)鍵字,但上層的副本仍然可以保留。如果在葉結(jié)點中刪除后,結(jié)點中索引項個數(shù)小于m/2,必須做結(jié)點的調(diào)整或合并工作。
從4階B+樹中做簡單刪除
m=41015182227344044475467727478818415344767
7884
6784簡單刪除關(guān)鍵字47,上層索引可以不改10151822273440445467727478818415344767
7884
6784
從4階B+樹中刪除時的調(diào)整
m=41015182227344044475467727478818415344767
7884
6784刪除關(guān)鍵字15,調(diào)整上層索引改變1018
2227344044475467727478818418344767
7884
6784如果右兄弟結(jié)點的關(guān)鍵字?jǐn)?shù)已達到下限m/2,沒有多余的關(guān)鍵字可以移入被刪關(guān)鍵字所在的結(jié)點,必須進行結(jié)點的合并。將右兄弟結(jié)點中的所有(關(guān)鍵字-指針)索引項移入被刪關(guān)鍵字所在結(jié)點,再將右兄弟結(jié)點刪去。這種結(jié)點合并將導(dǎo)致雙親結(jié)點中“分界關(guān)鍵字”的減少,有可能減到非葉結(jié)點中關(guān)鍵字個數(shù)的下限m/2
以下。這樣將引起雙親結(jié)點的調(diào)整或合并。刪除關(guān)鍵字74,78,A,B結(jié)點合并1018
2227344044475467727478818418344767
7884
67841018
2227344044475467728184183447
6784
4784ABCD散列(Hashing)散列方法在表項存儲位置與其關(guān)鍵字之間建立一個確定的對應(yīng)函數(shù)關(guān)系Hash(
),使每個關(guān)鍵字與結(jié)構(gòu)中一個唯一存儲位置相對應(yīng):
Address
=Hash(Rec.key)在查找時,先對表項的關(guān)鍵字進行函數(shù)計算,把函數(shù)值當(dāng)做表項的存儲位置,在結(jié)構(gòu)中按此位置取表項比較。若關(guān)鍵字相等,則查找成功。在存放表項時,依相同函數(shù)計算存儲位置,并按此位置存放。這種方法就是散列方法。在散列方法中使用的轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此方法構(gòu)造出來的表或結(jié)構(gòu)就叫做散列表。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}
例如:對于如下9個關(guān)鍵字設(shè)
哈希函數(shù)f(key)=
(Ord(第一個字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDei問題:
若添加關(guān)鍵字Zhou,怎么辦?1)哈希函數(shù)是一個映象,即:將關(guān)鍵字的集合映射到某個地址集合上,
它的設(shè)置很靈活,只要這個地址集合的大小不超出允許范圍即可;從這個例子可見,2)由于哈希函數(shù)是一個壓縮映象,因此,在一般情況下,很容易產(chǎn)生“沖突”現(xiàn)象,即:key1key2,而f(key1)=f(key2)。產(chǎn)生沖突的關(guān)鍵字叫同義詞3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。這是因為:在設(shè)計查找表時,只可能知道關(guān)鍵字所屬范圍,而不知道確切的關(guān)鍵字。一般情況下,只能選擇恰當(dāng)?shù)墓:瘮?shù),使沖突盡可能少地產(chǎn)生。因此,在構(gòu)造這種特殊的“查找表”時,除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外;還需要找到一種“處理沖突”
的方法。散列函數(shù)構(gòu)造散列函數(shù)時的幾點要求:散列函數(shù)應(yīng)是簡單的,能在較短的時間內(nèi)計算出結(jié)果。散列函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵字,如果散列表允許有m個地址時,其值域必須在0到m-1之間。散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中。構(gòu)造哈希函數(shù)的常用方法
對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法:
若是非數(shù)字關(guān)鍵字,則需先對其進行數(shù)字化處理。1.直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù)
H(key)=key
或者
H(key)=akey+b1.
直接定址法此法僅適合于:地址集合的大小==關(guān)鍵字集合的大小此方法僅適合于:能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。2.數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us),分析關(guān)鍵字集中的全體,并從中提取分布均勻的若干位或它們的組合作為地址。數(shù)字分析法構(gòu)造:對關(guān)鍵字進行分析,取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大,且可能出現(xiàn)的關(guān)鍵字事先知道的情況例有80個記錄,關(guān)鍵字為8位十進制數(shù),哈希地址為2位十進制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析:位只取8位只取1位只取3、4位只取2、7、5位數(shù)字分布近乎隨機所以:取位任意兩位或兩位與另兩位的疊加作哈希地址除留余數(shù)法構(gòu)造:取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址,即H(key)=keyMODp,pm特點簡單、常用,可與上述幾種方法結(jié)合使用p的選取很重要;p選的不好,容易產(chǎn)生同義詞
實際造表時,采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài)),總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。三、處理沖突的方法
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024山林土地租賃與林業(yè)科技創(chuàng)新合作合同2篇
- 2025航空貨運合同樣本
- 2024年施工單位BIM技術(shù)應(yīng)用人員勞動合同范本3篇
- 2024年暑假工合同范本:暑期實習(xí)兼職服務(wù)規(guī)范3篇
- 2024年無人駕駛技術(shù)研發(fā)與許可合同
- 2024年農(nóng)產(chǎn)品銷售退款保障協(xié)議合同范本3篇
- 智能化商場監(jiān)控施工合同
- 2025食品委托生產(chǎn)合同范文
- 電力公司維修工招聘合同范本
- 建筑安裝吊車租賃合同樣本
- 新版哈薩克斯坦簽證申請表
- 俄語閱讀知到章節(jié)答案智慧樹2023年哈爾濱師范大學(xué)
- 《憐憫是人的天性》優(yōu)秀教學(xué)設(shè)計(統(tǒng)編版高二選擇性必修中)共3篇
- 九招致勝課件完整版
- 奧鵬北京師范大學(xué)22春《信息技術(shù)教育應(yīng)用 》離線作業(yè)非免費答案
- 移動電源中英文規(guī)格書
- 血透患者需要定期抽血檢查的項目
- 2022年環(huán)保標(biāo)記試題庫(含答案)
- 港口水工建筑物課程設(shè)計范本方塊
- 北京粉末冶金零部件項目可行性研究報告
- 二年級上冊音樂教案-過新年 蘇少版
評論
0/150
提交評論