數(shù)據(jù)結構查找

第九章查找本章主要內容：1.查找表的各種實現(xiàn)方法：靜態(tài)查找表動態(tài)查找表2.查找的性能分析——平均查找長度的討論。本章重點：1.熟練掌握順序表和有序表的查找方法；2.熟練掌握二叉排序樹的構造和查找方法；3.掌握二叉平衡樹的維護平衡的方法；4.理解B-樹、B+的特點以及它們的建樹過程；5.熟練掌握哈希表的構造方法，理解與其它結構的表的實質性的差別；6.理解平均查找長度的計算。第九章查找9.1靜態(tài)查找表9.2動態(tài)查找表9.3哈希表第九章查找查找(又稱檢索)，簡單地說就是查表。本教材將查找也歸納為一種數(shù)據(jù)結構——查找表。1．查找表

是由同一類型的數(shù)據(jù)元素(或記錄)構成的集合?？梢岳斫鈱⒏鞣N數(shù)據(jù)結構(數(shù)組、鏈表、和樹形)組成的一個表，在此表中進行查找操作。2．對查找表的操作(1)

查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；(2)

檢索某個“特定的”數(shù)據(jù)元素的各種屬性；(3)

在查找表中插入一個數(shù)據(jù)元素；(4)

從查找表中刪除某個數(shù)據(jù)元素。第九章查找

3．靜態(tài)查找表只作前兩種稱為“查找”操作的查找表為靜態(tài)查找表。靜態(tài)查找表中表的內容不變。

4．動態(tài)查找表在查找過程中同時插入表中不存在的數(shù)據(jù)元素或從查找表中刪除已存在的某個數(shù)據(jù)元素，此類表為動態(tài)查找表。表中的內容不斷變化。

5．關鍵字數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值，用它可以標識一個數(shù)據(jù)元素(或記錄)。

6．主關鍵字唯一標識一個記錄的關鍵字。第九章查找7．次關鍵字識別若干記錄的關鍵字。

8．查找

根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的記錄或數(shù)據(jù)元素。9．查找成功表中存在關鍵字等于給定值的記錄，查找結果為給出記錄的信息或該記錄在表中的位置。10．查找不成功表中不存在關鍵字等于給定值的記錄，查找結果為空記錄或空指針。

11．性能分析衡量一個算法好壞的量度有三條：時間復雜度、空間復雜度、算法其它性能。查找算法中的基本操作是“將記錄的關鍵字和給定值進行比較”，以“其關鍵字和給定值進行比較的次數(shù)的平均值”為衡量查找算法好壞的時間標準。

平均查找長度定義為確定記錄在查找表中的位置，把查找過程中對關鍵字需要執(zhí)行的比較次數(shù)稱為平均查找長度。平均查找長度為存儲結構中數(shù)據(jù)對象總數(shù)n的函數(shù)：ASL=∑PiCi(1≤i≤n)其中：Pi為查找表中第i個記錄的概率，∑Pi=1Ci為找到表中其關鍵字與給定值相等的第i個記錄時，關鍵字和給定值已比較的次數(shù)。Ci隨查找過程不同而不同。Ci取決于所查找記錄在表中的位置。

一、順序表的查找

9.1靜態(tài)查找表

9.1靜態(tài)查找表

一、順序表的查找二、有序表的查找三、索引順序表的查找

一、順序表的查找

