第7章查找科技學(xué)院計(jì)算機(jī)

??老Office:9棟樓9-206（網(wǎng)絡(luò)教研室?: 課件：:第7章查哈希表教學(xué)內(nèi)教學(xué)目

ASLASLn關(guān)關(guān)鍵字的平均比較次數(shù)，也稱平均搜ASL(AverageSearchn：記錄的個(gè)pi：查找第i個(gè)記錄的常認(rèn)為pi=1/nci：找到第i個(gè)記錄所需一、順序查找（線性查找順序查找（線性查找）使用數(shù)組:若查找函數(shù)設(shè)計(jì)如下intseqSeach(inta[],intn,intelem){inti=0;while(i<n&&a[i]!=elem)i++;if(a[i]==elem)returni;elsereturn-}此查找函數(shù)正確順序查找（線性查找）使用數(shù)組:若查找函數(shù)設(shè)計(jì)如下intseqSeach(inta[],intn,intelem){inti=0;while(i<n&&a[i]!=elem)i++;if(i<n)returni;elsereturn-}此查找函數(shù)才正順序查 typedefstruct

順序typedefstruct

//表基

第2章在順序表L中查找值為e的數(shù)#defineMAXSIZEtypedefstructElemTypeint

//指向數(shù)據(jù)元素 //線性表的當(dāng)前intLocateELem(SqListL,ElemType{for(i=0;i<if(L.elem[i]==e)returni+1;return0;}改進(jìn)：把待查關(guān)鍵字key存入表頭（“哨兵”），逐個(gè)比較，可免去查找過(guò)程中每一步都要檢測(cè)是否查找完畢加快速typedefstruct

intSearch_Seq(SSTableST,KeyTypekey//若成功返回其位置信息，否則返回for(i=ST.length;ST.R[i].key!=key;--i//不用for(i=ni>0;ifor(i=1;i<=nreturn(3/*在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則返該元素在表中的位置；否則返回-intSearch_Seq(SSTableST,KeyTypekey){for(i=0;ST.R[i].key!=key;++i從前往后找if(i<ST.length)returni;elsereturn-1;平均查找長(zhǎng)度為確定記錄在查找表中的位置，數(shù)的期望查找成 nST假定Pi11 nASL查找不成功

(ni1)n2n2ASL=n+平均查找長(zhǎng)ASL

(ni1)

1(n1)

3(n2n 順序查找的性能分 設(shè)表中各記錄查找概率相ASLs(n)=(1+2+...+n)/n查找不成功時(shí)的平均查找長(zhǎng) ASLf順序查找算法有特 算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無(wú)任何要求（順序和鏈?zhǔn)絥A1nAS。查找概率查找概率相等時(shí)，ASL有序表的順序個(gè)元后的元素的關(guān)鍵字均大于key，所以表 –在有序表中，取中間的記錄作為比較對(duì)象，如果要查找記2.To10i，，i=T1e當(dāng)lo<=i：計(jì)算中間記錄的位置將待查記錄的關(guān)鍵字key和R[mid].key進(jìn)行a．若key=R[mid].key，查找成功，mid素b．若key>r[mid].key，說(shuō)明若存在要查找的元素，查找表的后半部分。修改查找范圍的下界：low=mid+1，轉(zhuǎn)重復(fù)以上過(guò)程，當(dāng)low>high時(shí)，表示查找失敗折半找

若k>R[mid].key，則

51234567895 5lowmid折半

若k>R[mid].key，則

找 5

555

7

lowmid折半直至low>high時(shí)，查找失 5low 5high折半查找（非遞歸算法 初始時(shí)，令讓k與mid指向的記錄比較 –若k==R[mid].key，查找–若k<R[mid].key，則high=mid-–若k>R[mid].key，則重復(fù)上述操作，直至low>high折半【算法描述】-算法 elseif(key<ST.R[mid].key)high=mid-1;//前一子表查else //后一子表查}return //表中不存在待查元}Procedurebinsearch(A[],key,low, //第一項(xiàng)數(shù)據(jù)的索引值小{mid=(lowhigh)/

//計(jì)算中間{

//「鍵值」與「中間值」比較

Case"="return //Casereturnbinsearch(A,keylowmid-1);//遞歸調(diào)用找Casereturnbinsearch(A,keymid+1,high) //遞歸調(diào)用找Return-End

//搜尋失敗，傳回-折半查找（遞歸算法intSearch_Bin(SSTableST,KeyTypekey,intlow,int{if(low>high)return0; if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)Search_Bin(ST,key,low,mid-1);//遞Search_Bin(STkey,mid+1,high//}折半查找的性能分析－判定 56

10

外結(jié)若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)方形結(jié)點(diǎn)為判定樹(shù)的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn):6