9.1靜態(tài)查找表在線性表進行的查找。用順序表或線性鏈表表示查找表。1．表的存儲結構typedef{Elemtype*elem//數(shù)據(jù)元素存儲空間基址Intlength//表的長度}SSTable;2．定義從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功；反之，若直到第一個記錄，其關鍵字和給定的值比較都不等，則查找不成功。3．算法intSearch_Seq(SStableST,Keytypekey){

ST.elem[0].key=key//ST.elem[0].key為“哨兵”for(i=ST.length；ST.elem[i].key！=key);--i)returni;}

一、順序表的查找

9.1靜態(tài)查找表4．性能分析對于含有n個記錄的表，查找成功時的平均查找長度為ASL=∑PiCi(1≤i≤n)一般Ci=n-i+1設每個記錄查找的概率相等，即Pi=1/nn為表的長度則ASLss=1/n*∑(n-i+1)=(n+1)/2

一、順序表的查找

9.1靜態(tài)查找表上述定義是忽略查找不成功的概率，否則，查找算法的平均查找長度應為查找成功的平均查找長度和查找不成功的平均查找長度之和。(假設成功與不成功的概率相同，對每個記錄查找的概率也相同，此時對任一記錄查找的概率為1/(2n)，即Pi=1/(2n))（查找不成功需要比較n+1次）ASLss=1/2n*∑(n-i+1)+∑n(n+1)/2n=1/2n*∑(n-i+1)+(n+1)/2=3(n+1)/4查找成功的平均查找長度

查找不成功的平均查找長度

二、有序表的查找所謂有序表是指表中數(shù)據(jù)元素(或記錄)是有序的(遞增、遞減)，在有序表中進行查找所用的方法主要是折半查找(二分法查找)。1．折半查找方法在所查找的區(qū)間范圍內，以處于區(qū)間中間位置記錄的關鍵字和給定值比較，若相等，則查找成功；若不等，則縮小范圍在新的區(qū)間繼續(xù)折半查找。新的區(qū)間是通過判斷關鍵字和給定值的大小，若關鍵字值比給定值小，則新的區(qū)間為小于中間位置的區(qū)間；否則為大于中間位置的區(qū)間。直至新的區(qū)間中間位置的記錄的關鍵字等于給定值或者查找區(qū)間的大小小于零時(找查不成功)為止。

9.1靜態(tài)查找表123

456

789101121

051319

2137566475808890lowhighmid=(low+high)/2high=mid-1midLow=mid+1mid查找成功，返回mid值。比較次數(shù)為3次。2.折半查找的算法采用順序存儲結構。IntSeardh_Bin(SSTableST，KeyTypekey){low=1;high=ST.length；//置區(qū)間初值while(low<=high){mid=(low+high)/2;//取不大于(low+high)/2的值if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)high=mid-1;elselow=mid+1;}

return0;}

二、有序表的查找

9.1靜態(tài)查找表3.折半查找的性能分析如下11個數(shù)：1234567891011051319213756647580889034234134234查找時，第6位置的56需比較1次；第3和9位置的19和80需比較2次；第1、4、7和10位置上的數(shù)據(jù)需比較3次；第2、5、8和11位置的數(shù)據(jù)需比較4次。(1)

判定樹

用二叉樹描述折半查找的過程，稱此二叉樹為判定樹。

二、有序表的查找

9.1靜態(tài)查找表假定有序表中有n個記錄，這n個記錄作為二叉判定樹的n個結點。根結點為有序表的中間結點即比較一次的關鍵字K(low+high)/2，左右子樹分別為K<K(low+high)/2和K>K(low+high)/2的子過程，這是一個遞歸構造過程。

二、有序表的查找

9.1靜態(tài)查找表分析：一奧個折吳半成斧功查甚找，撒正好起對應衡判定控樹的熊一個析內部翅結點他(樹僵中的款結點牛)，關鍵白字的塔查找嫂次數(shù)為從翠根結藝點到吸該結灑點的路徑榜長度月加1或該創(chuàng)結點撒在判定虹樹的賠層數(shù)。如顫若查怖找2嘆1所窯走的路蔽徑為跑從根敗結點塌6到戲結點梨4，嫁所走液路徑裂長度郊為2調，結掌點4聚所在狐的層堵數(shù)為港3。結論津：折半史查找槳法在查找雹成功時進反行比較福的次蹈數(shù)最匠多不吩超過樹的迷深度，即lo遞g2n+1。二、心有序聲表的常查找9.哪1靜態(tài)查找欺表(2嬸)組折半件查找彼的平只均查遠找長跪度折半炮查找戶時查找篇不成裂功的過蠟程就喚是一殖條從蘆根結擋點到虹外部味結點礙的路炮徑，比較款的次乎數(shù)為從表根結射點到碼外部皺結點揚的路徑頸長度圾或內趕部結政點的治個數(shù)。因始此不成遙功查飾找的苦比較蛇次數(shù)最多以也不碌超過lo遮g2n+1。二、例有序蠻表的萌查找內部貨結點外部畜結點9.品1靜態(tài)查找膽表二、姿有序訪表的跡查找為了告討論百方便招，假趙設有省序表頁的長擴度n=觀2h-1籠(反之h=木lo宰g2(n嶼+1鑼))廳,則描尿述折刃半查墾找的猴判定賭樹是屆深度賠為h的滿裙二叉聯(lián)樹；慨另假孩設每李個記仙錄的挺查找苦概率醉相等偉=1揚/n;則折真半查針找的平均蜜查找際長度恭為：AS科Lbs=∑PiCi(i從1高到n)=1艱/n罷*∑敗j*協(xié)2j-健1(j從1牌到h)=nn+著1lo妹g2(n若+1客)-須1折半潑查找禿的效帳率比捕順序志查找研高，術但只仗適用殲于有序拴表且各順序凡存儲綱結構。9.語1靜態(tài)查找珍表三、索引練順序饑表的呀查找以索倆引順朋序表鍵表示倦靜態(tài)矮查找塊表，抄則用甜分塊存查找化來實廁現(xiàn)，帥又稱索引團順序役查找，性濫能介省于順赤序查肢找和奴折半段查找裁之間劈燕。1．螺索引斯順序墻表的線結構(1承)線性砌表：表欺中的濃結點尤被分場為若償干塊蒸，每宮一塊景中的悉結點月是任真意存煮放的利，塊營與塊最之間銅的結裂點關某鍵字筍是有搖序的繁，稱謠為分扒塊有鍬序。(2汁)索引醫(yī)表：將絲式線性擠表分杜成若皇干塊凱構成假一個追索引北表，射每一蜻塊是義線性層表中肚的一繼個子異表，虹對應司索引點表的楊一個斧索引族項，索引徐表按化關鍵土字有餓序。索引木項關鍵頭字項異：子表星內最桿大關喉鍵字指針回項：子表啄的第簡一個構記錄則在表袋中的自位置9.形1靜態(tài)查找陷表2248861713索引嶄表2212138920334244382448605874865312雖3公4右5管678集9脆10微1定1桃1醬21314雞1拐5變16獎17最大齊關鍵胸字擊起始悉地址三、索引旅順序互表的酒查找線性額表9.婆1靜態(tài)查找棉表2.作分塊枝查找敞的步鋸驟方驕法第一幼步：炮確定荒要查沾找的雄記錄受在表埋中的夫哪一看塊，榜在索在引表中采脆用順序才查找或折半遍查找。第二杯步：尊在確馬定的旬塊中距查找假記錄娃，由過于塊薦中的貧記錄旬是任意排簡列的躲，只嫩能采飾用順序麥查找。3.陣性能左分析平均謠查找料長度殿為：AS收Lbs=Lb+Lw將長聾度為n的表騾均勻醫(yī)分成b塊，宅每塊盛含s個記監(jiān)錄，b=列n/制s，設查瞧找概批率相逼等，兄分別乓為1港/b，馳1/杰s。則順杯序查可找所霸在塊致平均媽查找活長度她為:三、哀索引董順序芹表的授查找9.寒1靜態(tài)查找教表(2往)AS劃Lbs≈l稿og2(n裁/s塊+1批)+注s/僻2即(折半袍查找更確定這所在奔塊)9.鹽1儀靜質態(tài)查扛找表例：建立煉一棵趴具有赴13捐個結迫點的嶼判定鬧樹，尸并求扭其成筋功查紡找和萌不成堤功查塘找的佳平均克查找垃長度仔各為踏多少秋。9.膛1揚靜典態(tài)查均找表AS斤L成功=1姻/1眨3（莫1+紀2*排2+圣3*近4+顯4*薪6）逐=4祥1/播13AS白L失敗=1及/1灶4（抬3*額2+爬4*紋12栗）=既54倉/1笨4解：鈴用結栽點的蘇序號有表示夕結點含，構荒造的就判定津樹是：9.善2姿動燈態(tài)查鍛找表一、恭二叉柱排序謝樹(丘二叉曠查找母樹)二、雄平衡沾二叉此樹三、B-樹和B+樹1．法動態(tài)企查找紡表的幕特點表結騾構本割身是去在查匪找過躲程中至動態(tài)盲生成緣瑞的，產(chǎn)即對逼于給旋定值ke采y，若表友中存在其關鍵勁字等襖于ke歉y的記價錄，則查找典成功，否箱則插入氣關鍵辱字等于ke費y的記舍錄。2．鑰動態(tài)責查找雪表的法抽象北數(shù)據(jù)坑類型居定義略。3．立動態(tài)檢查找補表主膏要以樹結屯構表示療實現(xiàn)招。9.零2被動斯態(tài)查聚找表1.泛二嘗叉排倦序樹魔定義二叉胸排序凱樹(Bi仇na汪ry報S吧or辭t填Tr羞ee使)或者型是一叼棵空沫樹；或者毯是具晌有下漆列性桑質的順二叉私樹：若它儲的左林子樹昌不空柏，則左子術樹上所龍有的崖結點缸的值水均小于呼它的燥根結妥點的檔值；若它敘的右千子樹辣不空矩，則右子摸樹上所紫有的滋結點泄的值國均大于懇它的私根結我點的皆值；它的左、課右子哨樹也莫分別煮為二西叉排胃序樹。一、賣二叉澤排序華樹(坑二叉速查找酒樹)9.菠2動態(tài)遠查找眠表一、環(huán)二叉膚排序旨樹(福二叉浮查找李樹)9.億2動態(tài)淺查找島表2.蠻二體叉排痛序樹滴的查警找過繩程當二銳叉排鹽序樹蘿不空旗時，箏先將赴給定生值和瞎根結乏點的擴關鍵扒字比燥較，攀若相樸等，恨則查驚找成繼功；否則羞，3.斧二叉蓬排序正樹的肥存儲無結構通常將采用二叉財鏈表作為顧二叉往排序優(yōu)樹的倦存儲惜結構糕。一、抵二叉杰排序瘋樹(艦二叉壤查找吧樹)若給值定值抹小于械根結悶點的酷關鍵臺字，寒則在旋左子而樹上棋繼續(xù)封進行游查找房誠；若給夫定值脾大于賣根結業(yè)點的夸關鍵參字，晌則在扶右子哪樹上誕繼續(xù)發(fā)進行策查找型。9.刊2動態(tài)藏查找雙表4.趙二叉聾排序叫樹的都查找宇算法這是雹一個位遞歸啄查找祥過程熟：Bi織Tr益ee冬S腥ea狂rc餓hB慢ST(Bi悼Tr汗eeT,Ke毒yT日yp支eke靠y){i王f(駱(!流T)招||變(k思ey野==沙T-方>d勸at次a.嬸ke譯y)魔)re扇tu祝rn分(T朝);el界se銅i晌f(苗ke傾y<蓄T-哀>d去at灑a.趟ke擦y)re夠tu借rn也(Se暴ar靠ch稈BS凈T(T小->lc柄hi吸ld,k唐ey宋))牙;el盲sere搭tu粱rn立(Se使ar美ch受BS局T(T到->rc鄉(xiāng)豐hi易ld,k唱ey局));}一、停二叉勤排序名樹(怕二叉雜查找侵樹)9.月2動態(tài)籃查找您表1．遺二叉劍排序轉樹的臥插入這是述一個漠二叉優(yōu)排序眠樹的傲動態(tài)騰構造絨過程份。(1指)篇插入碑算法二叉廈排序交樹是守一種歡動態(tài)裕樹表躲。特點菌：樹的伸結構陰通常余不是坦一次民生成姨的，議而是晶在查跟找過腰程中岔，當樹津中不往存在叢關鍵俱字等桌于給躺定值痰的結霧點時疏再進落行插管入。新插該入的床結點起一定誕是一棍個新添必加的葉子結點，并乘且是透查找狹不成紡功時總查找救路徑蛇上訪堪問的惕最后謀一個訴結點孔的左鉤孩子形或右粱孩子覆結點獵。二、含二叉縮慧排序傷樹的挽插入堂和刪膝除9.樓2動態(tài)辮查找捐表St湯at染usSe拔ar炕ch硬BS蛾T(Bi受Tr窩eeT,Ke怨yT膝yp每eke那y,Bi刊Tr造eef,Bi船Tr悔ee&p){史//查找廟不成誰功，p指向渡查找請路徑荷上訪井問的綱最后財一個斥結點if腎(!店T){p母=f預;r舟et撐ur透n偶FA史LS兄E;繩}el搖se授i摸f蛋(k河ey真==炭T-棵>d浪at區(qū)a.暫ke野y)躬{p庸=T析;配re環(huán)tu譜rn秒T薄RU籌E;偶}種//查找竟成功尿，p指向漿找到計的結框點el商se梁i搞f害(k串ey仙<T形->套da坊ta五.k止ey和)re拳tu碎rnSe堤ar癥ch厲BS膜T(T-拖>lc椒hi罪ld,ke永y,T,p);el鴨se參r始et礦ur乎nSe憐ar軋ch謊BS露T(T-幻玉>rc滔hi耕ld,ke膝y,T,p);}St好at控us吼I蒙ns納er浙t_蟲BS普T(Bi倒Tr公ee&T顫,El攔em增Ty送pee){廊if騎(!Se危ar伙ch賊BS截T(T,e.敘ke慘y,NU挎LL摘,p))糧/林/查找麻不成染功{s=割(Bi粉Tr更ee*)ma逝ll蠅oc(si劍ze艷of(Bi草TN干od柔e))蔽;s-繪>d肌at良a=未e.嚼ke映y;市s-慎>lc莫hi船ld=s遠->rc悶hi麥ld=N饞UL棕L;if慎(!尋p)示T紅=s途;el速se盛i芽f馳(e告.k姻ey斃<p訪->蘇da煎ta鳥.k孕ey羞)川p水->lc杰hi驗ld=s級;el阻se檔p-桃>rc侮hi踐ld=s尾;re正tu擠rn偉T獅RU椅E;普}el宇se忽r及et秤ur改n訓FA改LS勺E;}二、跪二叉憶排序嚇樹的慈插入咬和刪船除9.隆2動態(tài)根查找猜表(2劈燕)二蒜叉排袖序樹濃的構關造特槍點若從仙空樹黃出發(fā)只，經(jīng)熔過一華系列剖的查套找插肚入操葡作之氧后，傘可生腳成一待棵二警叉排似序樹逃。中序夕遍歷摸二叉滴排序初樹可得搬到一型個關鍵仙字有加序的躁序列。構造頑樹的獸過程格就是禮一個百對無爬序序驕列進盡行排掘序的澇過程。一湯個無欄序序績列通泉過構運造一視棵二背叉排慎序樹農(nóng)而變暢成一芝個有紫序序無列。在二酷叉排踐序樹菠上插品入一更個記識錄或嗽結點禮，不塔需要錘移動混其它野記錄圈或結榮點。二、蕉二叉汗排序稀樹的販插入則和刪蹦除9.顧2動態(tài)疫查找渡表例：劈燕設查第找的鈔關鍵恭字序擾列{漂45就，2富4，頑53煎，4暢5，魄12暑，2棕4，每90摧}，耐則生愉成二即叉排藍序樹奮的過鼓程如悟圖所掉示。二、幅二叉創(chuàng)排序補樹的紛插入夏和刪苦除9.音2動態(tài)選查找幼表2．擺在二括叉排胃序樹象上刪批除一鳳個結埋點對于炸在二釣叉排乘序樹登上進佳行一捉個結慢點的引刪除魚，由蠻于是津在一旋個有條序序盯列中廚刪除矛，要附求刪幣除結睡點后況，仍聯(lián)保持胞二叉橫排序步樹的賢結構損特點缺不變鐘。(1勾)方埋法設被既刪除僑的結薯點為否*p，其雙熔親結墨點為的*f，設*p為*f的左兔孩子璃。三種局情況淚：二、棚二叉互排序碗樹的警插入影和刪抗除9.壯2動態(tài)疏查找拼表若*p為葉造子結朱點，鳳即PL和PR均為煌空樹軍。只陸需修饅改其襯雙親載結點搖的指礎針即酒可，犯如圖標(a)萌。若*p結點斯只有讀左子造樹PL或右痛子樹PR蹄，此時制只要借令PL或PR直接持成為昨其雙耍親結席點*f的左鴿子樹循即可掏，如勤圖(b)翼。二、復二叉吐排序紡樹的做插入洞和刪變除9.信2動態(tài)燥查找淡表若*p結點攀的左間子樹盾和右蹈子樹駐均不朵空。有兩貍種處舞理方皆法。炮以下音圖為應例說炒明。圖(a)是在濱刪除幟*p結點謝之前殺，中勢序遍蟻歷二獻叉樹墨得到好的序秀列為播{…殘.CLC…墻QLQSLSPPRF…飄}，在刪抹除*p結點振之后波，要反保持叨其它誓元素南之間陷的相稻對位棍置不質變。二、骨二叉膽排序洗樹的胃插入?yún)f(xié)和刪拍除9.厘2動態(tài)火查找灰表方法斤一：燥令*p的左概子樹皺為*f的左鑄子樹剪，而謀*p的右系子樹互為*s的右繡子樹抖，如蛋圖(b)夏；方法嗓二：參令*p的直約接前溝驅(廁或直價接后弱繼)折替代誓*p，然后竭從二寒叉排魂序樹格中刪撒去它掃的直成接前綁驅(米或直形接后捐繼)器。如慮圖(c)當以販直接抬前驅利*s代替型*p時，炒由于戚*s只有懲左子寬樹SL，則在突刪去甘*s之后雄，只逼要令SL為*s的雙滑親*q的右棵子樹竊即可臣。二、籍二叉踏排序忠樹的蔥插入顯和刪揉除9.寬2動態(tài)輕查找川表(2艙)算跡法St凱at摟usDe反le肥te都BS衡T(Bi勻Tr怎ee&T綱,Ke冒yT暑yp寨eke話y){i蜂f(綱!T遲)re畢tu啄rn嘩F鵲AL麻SE;el狼se{i碧f防(k躁ey為==性T-緊>d統(tǒng)at化a.毅ke殊y)re蔬tu橫rn如D隱el層et烏e(患T);el梢se誕i厘f(料ke販y<冶T-誰>d穿at歪a.錯ke腐y)re欠tu極rnDe請le斧te液BS需T(T關->lc堆hi立ld,k炮ey午);el臉se修r(nóng)溫et群ur統(tǒng)nDe揉l(xiāng)e魯te菌BS廚T(T藍->rc陪hi跌ld,k掀ey閣);re亮tu敢rn穴T偶RU默E;}}二、尋二叉漁排序袖樹的喘插入慈和刪戴除9.蛾2動態(tài)塔查找偉表Vo藥id咬D壇el焦et正e(Bi爹Tr楚ee&p尚){夢if吸(!展p-朱>rc酒hi緣瑞ld)//右子同樹空搏則只廳需重雖接它論的左結子樹{q=攤p;扁p=禁p-薦>lc艇hi喇ld;f燙re噴e(浩q)掩;}el絡se揪i任f(合!p鴉->lc還hi蝴ld)//左子再樹空程只需鍋重接猛它的軍右子熊樹{q=斤p;服p=餓p-宰>rc執(zhí)hi科ld;f僅re伍e(欣q)堤;}el座se{q備=p盆;s鋪=p趨->lc撒hi旋ld;wh炎il鏈e(磨s-丹>rc種hi偶ld){q脊=s孤;s窮=s粘->rc扇hi宿ld;}//轉左駛，然鄉(xiāng)豐后向廟右到級盡頭p-妙>d伯a(chǎn)t歷a=款s-綁>d僻at拒a;//央s指向才被刪縫結點辭的“椒前驅”if嘗(q鐘!=殖p)剪q創(chuàng)->rc令hi社ld=s叔->lc撓hi且ld;//重接尺*q的右珠子樹el促se芒q違->lc紛hi險ld=s獎->lc忌hi吊ld;//重接銅*q的左清子樹de存le她te景s池;}端}二、騙二叉獎排序董樹的孤插入憤和刪蠶除9.炮2動態(tài)孤查找寸表三、胳二叉嚇排序源樹的焰查找榜分析分析瓣在二能叉排婆序樹民上查績找其妙關鍵卡字等螺于給約定值查的結津點的亞過程雖，恰是腫走了梁一條撕從根旅結點逼到該鑼結點中的路畢徑的煉過程窩，和封給定女值比雕較的櫻次數(shù)竊等于窗路徑菠長度萄加1肢(或職結點折所在跑層數(shù)則)，與折稱半查偏找相嶄類似傘。折半蛙查找后長度綱為n的表妖的判喬定樹優(yōu)是唯斥一的溜；而珠含有n個結縮慧點的悄二叉適排序仁樹卻傳不唯殿一，佩取決瘦于關鍵母字的剩序列。因拳此，含有n個結皆點的識二叉深排序削樹的撐平均盯查找匹長度岸和樹就的形疏態(tài)有咳關。由分析牛得知：二圈叉排迎序樹疑的平宜均查車找長與度最差學情況閉與順駕序表繩相同渠(關賞鍵字叢有序數(shù)時)；最好慰情況悔與折壺半查狐找相纏同。瘋但平殲均查啟找長滋度是艱和lo助gN等數(shù)量雪級的絮。9.吸2動態(tài)就查找蹲表如：嬸含有制相同襖的關抓鍵字景的兩逝個序柴列。序列輸一：膊45襪，2篇4，舌53爹，1醬2，吉37不，9害4序列婆二：覺12袖，2藍4，昌37陪，4汽5，存53秤，9括4452453123794122437455394序列牌一O(lo廳gN)序列鴨二O(點n)1．楚平衡柴二叉注樹的刻定義平衡投二叉虹樹(Ba等la拴nc額ed銷B狼in莊ar嗓y童Tr隱ee或He說ig愉ht球-B港al鄭an嬸ce慈d委Tr及ee)又稱AV奴L樹。它或童者是一棵轉空樹；或者具有刺下列喬性質妨的二崖叉樹：它的博左右鞋子樹唇都是兇平衡堅二叉拖樹，惡且左選子樹口和右嘆子樹啞的深度百之差練的絕戶對值嘴不超誓過1。2．束平衡截因子靠(BF閑)結點依的平魄衡因閘子為姓該結愁點的登左子暈樹深逆度減拔去它鏟的右杏子樹抬深度睜。平衡有二叉陡樹的掀平衡陪因子紐奉為-描1、后0和調1，巨即絕馳對值業(yè)小于穗等于炒1。閱否則恩該二屑叉樹陳為不緣瑞平衡財二叉瞞樹。四、弄平衡背二叉黎樹9.慌2動態(tài)紅查找奇表四、訊平衡鏈二叉淡樹不平面衡二熄叉樹平衡撇二叉訓樹9.帆2動態(tài)擇查找秒表四、房誠平衡棒二叉木樹2．催平衡耳二叉你樹的宏構成例：很將關纏鍵字留序列許為{來13榨,2滅4,寨37挪,9題0,扁53鉤}構諒成二盞叉排尚序樹趨和平閱衡二邊叉樹色。9.遠2動態(tài)隱查找夫表四、寸平衡面二叉糊樹{1丘3,膊24榨,3襲7,誘90聰,5鑼3}9.圓2動態(tài)訊查找微表(1匙)在二你叉排噴序樹錢上插紐奉入結皮點或妥構造梅時，菜二叉接排序裹樹結具點的本平衡道因子爆滿足筋絕對朱值不踐超過口1的度條件墓時，蓋這棵腐二叉買排序晚樹就艦是平之衡二廈叉樹晝，構朗成方侍法同拆二叉疏排序糊樹相睜同，底無其驢它變悶化。(2完)若在袋插入貪結點累時，恢使結付點的蟲平衡券因子湖絕對襖值出敢現(xiàn)大智于1稱的時韻候，貪這時須二叉季樹失去普了平蒸衡，需廢要對應二叉棍排序蘇樹進蕩行調剖整，估即“旋轉絹”以該保持余二叉料排序謎樹為辱平衡公二叉超樹。四、挖平衡瓦二叉描樹9.柄2動態(tài)尾查找努表(3屈)對失災去平撿衡的疏二叉驅排序渾樹的調整可規(guī)律一般梳情況敢下，撫假設債由于糞在二初叉排選序樹書上插駕入結盒點而柿失去挽平衡薄的最險小子侮樹根販結點勤的指同針為a(即a是離扔插入絕結點垮最近校，且瀉平衡演因子悠絕對斃值超薪過1摩的祖媽先結鎮(zhèn)點)兇，則鹽失去溫平衡臣后進單行調唱整的傾規(guī)律脊可歸盛納為描下列內四種不情況承：a.單向淹右旋鮮平衡原處理有(LL型)b.單向擋左旋塵平衡濫處理叉(RR型)c.雙向蔑旋轉潤(先茫左后俊右)缸平衡心處理究(LR型)d.雙向煩旋轉辛(先紗右后釘左)疤平衡覽處理罵(RL型)四、秋平衡海二叉作樹9.吹2動態(tài)稈查找把表單向隨右旋嬸平衡低處理減(LL型)在a的左子疲樹的澤左子御樹上插脫入結暫點，鋤使得a的平衡醉因子辯由1紋增至且2，勝將a的左夠孩子b提升子為子主樹的根結訂點，a作為b的右子樹，b原來倍的右子語樹作為a的左子引樹。四、杰平衡瞇二叉芳樹9.唯2動態(tài)溝查找可表單向值左旋次平衡躺處理縮慧(RR型)在a的右子憲樹的烤右子節(jié)樹上插剛入結把點，耍使得a的平衡嶄因子擺由-造1減出至-騾2，父將a的右須孩子b提升垮為子稈樹的根結匹點，a作為b的左子盜樹，b原來陳的左子姐樹作為a的右子四樹。四、臉平衡裁二叉你樹9.賽2動態(tài)拌查找層表雙向劈燕旋轉耗(先趴左后盟右)瓣平衡碎處理觸(LR型)在a的左子丙樹的搭右子熟樹上插變入結駱點，淘使得a的平衡快因子芳由1占增至就2，蜘將a的左籃孩子支的右裝孩子br提升談為子免樹的孝根結思點，b、轟a作為br的左、揮右子饅樹，br原來遮的左、艇右子束樹分別衫作為b的右子銳樹和a的左子囑樹。四、厭平衡愚二叉誰樹9.鞏2動態(tài)雅查找酸表雙向壯旋轉爪(先獵右后旗左)倉平衡自處理找(RL型)在a的右子饑樹的看左子槐樹上插嫩入結何點，幣使得a的平衡近因子霞由-可1減困至-刪2，臨將a的右奔孩子指的左擁孩子bl提升術為子婆樹的列根結抵點，a、蛇b作為bl的左、艷右子底樹，bl原來豆的左、腹右子顆樹分別違作為a的右子布樹和b的左子施樹。四、屢平衡惰二叉卸樹9.熊2動態(tài)溝查找次表(4嗎)旋轉乏操作吳的正傭確性蹤蝶容易嶄由“闊保持暖二叉講排序灣樹的厘特性列：中慕序遍翻歷所袍得關道鍵字拳序列巴自小飽至大煙有序權”證望明之罪。(5卸)經(jīng)過族平衡巴旋轉旨處理帆之后席，以糟*b或*br(*bl)為根聲的新班子樹狠為平氣衡二升叉樹靜，而換且它丸的深群度和柔插入雁之前帶以駁*a為根啦的子追樹相玻同。獎因此甜，當衰平衡商二叉配排序火樹因竹插入蛛結點疾而失迎去平瓦衡時蛾，僅犧需對痛最小物不平骨衡子眠樹進確行平膠衡旋餃轉處錄理即字可。遙因為黎經(jīng)過侄旋轉森處理陜之后棵的子朱樹深滾度和揭插入秩之前榴相同球，因陪而不槽影響月插入籌路徑湯上所裝有祖委先結傲點的由平衡沸度。四、萄平衡李二叉斧樹9.族2動態(tài)諷查找抖表3．蔬在AV剖L樹BB較ST上插柱入一提個新肥的數(shù)俯據(jù)元跌素e的遞貫歸算號法(1庫)若BB銅ST為空逆樹，能則插室入一質個數(shù)煙據(jù)元緒素為e的新燈結點齒作為BB茅ST的根物結點種，樹霸的深飛度增遮1；(2許)若e的關未鍵字敵和BB財ST的根折結點祝的關日鍵字濫相等每，則廢不進訊行插屑入；(3雁)若e的關狗鍵字販小于BB編ST的根偽結點皆的關即鍵字茶，而嬌且在BB答ST的左鴉子樹傻中不躬存在網(wǎng)和e相同偵關鍵余字的糞結點常，則架將e插入腐在BB持ST的左軟子樹尿上，拍并且維當插莖入之昆后的掀左子躍樹深活度增枯加(榴+1護)時標，視帳如下千情況仆處理蔬：四、漢平衡情二叉常樹9.擦2動態(tài)釘查找非表BB緊ST的根垃結點仰的BF為-亦1：溉則將雹根結鐵點的BF更改蘿為0汽，BB否ST的深錄度不況變，欣如下五圖(a)所示難。BB乓ST的根舊結點娘的BF為0繩：則協(xié)將根比結點盈的BF更改供為1獎，BB萬ST的深京度增地1，肌如下餐圖(b)所示米。(a)(b萄)四、雷平衡廳二叉鍬樹9.允2動態(tài)寫查找福表c)BB犯ST的根兄結點廊的BF為1投，分仇兩種殘情況膏：BB站ST的左絨子樹際根結鏟點的BF為1傷：則遇需進浙行單凡向右廉旋平態(tài)衡處瘡理，改處理恒之后氣，根妨結點壺和其卡右子健樹根帳結點傲的BF改為摔0，案樹的鑼深度局不變丈，如距圖(c河)。四、曉平衡春二叉乖樹9.峰2動態(tài)著查找館表BB聽ST的左售子樹繞根結隨點的BF為-脹1：暴則需龜進行霜先向諒左、牲后向議右旋獻轉平屑衡處暴理，聾處理茅之后而，修沿改根詠結點扮和其追左、億右子鞠樹根臟結點遼的BF否，樹的鑒深度月不變很。四、掩平衡完二叉轎樹9.使2動態(tài)持查找過表(4必)若e的關儀鍵字好大于BB撈ST的根疼結點慮的關營鍵字姻，而笛且在BB驢ST的右福子樹給中不盛存在洪和e有相在同關隱鍵字貝的結巖點，蘭則將e插入頑在BB翅ST的右撒子樹頸上，盜并且扁當插欄入之恐后的傭右子咱樹深播度增紡加(濕+1魄)時欄，分惹別就背不同聞情況州處理回之，蓄與(類3)練類似。四、箏平衡傾二叉券樹9.氣2動態(tài)綁查找閑表4．平響衡樹妻查找兆的分捆析同排夠序樹齡，在綢查找揮過程跟中和災給定徹值進學行比私較的滋關鍵矛字個業(yè)數(shù)不背超過側樹的才深度降。我們叔考慮興最壞誤情況既，既n個關撐鍵字斥平衡企樹的蛋最大豪深度航，為柔此我繪們需城要知倍道深煉度為h的平酷衡樹淺所具沫有的島最少薯結點礎數(shù)．設深謀度為h的平罪衡二半叉樹枯的最訴少節(jié)辣點為Nh。已知雀：N0=0，N1=1，N2=2，則Nh=Nh-富1+Nh-殲2+1遷(遞歸)，和次斐波示那契慮序列恥極為陳相似輛。當h≥籃0時，則含連有n個關病鍵字候的平竭衡樹診的最雞大深線度。四、賺平衡獎二叉亞樹9.販2動態(tài)調查找貪表例：敵設一優(yōu)組記噸錄的痛關鍵鞭字按拜下列符次序釋進行昏插入{4盼，5不，7沸，2蟲，1拳，3車，6信}，生成冷一棵AV趙L樹。應試描摟述其喂生成惡及調奮整成左平衡敞二叉像樹的類過程炸，并洞指明私該步務驟是承屬于佳什么迫調整揪平衡蒙方式于的基令本類抓型。四、帝平衡出二叉壓樹9.銅2動態(tài)穗查找墻表四、擦平衡孤二叉壩樹9.房誠2動態(tài)掘查找劣表四、兵平衡輛二叉保樹9.躺2動態(tài)付查找卡表1．B-樹的洞定義前面盼介紹遍的查友找法臭，僅密適用疫于計暮算機神內存險中的蜜文件怎或表廣，統(tǒng)薪稱為透內查賽找法采，而稼對外答存上晨文件鄙的查泡找稱塵為外僵查找交法。前面緩介紹帆的方斜法也句可應跳用于問磁盤罩文件宏，例鼻如一弓個磁范盤文功件包獨含n個記據(jù)錄，n=鄭106，且該擁文件征表示竊成一逝棵二踐叉樹泡形，絮那么蹤蝶欲從基該文藝件中笨查找占包含妙某一濾給定楊關鍵模字的扎記錄漲平均嗽來說帖大約巾要做lo帳g2n=銀lo癥g2106≈2尿0次磁狠盤的仁存取蕩操作鼠。因竄為對奏磁盤紡存取銜的速丈度比遍內存添中的隨存取萄速度帳慢得核多，級因此爬當n較大踢時，泉用二猾叉樹止形來鏟表示青文件怎是行來不通瓣的。豆對于忽外存慕上的進文件扔而言紹，減得少查敘找過吉程中隱磁盤朱存取接次數(shù)填，是臘很必動要的襪，B-樹就早是解冷決此評類問邊題提蘆出的溫。五、B-樹和B+樹9.漆2動態(tài)旦查找湖表B-樹是謝一種盞平衡冷的多店路查揉找樹胃，是殖一類掩適于射外查義找的六數(shù)據(jù)圓結構失。m階的B-樹，瓜或為折空樹善，或脂為滿標足下吩列特逃性的m叉樹股：(1慕)樹中懂每個菌結點顧至多有m棵子莊樹；(2嚼)若根耳結點攻不是牌葉子爺結點，則礦至少扭有兩棵子衛(wèi)樹；(3擦)除根尸之外餐的所蒼有非終奸端結遷點至少語有m/紐奉2棵子乖樹；(4兆)所有非終催端結窄點具有n(m/刑2-漂1≤n館≤m資-1)個關鍵寇字域和n+近1個指針啊項，指磨向該鋼結點貍的n+愿1棵子殲樹；坡結點枝包含塘下列吉信息恩數(shù)據(jù)(n,菜A0,K1,A1,K2,A2,…開…Kn,An)其中息：Ki為關謙鍵字鋼，且Ki≤Ki+1，Ai為指只向子誕樹根樓結點曠的指餡針，襪且KAi-1≤Ki≤KAi，。(5種)所有芹葉子洋結點并都出傍現(xiàn)在或同一長層次疾上，栗且不婆帶信政息，忘僅表懇示查恒找失飼敗(門外部待結點茄)。五、B-樹和B+樹9.迅2動態(tài)勉查找鋤表下圖臣所示餅的是互一棵物4階穗的B-樹(刃又稱2-課4樹，非限終端宵結點伐關鍵犬字個倉數(shù)至微多為冒3，胖至少廳為1亞，子窯樹個婆數(shù)最坦少為共2，膊最多扭為4堡)五、B-樹和B+樹9.豪2動態(tài)叮查找批表2．B-樹上粥的查阻找在B-樹上轟的查劑找過胳程和墊二叉券排序碑樹的釋查找請類似缺。首擴先在估根結鑒點所賤包含糕的關胞鍵字襲中查掃找給減定的辜關鍵奸字。減若找斗到，金則查膏找成牲功；阻否則勞，確戀定待徐查關徐鍵字抓所在寨的子嶼樹并擁在其偶上查竄找，化直到右查找狼成功狹或查批找不游成功肢(失可配結沈點F)專。在B-樹上賄進行北查找白的過湖程是慨一個現(xiàn)順指豪針查素找結鄭點和篇在結鳥點的鄰關鍵吊字中陶進行嗓查找苗交叉攻進行該的過禿程名。五、B-樹和B+樹9.當2動態(tài)鄉(xiāng)豐查找儲表3．B-樹查情找分由析從上狹面的野分析殘得知漏，在B-樹上怒進行榴查找尼包含盛兩種單基本存操作藏：(1)紗在B-樹中題找結然點：性在磁荷盤上廁進行軍。(2描)項在結憂點中紐奉找關頁鍵字閘：在條內存寧中進罰行的牽。對(稱1)電的查脫找效豈率決舒定了B-樹的門查找覆效率不，取澇決于添待查參關鍵粥字所胞在結門點在B-樹上刃的層菌次數(shù)隔，這吳是決怪定B-樹查臺找效煉率的迅首要停因素碗?？紤]磁最壞窗情況員，即苦待查武結點務在B-樹上險的最岡大層著次上未，確獄定含鉛有N個關抄鍵字臟的m階B-樹的唇最大神深度榆，即宏可判借斷其律查找騙效率央。在具臟有N個關略鍵字進的B-樹上旦進行昌查找漿時，土從根圍結點距到關擾鍵字K所在翅結點帥的路幕徑涉伯及的凝結點距數(shù)目拘不超襖過:lo膛gm/帝2((撥N+煩1)晚/2寒)+嚷1。五、B-樹和B+樹9.思2動態(tài)大查找恰表4．B-樹的佛插入軍和刪勞除在B-樹上益進行礦插入殃和刪暢除操挨作較聽為復共雜，灣要使樹進行項操作御后的淡結點偉中關果鍵字悉個數(shù)N滿足m/崖2-逝1違≤儉N估≤你m-面1，將涉舉及結批點的分裂與合并。(1董)B-樹的叮插入B-樹的剃生成儉也是儀從空毫樹開越始，育逐個剖插入虛關鍵脊字而桶得。味由于B-樹中栗關鍵之字個質數(shù)必惡須≥m/挪2-1油，因此政，每糖次插忽入一辰個關刪鍵字和不是潮在樹鄉(xiāng)豐中添危加一冊個葉旬子結虧點，估而是綱首先困在最惹低層繳的某開個非謝終端禮結點術中添蘿加一組個關蠟鍵字帶，若該惜結點晝的關鴉鍵字棕個數(shù)忽不超媽過m-敬1，則插感入完話成，申否則脫要產(chǎn)休生結模點的?！胺帜选?。五、B-樹和B+樹9.料2動態(tài)蠢查找慮表“分眼裂”縫的實鞋現(xiàn)：假設烏*p結點搶中已持有m-管1個關莊鍵字墨，當閃插入頂一個矮關鍵像字之升后，嫌結點獎含有酷信息蝴為：m,挨A0，(右K1，A1)，金……昆(Km，Am)其中Ki<Ki+11≤圓i<仿m此時介可將引*p結點職分裂隔為*p和*p’兩個佳結點勇，以m/風2為分型裂中宋心，宇其前彈一部攀分，習放在*p結點棒中，真后一務部分四放在*p’結點棄中。其中篇：*p結點播中含挽有信禿息為m/速2-1采，A陡0，倘(K1，A1)，望……盤(Km/槳2-1,Am/償2-1)*p瞞’結點倦中含并有信巖息為m-m/卻2，Am/柳2，(稅Km/炊2+1，Am/鍋2+1)，松……立(Km，Am)而關簽鍵字Km/鏡2和指巴向*p’的指孝針一萬起插宏入到窗*p的雙胡親結唐點中外。五、B-樹和B+樹9.陡2動態(tài)休查找蝴表(2腸)B-樹的榆刪除若在B-樹上牽刪除琴一個穩(wěn)關鍵跌字，內則首摟先應嘩找到憑關鍵位字所注在結湖點，托并從將中刪憶除之迅，若扇該結之點為環(huán)最下匹層的拘非終濁端結視點，白且其叢中關鍵粥字數(shù)瞧目不公少于m/柄2，則刪古除完至成，碌否則腎要進擊行“海合并尸”結脅點的叢操作率。五、B-樹和B+樹9.倚2動態(tài)銀查找霜表刪除垃最下帽層非吧終端瞎結點顯中的垃關鍵描字情蕩況，有下膠列三從種可朱能：被刪挨除關貨鍵字兇所在汗結點巨中的質關鍵釣字數(shù)莫目不諸小于m/沒2，則只妨需從釘該結森點中膝刪去麗該關蹈鍵字Ki和相得應的慰指針Ai程，樹的勾其它出部分孟不變漁。被刪挑關鍵潔字所筐在的治結點碎中的鏟關鍵殃字數(shù)凈目等獵于m/穿2-1蹤蝶，而與磨該結匙點相介鄰的稈右兄鮮弟(殃或左朵兄弟蜘)結下點中刷的關躁鍵字烤數(shù)目乳大于m/侮2-1陷，則需侮將其粗兄弟乎結點咸中最暖小(沿或最雨大)福的關我鍵字寬上移霧至雙予親結跑點中淺，而鏈將雙明親結換點中紅小于豈(或記大于善)且環(huán)緊靠奪該上翠移關被鍵字秀的關猜鍵字偉下移叛至被前刪關探鍵字門所在池結點般中。被刪摩關鍵鋪字所鈔在結利點和鋪其相沒鄰的肥兄弟置結點答中的風關鍵醬字數(shù)保目均糕等于m/雞2-1菠。假設喜該結美點有產(chǎn)右兄駕弟，考且其缸右兄戲弟結質點地震址由拋雙親肢結點覆中的孫指針Ai所指朽，則辣刪去慘關鍵泳字之悲后，省它所買在結逗點中較剩余授的關書鍵字某和指蔥針，危加上芽雙親取結點淺中的稼關鍵盟字Ki一起好，合晚并到Ai所指河兄弟龍結點炊中(封若沒猾有右掏兄弟摩，則蔬合并透到左都兄弟磁結點小中)韻。五、B-樹和B+樹9.面2動態(tài)曠查找偏表一、呀哈希課法的腔概念二、攝哈希役函數(shù)誤的構道造方伙法三、股處理遲沖突榆的方自法四、寸哈希答表的比查找吸及其帆分析9.繁3蘭哈識希表1．偉哈希秒法的軋引入哈希爐英文咳名稱煙為Ha妨sh眉，散列集(雜騾湊)脫的意形思。皆因此弦哈?？颖碛制卜Q散孤列表婦(雜筒湊表衣)。用哈損希表依是一柿種重謀要的拾存儲欣方法爆，也狼是一擔種常嚴用的屑查找尋方法畫。前搖述的畏查找蛙方法都是頑以關書鍵字腸的“比較”為暗基礎深的。卵查找裳的效蓄率依后賴于踢查找借過程趣中所奴進行驕比較委的次悼數(shù)。裕查找膠效率糕取決斯于結牧點的注個數(shù)捐。理想零的情掃況是洞希望博不經(jīng)忠過任量何比撒較，編一次載存取圓便能熔得到親所查緣瑞記錄晚，那喇就必適須在燃記錄指的存桿儲位季置和談它的爬關鍵籍字之掌間建山立一點個確橡定的折對應闖關系f，使每被個關插鍵字爐和結旬構中跳一個逃唯一竄的存繞儲位妻置相猾對應傷。這亞就是貢哈希巾法的遲思想鎮(zhèn)。查找席時，娘只需滋對結練點的躍關鍵宋字進就行某準種運殺算，護就能絲式直接雹確定為記錄共在表好中的航位置介。9.洋3份哈迎希表一、飯哈希匪法的駱概念2.迫哈隸希函沿數(shù)定鉤義將結床點的呈關鍵濃字作拜為自古變量ke匙y，通過何一個倡確定第的函數(shù)摸關系(關塞于關杯鍵字嗽的某窗種運踏算)f，計算曾出函鍛數(shù)值f(坐ke蔥y)作為圍該結波點的草存儲際地址掩。這滿個確靜定關再系f就是名哈希廉函數(shù)英。查找潔時，曠用哈竊希函怨數(shù)確股定地刪址取心結點肌。如：景某地猾區(qū)解蜻放后因人口傘調查筆表，懶關鍵降字是規(guī)年份顧。9.紫3炊哈積希表一、轎哈希徑法的普概念地址0102……22……58年份19491950……1970……2006人口15361540……2059……4065H(念ke乘y)露=k堪ey閣-1農(nóng)94快83.等哈呀希表真的定譯義用哈妙希函營數(shù)建輸立起夢來的壩存儲壺結構爽稱為巧哈希隱表。4.智散擋列地氏址法淚(散嘴列技遺術)用哈猴希函爺數(shù)轉擾換記卡錄關而鍵字棒得到攤存儲務地址巨，把擋各記兇錄散冠列到而相應躲的存息儲單唯元里停去的販方法懸，稱趴為散碑列地掃址法壟或關漢鍵字根轉換摸法。9.異3拋哈何希表一、卷哈希堂法的添概念5．豬沖突對不妖同的悅關鍵露字可菊能得忌到同考一哈凱希地影址，稿即ke蕩y1ke知y2，而f(琴ke郵y1)=幟f(隱ke理y2)，這種尚現(xiàn)象橡稱為駕沖突配。如：更全國桿各省油的人悅口統(tǒng)比計表殺中，滔關鍵段字為吼各省饅名字沈的漢盟語拼程音。切使用半不同察的哈恰希函勺數(shù)。H1(k平ey姥):關鍵網(wǎng)字中省第一饞個字疑母在浙字母藍表中餃的位占置H2(k臥ey顧):關鍵腥字中吃第一逢個與觸最后行一個厚字母斧在字娃母表針中位吸置的住和，賣若比虜30廟(表赤長)奮大，創(chuàng)則減皆30耍。9.奸3捏哈廈希表一、插哈希另法的島概念keybeijingtianjinhebeishanxishanghaiH1(key)0220081919H2(key)0904172828具有相同錢函數(shù)警值的關鍵鐮字對該賺哈希動函數(shù)飯來說駁稱為同義致詞。6．柄哈?？罘ǖ乃貎蓚€剩問題(1泊)掌如攻何構膚造哈蹲希函釘數(shù)構造御哈希摘函數(shù)溜也要頂解決般兩個爬問題軟：哈希陜函數(shù)羞應是尚一個壓縮樣映象函數(shù)爹，它道應具猜有較魂大的跑壓縮餅性，榨以節(jié)棉省存虎儲空覺間。亦這樣消就不憲可避怖免地光產(chǎn)生呈沖突虹。哈希鋸函數(shù)懲應具崗有較北好的散列彎性，盡饅量減惱少沖另突。(2要)挺如讓何解及決沖郊突9.世3態(tài)哈庸希表一、辮哈希籠法的狠概念7．喚綜合撇描述根據(jù)心設定析的哈?？购瘮?shù)H(黃ke幣y)和處理俱沖突的方企法將專一組關鍵感字映調像到一匯個有核限的連續(xù)晃地址腰集(唯區(qū)間專)上，并丑以關嗽鍵字斑在地槐址集垃中的宇“像”作央為記倦錄在裕表中絲式的存儲樸位置，這徒種表類便稱虧為哈希勿表，這丈一映像臉過程為哈希納造表直或散柿列表，所沈得存儲免位置稱為哈希順地址或散列屈地址終。9.眼3飯哈侄希表一、俊哈希雄法的沿概念均勻口的哈曉希函負數(shù)——若對計于關令鍵字充集合聲中的塔任一叛個關煩鍵字知，經(jīng)脂哈?；I函數(shù)愚映像泳到地檢址集組中任賭何一屠個地養(yǎng)址的睬概率僚是相針等的若，則事稱此間類哈乒希函種數(shù)為錯均勻陳的哈翻希函贏數(shù)。換句遷話說揮，就忌是關閣鍵字瘋經(jīng)過斤哈希朵函數(shù)焦得到宅一個塘“隨機奴的地蠶址”，只以便碗使一兔組關曉鍵字陣的哈越希地填址均勻染分布在整界個地朝址區(qū)毯間中視，從落而減來少沖蘭突。1．廟直接鬼定址六法取關鍵惱字或槽關鍵搶字的暖某個卸線性快函數(shù)吉值為哈淚希地厭址。怕即H(航ke喂y)鑄=k撿ey或H(陵ke懇y)餃=a棟*k糾ey罷+b其中a、桶b為常傘數(shù)。掠又稱H(盯ke笨y)為自恐身函擔數(shù)。這種媽方法馬，地簽址集苦合和施關鍵閘字集綱合相透同，艷沒有堅沖突喂，但走若關辭鍵字召集合綢大，剛則地晴址空稈間也悟很大肝，很糠少采尋用。9.像3悉哈千希表二、緊哈希方函數(shù)貓的構竿造方駱法2．代數(shù)字跌分析膽法假設正關鍵刃字是剖以r為基金的數(shù)廚(如虹以1同0為繪基的白十進撲制數(shù)殃)，威并且框哈希球表中誤可能漸出現(xiàn)孤的關料鍵字柱都是急事先富知道檢的，抱則可雹取關寨鍵字岔的若矮干數(shù)害位組熱成哈捧希地雖址。此方榆法是悲通過干分析流關鍵停字的使構成營(主鴉要是鬧數(shù)字漂形式聯(lián))，為了屆盡量飄避免太沖突斗，取萄那些迎出現(xiàn)尚的數(shù)耀字隨際機的框位數(shù)剪，作量為哈蓬希地酒址的薄位數(shù)寺，而浴那些略總出愁現(xiàn)一而種數(shù)糊字或成某幾舟種數(shù)儉字的倍位數(shù)撲，則川不取皮。9.