10內(nèi)結(jié)--

Cost(levelT(ai)pi)((levelT(ei)1)qi

外結(jié)ASLASL＝1/11*(1*1＋2×2＋4×3+4*46

10--

外結(jié)查找成功時(shí)比較次數(shù)：為該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)，不超過(guò)的深度d=log2n+1=查找不成功的過(guò)程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑dd-1性質(zhì)4:具有性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為log2nk-1 k-1k

2k12k2k?1?12k?1?1＜n≤2k?12k?1≤n＜2k所以k=log2n+1注log2n＋1折半查找的性能比順序查找效率高,時(shí)間復(fù)雜度O(log2n)。 折半3.折半查找的性能分–假設(shè)有序表的長(zhǎng)度n=2h-1（反之h=log2(n+1)），度 1 ASLp C

h2h1 ASLn1log(n1) –n>50分塊分塊分塊索引表的類(lèi)型定義如#definen4typedefstruct{ElemTypeinttypedefstruct{

indexItemint分塊值為、、、，分為四個(gè)塊和索引表，如8分塊intSearch_Idx(SSTableST,indexTableID,ElemTypekey){intlow=1,high=ID.length,mid,s,t,found=0;if(k<ID.elem[mid].key)high=mid-1;elseif(k>ID.elem[mid].key)low=mid+1;elsefound=1;low=mid;}/*找到，確定下一步的查找塊}//s=ID.elem[low].stadr;//下一步的查找范圍定位在第low塊else分塊if(ST.elem[t].key==k)returnelse{ if(p!=(t+1))returnk;elsereturn分塊–分塊查找的平均查找長(zhǎng)度為索引查找和塊內(nèi)查找的平均查ASLL

b1

s1

s22s –分塊查找的優(yōu)點(diǎn)是在表中插入或刪除一個(gè)記錄時(shí)，只要找的空間，以及將初始表分塊排序的運(yùn)算。分塊分塊查找（塊間有序，塊內(nèi)無(wú)序。含每個(gè)子表的起始地址（即頭指針）717189第1 第2 第3分塊查找過(guò)

分塊②確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)分塊查找性能對(duì)索引表查找的 對(duì)塊內(nèi)查找的ASLbslog2(n1)s (log2nASLbsn1) S為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的Sb分塊查找優(yōu)

缺點(diǎn)：要增加一個(gè)索引表的空間并對(duì)初始索引鍵鍵若表中存在，則成功返否則插入關(guān)鍵字等于key的記二叉二叉排序樹(shù)或是空樹(shù)，或是滿足如下性質(zhì)的二叉樹(shù) 其左 本身又各是一棵二叉排序二叉排序下列圖形中，哪下列圖形中，哪個(gè)不是二叉排序樹(shù)二叉排序練練

得到一個(gè)得到一個(gè)關(guān)鍵字的遞增二叉排序樹(shù)的操作－查 若大于根結(jié)點(diǎn)，查其

在左 上的操作類(lèi)

【算法思 2若二叉排序樹(shù)非空，將給定值key與根結(jié)點(diǎn)的關(guān)鍵T->data.key②若key小于T->data.key，則進(jìn)一步查找 ③若key大于T->data.key，則進(jìn)一步查找 二叉排序樹(shù)的–二叉排序樹(shù)用二叉鏈表 typedefstruct

typedefstructElemType structBSTNode*lchild,*rchild二叉排elseif(key<T->data.key)returnSearchBST(T-//在 中繼續(xù)查//在 中繼續(xù)查}//二叉排二叉排序樹(shù)的操 樹(shù)中已有，不再樹(shù)中沒(méi)有，查找直至某個(gè)葉子結(jié)點(diǎn)的左或右 為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)插插入的元素一定在二叉排序樹(shù)的操作插入結(jié)點(diǎn)

二叉排序樹(shù)的操{10，18，3，8，12，2， 3 87二叉排二叉排序樹(shù)不同插入次序的序列生成不同形態(tài)的二叉排

二叉排二叉排序樹(shù)的操防止重 后樹(shù)的高度增–刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清，再釋放它即可 –被刪結(jié)點(diǎn)左、 都存在，可以在它的。查找的性能分 nnpici1223252.2(左圖npici1234553(右圖n查找的性能分 平均查找長(zhǎng)度和二叉樹(shù)的形態(tài)有關(guān)，即最好：log2n（形態(tài)勻稱，與二分查找的判定樹(shù)相似（n+1)/2（單支樹(shù) n

pici(12232)/52.2( npici1234553(n院院練例:3個(gè)結(jié)點(diǎn)3

Exampleforoptimal

Cost(levelT(ai)pi)((levelT(ei)1)qi searchtreeswithequalWithequalprobabilitiespi=qi=1/7foralli,weCost(tree(a))3*13*13*12*12*11*11*1 Cost(tree(b))2*12*13*13*13*11*11*1 Cost(tree(c))2*12*12*11*12*12*12*1 Cost(tree(d))1*11*13*13*13*12*12*1 Cost(tree(e))1*11*12*12*13*13*13*1 q0 q1q0q1q2q1 ExampleExampleforoptimalbinarysearchtreeswithdifferent(levelT(ai)pi)((levelT(ei)1)qi 3210iCost(tree(a))3*.153*.53*.12*.12*.051*.051*.052.65Cost(tree(b))2*.152*.53*.13*.13*.051*.051*.052.05Cost(tree(c))2*.152*.52*.11*.12*.052*.052*.051.9Cost(tree(d))1*.151*.53*.13*.13*.052*.052*.051.6Cost(tree(e))1*.151*.52*.12*.13*.053*.053*.051.5q0 q1q0q1q2

Cost(levelT(ai)pi)((levelT(ei)1)qi OptimalForagivensetofprobabilities,ourgoalistoconstructabinarysearchtreewhoseexpectedsearchissmallest.Wecallsuchatreeanoptimalbinarysearchtree.平衡二(BalancedBinary是平是平衡二叉所有結(jié)點(diǎn)的左、 平衡二叉樹(shù)(AVL樹(shù)任一結(jié)點(diǎn)的平衡因子只能?。?1、01；如果對(duì)于一棵有n個(gè)結(jié)點(diǎn)的AVL樹(shù)，其O(log2n)數(shù)量級(jí)，ASL也保持在O(log2n)量級(jí)平衡二叉樹(shù)(AVL樹(shù)練習(xí)：判斷下列二叉樹(shù)是否AVL- - 0

- 0(a)平衡 (b)不平衡平衡二叉樹(shù)(AVL樹(shù)LLRR平衡旋LR平衡旋LLRR平衡旋LR平衡旋RL平衡旋平衡二叉樹(shù)(AVL樹(shù)平衡二叉樹(shù)（BalancedBinary最小不平 的調(diào)整方法 平衡二叉樹(shù)(AVL樹(shù)最小不平 的調(diào)整方法 平衡二叉樹(shù)(AVL樹(shù)最小不平 的調(diào)整方法 平衡二叉樹(shù)(AVL樹(shù)最小不平 的調(diào)整方法–雙向旋轉(zhuǎn)(先右后左)平衡處理(RL型)：在A的右 中插入新結(jié)點(diǎn)造成失衡，則先以C ，進(jìn)行一次右旋平衡處理，將B作為C的 平衡二叉樹(shù)(AVL樹(shù)平衡二叉–在平衡二叉樹(shù)上進(jìn)行查找的過(guò)程和在二叉排若在A的的若在A的的結(jié)點(diǎn)，使A的平衡因子從12，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)(以B為旋轉(zhuǎn)軸LLB RR若在A的 的 上插結(jié)點(diǎn)，使A的平衡因子從-1增至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn) (以B為旋轉(zhuǎn)軸 若在A的 的 上插(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸4）RL平衡旋 (以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸

A A 平衡二叉樹(shù)(AVL樹(shù)【調(diào)整原LLLRRLRR標(biāo)線牽涉到三個(gè)節(jié)點(diǎn)。而三個(gè)節(jié)點(diǎn)中，將中間鍵值(一)LL型(Left- (二)RR型(Right-大L中大L中LCAR中R大B B B 小(三)LR型(Left- (四)RL型(Right-大L大LBR中AR大LCCC 小調(diào) 中練習(xí)：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排（--需要RR平衡旋 (繞B逆轉(zhuǎn),B為根0

- 0

需要RL平衡旋(繞C先順后逆0 0 ConstructanAVLtreeForeachofthefollowinglists,constructanAVLtreebyinsertingtheir a.1,2,3,4,5, b.6,5,4,3,2,c.3,6,5,1,2,a.1,2,3,4,5, b.6,5,4,3,2, c.3,6,5,1,2,a.1,2,3,4,5, b.6,5,4,3,2, c.3,6,5,1,2,B 。(有m/2~m m階排序樹(shù)及B樹(shù)m階B樹(shù)符合下列條樹(shù)根至少有2 ，除非它也是樹(shù)葉除了樹(shù)根和樹(shù)葉之外，其余的內(nèi)部節(jié)點(diǎn)，至少 m/2 所有的樹(shù)葉都在同一均相同L0K1L1K2 4 f4

g3340

i6369 BBtreeofOrderBB樹(shù)允許多個(gè)鍵值存放在一個(gè)節(jié)點(diǎn)。其每個(gè)節(jié)點(diǎn)內(nèi)的鍵值是經(jīng)過(guò)排序的，以方便搜尋。如果節(jié)點(diǎn)存放的鍵值數(shù)目達(dá)到上限，就成兩個(gè)新節(jié)點(diǎn)，并將中間的鍵值向上插入其父節(jié)點(diǎn)。這種樹(shù)狀結(jié)構(gòu)可保證所有葉節(jié)點(diǎn)都處于同一個(gè)高logm(n+1)≤ ≤注: BtreeofOrder4--InsertBtree假設(shè)輸入的數(shù)據(jù)庫(kù)為ASEAR,C,HI,NG,X,A,M,P,L,E}，第二個(gè)A加入{A,E,S}節(jié)點(diǎn)后，將會(huì)超過(guò)2-3-4樹(shù)的限制。這時(shí)候便要將{AAES}予以，并將其中間值E取出成為父節(jié)點(diǎn)。Btree Btree m階排序樹(shù)及B樹(shù)

L0K1L1K2

個(gè)可插入點(diǎn)（一定是樹(shù)葉）412e1821f2427g3340h

i6369j

L0K1L1K2

樹(shù)葉，同時(shí)將中間的鍵值（第2個(gè)）

4 f4

g3340

i6369

m階排序樹(shù)及B樹(shù)abcef2427gabcef2427g3340i6369j74774dL0L0K1L1K2abcef2427hi6369j74774

m階排序樹(shù)及B樹(shù)L0L0K1L1K2abcef2427hi6369j74774加入鍵值

L0K1L1K2xxabcd B樹(shù)的方法主要是要應(yīng)用在大型文件系統(tǒng)中。因?yàn)槠鋬?nèi)存有限，再加上數(shù)據(jù)量很大時(shí)，我們無(wú)法一次將整個(gè)樹(shù)狀結(jié)構(gòu)加載內(nèi)存來(lái)運(yùn)算。所以，樹(shù)狀結(jié)構(gòu)會(huì)存放在像硬盤(pán)這樣的裝置中，通常每個(gè)節(jié)點(diǎn)會(huì)配置一個(gè)單位以方便存取。當(dāng)B樹(shù)的節(jié)點(diǎn)數(shù)越少，高度越低，則存取磁B+在B+樹(shù)中的節(jié)點(diǎn)通常被表示為一組有序的元素和子指針。如果此B+樹(shù)的序數(shù)(order)是m，則除了根之外的每個(gè)節(jié)點(diǎn)都包含最少m/2個(gè)元素最多m-1個(gè)元素，對(duì)于任意的節(jié)點(diǎn)B+B+樹(shù)的特點(diǎn)是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對(duì)數(shù)時(shí)間復(fù)雜度。B+樹(shù)元素自底向上插入，這與B+樹(shù)背后的想法是內(nèi)部節(jié)點(diǎn)可以有在預(yù)定范圍內(nèi)的可變量目的子節(jié)點(diǎn)。因此，B+樹(shù)不需要像其他自平衡二元搜索樹(shù)B+2-3左子節(jié)點(diǎn)所存放數(shù)據(jù)右子節(jié)點(diǎn)所存放數(shù)據(jù)皆Ldata.keyRdata.key9 2-3log3(n+1)-1≤h≤log2(n+1)-98Constructionofa2-3A2-3treeisalwaysheight-Forthelist9,5,8,3,2,4,2-323樹(shù)其實(shí)就是「3階的B樹(shù)」Btreeoforder3。因此在23樹(shù)上的每個(gè)節(jié)具有1個(gè)鍵值（2個(gè)指標(biāo)）的節(jié)點(diǎn)稱為“2-node”（2-節(jié)點(diǎn)具有2個(gè)鍵值（3個(gè)指標(biāo)）的節(jié)點(diǎn)稱為”3-node（3-節(jié)點(diǎn)）2–3樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)可 為typedefstruct {

KeyLeft,KeyRight *LinkLeft,*LinkMiddle,}232–3樹(shù)的節(jié)點(diǎn)鍵值插入，原則如下（與B樹(shù)同新鍵值的第一個(gè)可插如果樹(shù)葉的數(shù)據(jù)字段如果樹(shù)葉的數(shù)據(jù)字段已經(jīng)額滿沒(méi)有空位，則樹(shù)葉進(jìn)行節(jié) (split)每次插入最多可能使2–3樹(shù)的高度h增加12加入22

2-3加入

17 ，鍵值17加入

78 78

27加入27

72c72148148

節(jié)點(diǎn) 72加入5,9, 72014589014589 加入

7 7

節(jié)點(diǎn) 013589 01358911 2-3-41左子節(jié)點(diǎn)所存放數(shù)據(jù)右子節(jié)點(diǎn)所存放數(shù)據(jù)皆大于(>)鍵值Ldata.keyRdata.key左子節(jié)點(diǎn)所存放數(shù)據(jù)皆小于(<)Ldata.key鍵值中子節(jié)點(diǎn)所存放數(shù)據(jù)皆大于(>)Ldata.key鍵值和小于Rdata.key鍵值右子節(jié)點(diǎn)所存放數(shù)據(jù)皆大于(>)Rdata.key12 2-3-42若為4節(jié)點(diǎn)類(lèi)型，只包含三個(gè)鍵值(Ldata.keyMdata.key和Rdata.key)資料和左、、右子節(jié)Ldata.keyMdata.keyRdata.key左子節(jié)點(diǎn)所存放數(shù)據(jù)皆小于(<)Ldata.key鍵值左中子節(jié)點(diǎn)所存放數(shù)據(jù)皆大于(>)Ldata.key鍵值和小Mdata.key鍵值右中子節(jié)點(diǎn)所存放數(shù)據(jù)皆大于(>)Mdata.keyRdata.key鍵值右子節(jié)點(diǎn)所存放數(shù)據(jù)皆大于(>)Rdata.key鍵鍵樹(shù)中所有的樹(shù)葉節(jié)102-3-42-3-4 加入刪除

刪除插入和刪除需要時(shí)間為Ologn2-3-4樹(shù) 234樹(shù)其實(shí)就是「4階的B樹(shù)」B-treeoforder4在234樹(shù)上的每個(gè)節(jié)點(diǎn)最多有3個(gè)鍵值、4具有1個(gè)鍵值（2個(gè)指標(biāo)）的節(jié)點(diǎn)稱為“2-node”（2-節(jié)點(diǎn)）具有2個(gè)鍵值（3個(gè)指標(biāo)）的節(jié)點(diǎn)稱為“3-node”（3-節(jié)點(diǎn)）具有3個(gè)鍵值（4個(gè)指標(biāo)）的節(jié)點(diǎn)稱為“4-node（4-節(jié)點(diǎn)）。2–3–4樹(shù)的節(jié)點(diǎn)結(jié)構(gòu) typedefstruct

}234每個(gè)節(jié)點(diǎn)有2個(gè)指標(biāo)，并且每個(gè)指標(biāo)有2在畫(huà)出紅－黑樹(shù)時(shí) 一個(gè)2–node轉(zhuǎn)成1個(gè)紅－黑樹(shù)節(jié)點(diǎn)，2個(gè) 標(biāo)的Color均為Black 一個(gè)3node轉(zhuǎn)成2個(gè)紅－黑樹(shù)節(jié)點(diǎn)，這2個(gè)紅－黑樹(shù)節(jié)點(diǎn)以1個(gè)Red

或

變種的AVL樹(shù) Red-Blacktree,簡(jiǎn)稱RB-它是在1972年由·貝爾發(fā)明的，他稱之為“對(duì)稱二LeoJ.Guibas和RobertSedgewick于1978年寫(xiě)的一篇中獲得的特點(diǎn)：利用對(duì)樹(shù)中的結(jié)點(diǎn)“ 壞情況運(yùn)行時(shí)間，它可以在O(logn)時(shí)間內(nèi)做查找，插入和刪除，這里的n是樹(shù)中元素的數(shù)目平衡的擴(kuò)充二叉顏色特征：每個(gè)結(jié)點(diǎn)為“黑色”或“紅色根特征：根結(jié) 是“黑色”外部特征：擴(kuò)充外部葉結(jié)點(diǎn)都是空的“黑色”結(jié) PropertiesofaRed-BlackTherootisEveryrednodehasablackAnychildrenofarednodeareblack;thatis,arednodecannothaveredchildren.Everypathfromtheroottoaleafcontainsthesamenumberofblacknodes.AddingEntriestoaRed-BlackAddinganentrytoared-blacktreeresultsinanewredleaf.Thecolorofthisleafcanchangelaterwhenotherentriesareaddedorremoved.Red-blacktree( 樹(shù))對(duì)樹(shù)而言，只要所有從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑其所經(jīng)h≤2lgn 樹(shù)結(jié) B C和{B,D}互換顏 根節(jié)點(diǎn)C必須為黑樹(shù)的插入與刪除…為O(lgn)。也是O(lgn)。116Datastructureofred-black(RedorAred-blacktreewithninternalnodeshasheightatmostJAVA集合框架：TreeSet和 代碼參Huffman內(nèi)部路徑長(zhǎng)internalpathlength：由樹(shù)根到每個(gè)內(nèi)部節(jié)點(diǎn)的路徑長(zhǎng)度之總和外部路徑長(zhǎng)(externalpathlength：由樹(shù)根到每個(gè)外部節(jié)點(diǎn)的路徑長(zhǎng)度之總和 E F G 此樹(shù)的內(nèi)部路徑長(zhǎng)I0A1B1C)2D)外部路徑長(zhǎng)E2E2F)3G外部路徑長(zhǎng)：由樹(shù)根到每個(gè)外部節(jié)點(diǎn)的路徑長(zhǎng)乘上該節(jié)點(diǎn) 之總此圖 外部路徑長(zhǎng)=2*8(E)+2*7(F)+3*9(G)=對(duì)具有相同外部節(jié)點(diǎn)同 也相同的不同二元樹(shù)， 外部路徑長(zhǎng)也同。其 外部路徑長(zhǎng)最小的二元樹(shù)稱為Huffman樹(shù)，或稱最佳二元樹(shù)算法：Huffman法建算法：Huffman法建立編碼(編碼字母表與頻率 當(dāng)串行中多于一個(gè)元素，重復(fù)循從串行新，將最小的兩 生成一為兩 樹(shù)入串行適當(dāng)位，使串行仍然維持由和Huffman算法：由已知的外部節(jié)點(diǎn)建構(gòu)Huffman樹(shù) 外部路長(zhǎng)最小的樹(shù)） 否 Huffman假設(shè)有ABCDEF六個(gè)樹(shù)葉， 分別為15,8,30,27,5,將樹(shù)葉按 ，由小到大排序好，成為一有序串行E/ B/ A/ F/ D/ C/ E B將節(jié)點(diǎn)NN/ A/ F/ D/ C/取最左邊兩個(gè)節(jié)點(diǎn)N和A，合成新節(jié)點(diǎn) N AE BHuffman將節(jié)點(diǎn)P放入有序串行的適當(dāng)位F/ D/ P/ C/取最左邊兩個(gè)節(jié)點(diǎn)F和D，合成新節(jié)點(diǎn) N A FDEEB將節(jié)點(diǎn)R放入有序串行的適當(dāng)位置，使串行保持次序P/ C/ R/取最左邊兩個(gè)節(jié)點(diǎn)P和C，合成新節(jié)點(diǎn) FD CN AEEBHuffman將節(jié)點(diǎn)S放入有序串行的適當(dāng)位R/ S/取最左邊兩個(gè)節(jié)點(diǎn)R和S，合成新節(jié)點(diǎn)T，只剩一個(gè)FF D30AEBHuffman６個(gè)字母需要編碼，分別是A/15B/8C/30,D/27E/5,F/15，合起來(lái)剛好100%。我們依照前述Huffman算法建構(gòu)Huffman樹(shù)：010F1010F1D0011300E1BAB的編碼右左左右=C的編碼=右右D的編碼=左右E的編碼=右左左左=F的編碼=左左編碼一篇1000個(gè)字母的文章。根據(jù)字母出現(xiàn)的頻率，它們的出現(xiàn)次數(shù)分是A出現(xiàn)的次1000*15B出現(xiàn)的次數(shù)1000*8C出現(xiàn)的次數(shù)=1000*30D出現(xiàn)的次數(shù)=1000*27E出現(xiàn)的次數(shù)1000*5F出現(xiàn)的次數(shù)1000*15因此總共需要的bit150*3+80*4+300*2+270*2+50*4+150*2=編碼，每個(gè)字母用3個(gè)位表示，(8種組合)，共需3000壓縮率＝(1 )*100%207.3哈希 哈希

優(yōu)點(diǎn)：查找速度極快O(1),查找效率與元素個(gè)數(shù)n例2001120V02001120V0將2001011810231的所有信息存入V[31]單元查找2001011810216的信息，可直 例數(shù)數(shù)據(jù)元素序(14，23399251)若規(guī)定個(gè)k的 ），出 結(jié)。內(nèi)9內(nèi)9

232425

39如何內(nèi)9內(nèi)9

14

232425

39根據(jù)哈希函數(shù) 有關(guān)哈希方法(雜湊選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素 位置并按哈希函數(shù)(雜湊函數(shù))：哈希方法中使用的轉(zhuǎn)換有關(guān)哈希表(雜湊表)：按上述思想構(gòu)造的地址 9 11 14 232425 39內(nèi)9沖突：不同的關(guān)鍵碼映射到同一個(gè)哈希key1key2，但同義詞：具有相同函數(shù)值的兩個(gè)關(guān)hashfunction:h:U{0,1,…,m-hashtable:T[0…m-khashstoslot:h(k)hashcollision:twokeyshashtothesame哈希函數(shù)：H(k)=kmod7

地址應(yīng)該足夠 同義如何

是不可能避制制定一個(gè)好的解 方哈希函數(shù)的根據(jù)元根據(jù)元素集合的特性構(gòu)地址均折疊隨機(jī)數(shù)DirectaddressingisasimpletechniquethatworkswellwhentheuniverseUofkeysisreasonablesmall.SupposethatanapplicationneedsadynamicsetinwhichanelementhasakeydrawnfromtheuniverseU={0,1,…,m-1}wheremisnottoolarge.Weshallassumethatnotwoelementshavethesamekey.Forexample:nnumbers,range:[1,k],usesA[1..k]andletA[i]=i.Disadvantage:Wastingtoomuchextra ysisofAlgorithms-Chapter直接尋址akey+ (a、b為常 缺點(diǎn)：要占用連續(xù)地址空間，空間效率低直接尋址哈希函數(shù) 除留余數(shù)法（最常用重點(diǎn)掌握Hash(key)=keymod (p是一個(gè)整數(shù)關(guān)鍵：如何選取合適的技巧：設(shè)表長(zhǎng)為m，取p≤m且為質(zhì)構(gòu)造哈希函數(shù)考慮的①執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間的長(zhǎng)的大鍵字的分 h(k1)=h(k2)thenthereisaGoodhashfunctionsresultinfewerCollisionscanneverbe yTwotypeshandlecollisionsOpenhashing-bucketpointstolinkedlistofallhashingtoClosedhashingonekeyperincaseofcollision,findanotherbucketforoneofthekeysCollisionresolutionlinearprobing:usenextdoublehashing:usesecondhashfunctiontocomputeHashingOpenhashing(separateInopenhashingkeysarestoredinlinkedlistsattachedtocellsofahashingtable.Closedhashing(openThesimplestone–calledlinearprobing,checksthecellfollowingtheonewherethecollision處 的方 1.1.開(kāi)放尋2.2.鏈地開(kāi)放尋址法（開(kāi)地址法 線性線性二次偽隨LinearCheckthecellfollowingtheonewherethecollisionItsufferstheprimaryclusteringh(k,i)(h'(k)i)mod線性探測(cè)法linearprobingHi=(Hash(key)+di)mod (1≤i<m其中：m為哈希表 為增量序列1，2，…m-1，且di=i， 一 ，就找下一個(gè)空地址存線性探測(cè)法linearprobing【作法】是指將哈希地址視為環(huán)狀的空間，當(dāng)溢位發(fā)生以探測(cè)法執(zhí)行會(huì)

碰 345630mod 37mod 40mod②Hash(29)=7，11=8②Hash(29)=7，11=8，哈希地址8為空，因此將29，由H1=(Hash(29)+1)關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，哈希函數(shù)為Hash(key)=keymod 378 3連續(xù)移線性探測(cè)法的特 解決方案：二次(平方)探測(cè)法(quadraticprobingHash(3)=3，哈希地，H1=(Hash(3)+1Hash(3)=3，哈希地，H1=(Hash(3)+12)mod11=4，仍 H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}， 哈希函數(shù)為Hash(key)=keymod11HHi=(Hash(key)±di)mod其中：m為哈希表長(zhǎng)度，m要求是某個(gè)4k+3 3 二次(平方)探測(cè)法(quadraticprobing)(有些【作法當(dāng)f(x)的地址發(fā)生地址 f(xi2modbf(xi2modb的來(lái)找地址，而i是代表第i (碰撞)，并且1<=i<=(b-1)/2，b是質(zhì)數(shù)。平方【范例】假設(shè)有一串?dāng)?shù)列15,29,52,80，并設(shè)b=13，其哈希函數(shù)H(X)=Xmodb，請(qǐng)利用平方探測(cè)法來(lái)解 的問(wèn)題【解答H(80)=80mod13=2產(chǎn)生地 (第1次碰撞進(jìn)行溢位處理：H(xi2mod第1次處理：(2+12)mod13=3又產(chǎn) (第2次碰撞第2次處理：(2+22mod13=63434567XX80第2次碰80第1次碰偽隨機(jī)探測(cè) Hi=(Hash(key)+di)mod其中：m為哈di為隨機(jī)

(1≤i<m開(kāi)放地址法建立哈希表步 step1數(shù)據(jù)元素的關(guān)鍵字key，計(jì)算其哈 step2根據(jù)選擇的 址仍被占用，則繼續(xù)執(zhí)行step2，直到找到 DoubleDoublehashingrepresentsanimprovementoverlinearandquadraticprobinginthatprobesequenceareused.Itsperformanceismoreclosedtouniformhashing.h(k,i)(1(k)ih2(k))modSomefunctions mendedintheliteratureare:h2(k)=(m-2)-kmod(m-2)forsmalltablesorh2(k)=8-(kmod8)h2(k)=kmod97+ forlargeDoubleh(k,i)(1(k)ih2(k))modh1(k)=kmodh2(k)=1+(kmodInserti=0,h1(14)=1,h2(14)=i=1,h(14,1)=(h1(14)+1h2(14))mod13=i=2,h(14,2)=(h1(14)+2h2(14))mod13=2.鏈地址法(拉鏈法鏈表的表頭指針起來(lái)，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)^^0^^^ ^^^3^^4^^^6^^^^^8^^^^

鏈地址法建立哈希表step1取數(shù)據(jù)元素的關(guān)鍵字key，計(jì)算其哈空，則將該元素插入此鏈表；否則執(zhí)行step2解決。step2根據(jù)選擇的處理方法，計(jì)算關(guān)鍵字key的下一個(gè)地址。若該地址對(duì)應(yīng)的???非同義詞不，無(wú)鏈表上結(jié)點(diǎn)空間動(dòng)態(tài)申請(qǐng)，更適合于表長(zhǎng)不定的鏈地址法的哈希給定值給定值與關(guān)鍵字比給定k計(jì)算Y此地址查找查找Y關(guān)鍵字查找查找成按按處方法計(jì)算哈希哈希已已知一組關(guān)鍵字哈希函數(shù)為：H(key)=keyMOD13希表長(zhǎng)為m=16，用線性探測(cè)再散列處 ，即Hi=(H(key)+di)MOD 11 1 311 9 1

，H1=(1+1)

哈希用鏈地址法處

關(guān)鍵字^^0^^^ ^^^3^^4^^^6^^7^^8^^^^^^思關(guān)鍵字無(wú)無(wú)序表查找有有序表折半查找Fortheinput30,20,56,75,31,19andhashfunctionh(K)=KmodConstructtheopenhashtable(separateFindthelargestnumberofkeycomparisonsinasuccessfulsearchinthisFindtheaveragenumberofkeycomparisonsinasuccessfulsearchinthisFortheinput30,20,56,75,31,19andhashfunctionh(K)=KmodConstructtheclosedhashtable(openaddressing,i.e.linearFindthelargestnumberofkeycomparisonsinasuccessfulsearchinthisFindtheaveragenumberofkeycomparisonsinasuccessfulsearchinthisysisofhashingwith slots load

m(theaveragenumberofelementsstoredina哈希表的查

使用平均查找長(zhǎng)度ASL來(lái)衡量查找算法，ASL哈希函處 的方越大，表中記錄數(shù)越多，說(shuō)明表裝得越滿，發(fā)生的可能性就越大，查找哈希表的查找效率分 ASL與裝填因子ASL與裝填因子有關(guān)！既不是嚴(yán)格的O(1)，也不是ASL1 2ASL1 1ASL1ln(1)

）Inparticular,theaveragenumberofpointers(chainlinks)inspectedinsuccessfulsearch,1+/2,andanunsuccessfulsearch,.Ifahashtableinwhichcollisionareresolvedbychaining,asuccessfulsearchtakestime,(1+/2)ontheaverage,andunsuccessfulsearchtakestime,()ontheaverage,undertheassumptionofsimpleuniformhashing.1n

1n Xij

1 E[Xij j

ni j 1n 1

Totaltimerequiredasuccessful 1

n

ji1mn

(1 )(1 1 (nnm1 1 ninm i11

1n2n(n1) nm 1 ysisofopen-addressGivenanopen-addresshash-tablewithloadfactor=n/m<1,theexpectednumberofprobesinanunsuccessfulsearchisatmost1/(1-)assuminguniformhashing.

pi=Pr{exactlyiprobesaccessoccupiedslotsfor0in.Andpi=0ifi>Theexpectednumberofprobes

1

ipiiqi=Pr{atleastiprobesaccessoccupiedslots ipiqi E[X]iPr{Xi i(Pr{Xi}Pr{Xi iPr{Xi

i

nq1

mq n ni n

if0i ) ) m mi qi=0fori> 1ip1q1

... i

i

1Givenanopen-addresshashtablewithload,theexpectednumberofsuccessfulsearchis

1 1 assuminguniformhashingandassumingthateachkeyinthetableisequallylikelytobesearched>Asearchforkfollowsthesameprobesequenceasfollowedwhenkwasinserted.Ifkisthe(i+1)thkeyinsertedinthehashtable,theexpectednumberofprobesmadeinasearchforkisatmost 1i

miAveragingoverallnkeyinthehashtablegivesustheaveragenumberofprobesinasuccessfulsearch:1 m (HmHm1ni0m ni0m 1(lnm1ln(m(SincelniHilni1 11 m 1 0kSeth(k)=kmInterpretingkeysasnaturalASCII(p,t)=(112,116)=(112128+116)=幾點(diǎn)鏈地址法除留余數(shù)法作哈希函數(shù)優(yōu)于