第7章查找計算機系主要內(nèi)容7.1查找的基本概念7.2靜態(tài)查找表順序查找二分查找分塊查找7.3動態(tài)查找表二叉搜索樹/二叉排序樹平衡二叉樹27.4平衡多路查找樹3階B樹4階B樹M階B樹B+樹7.5哈希表哈希表與哈希方法哈希函數(shù)的構造方法處理沖突的方法重難點分塊查找二叉搜索樹查找過程、結點的插入結點的刪除(直接前驅(qū)或后繼替代)平衡樹二叉樹結點的插入、刪除不平衡形態(tài)的判定、旋轉平衡多路查找樹3階和4階B樹B+樹3哈希表/散列查找表哈希函數(shù)的構造解決沖突的方法各種查找算法的性能分析時間復雜度空間復雜度7.1查找的基本概念（1）查找表由同一類型的數(shù)據(jù)元素（或記錄）構成的集合，稱為查找表。如圖的學生招生錄取登記表。4學號姓名性別入學總分錄取專業(yè)┊┊┊┊┊20010983張三女438物聯(lián)網(wǎng)20010984李四男430計算機20010985王五女445英語┊┊┊┊┊20010998趙六男458人工智能┊┊┊┊┊表7-1學生招生錄取登記表7.1查找的基本概念（2）對查找表進行的操作查找某個特定的數(shù)據(jù)元素是否存在；檢索某個特定數(shù)據(jù)元素的屬性；在查找表中插入一個數(shù)據(jù)元素；在查找表中刪除一個數(shù)據(jù)元素。（3）靜態(tài)查找表在查找過程中，僅查找某個特定元素是否存在或查找其屬性；查找表被創(chuàng)建后，一般不做修改和更新，即不能進行插入、刪除和修改。（4）動態(tài)查找表既能查找，也可以更改(插入、刪除、修改)57.1查找的基本概念（5）關鍵字(Key)數(shù)據(jù)元素(也稱為記錄)中某個數(shù)據(jù)項的值，用它可以標識數(shù)據(jù)元素。（6）主關鍵字(PrimaryKey)可以唯一地標識一個記錄的關鍵字稱為主關鍵字。例如：身份證號、學號、ISBN編號、手機號等。（7）次關鍵字(SecondaryKey)可以標識若干個記錄的關鍵字稱為次關鍵字。例如：姓名、生日等。67.1查找的基本概念（8）查找(也稱為檢索)(Searching)在查找表中確定是否存在一個數(shù)據(jù)元素的關鍵字等于給定值的操作。若表中存在這樣一個數(shù)據(jù)元素，則稱為查找成功；否則，稱為查找失敗。（9）內(nèi)查找和外查找若整個查找過程全部在內(nèi)存進行，則稱為內(nèi)查找；若在查找過程中還需要訪問外存，則稱為外查找。目前的數(shù)據(jù)結構課程中，一般僅介紹內(nèi)查找，但是隨著大數(shù)據(jù)時代的到來，外查找算法越來越重要。77.1查找的基本概念

8

7.2靜態(tài)查找表靜態(tài)查找表，可以采用順序存儲，也可以采用鏈表存儲；若采用順序存儲一般為第2章所介紹的順序表為了處理方便，查找表中的數(shù)據(jù)元素并不總是從0號單元開始存儲，也經(jīng)常從數(shù)組的1號單元開始存儲。若采用鏈式存儲本節(jié)默認為無頭結點的單向非循環(huán)鏈表靜態(tài)查找表的特點：在查找過程中，表中數(shù)據(jù)元素不會發(fā)生變化。97.2.1順序查找順序查找是最基本的查找方法，既適用于順序表，也適用于鏈表。該方法也稱為線性查找。順序查找的基本思想從表的一端開始，順序掃描線性表，將給定值kx依次與各數(shù)據(jù)元素的關鍵字key進行比較。若相等，則查找成功，并給出數(shù)據(jù)元素在線性表中的位置或地址；若整個表掃描完畢，未能找到關鍵字與kx相同的數(shù)據(jù)元素，則查找失敗，給出查找失敗的提示。107.2.1順序查找順序查找算法的實現(xiàn)順序存儲時，數(shù)據(jù)元素一般從下標為1的數(shù)組單元開始存放；0號單元作為監(jiān)視哨，用來存放待查找的值x。110123naxR1R2R3......Rni=n;while(i>0

&&

a[i]!=x) i--;returni;//返回0說明未找到i=n;while(a[i]!=x) i--;returni;7.2.1順序查找順序查找算法的實現(xiàn)12intseqSearch(SeqListlist,ElemTypex)//從表list中查找數(shù)據(jù)元素x{

inti=list.length; //從數(shù)組的高下標端開始查找

//0號單元用作監(jiān)視哨，存放待查找的值或關鍵字

list.data[0]=x;

//while(i>0&&list.data[i]!=x)

while(list.data[i]!=x)

i--;

if(i==0)

return-1; //查找失敗，返回-1，表示沒有找到

else

returni; //查找成功，返回其下標}7.2.1順序查找監(jiān)視哨的作用：省去了循環(huán)中下標越界的判定，節(jié)約了比較時間；保存查找值的副本，查找時若遇到它，則表示查找失敗；不必再判斷查找表是否檢測完，查找失敗和成功時的處理，實現(xiàn)了統(tǒng)一。順序查找性能分析對一個含有n個數(shù)據(jù)元素的表，查找成功時有：13

7.2.1順序查找

147.2.2二分查找/折半查找二分查找也叫折半查找是一種效率較高的查找方法；但前提是表中元素必須按關鍵字有序（遞增或遞減）排列。二分查找的基本思路取有序表中的中間元素作為比較對象，若給定值與中間元素的關鍵字相等，則查找成功；若給定值小于中間元素的關鍵字，則在中間元素的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關鍵字，則在中間元素的右半?yún)^(qū)繼續(xù)查找。重復上述查找過程，直到查找成功，或查找失敗。157.2.2二分查找/折半查找舉例：待查找的值K＝221602161122252739334256778179013245687910111312lowmidhighlowmidhighmidhighlowmidhighlow[1,13][1,6][4,6][4,4]逐步縮小查找范圍mid=(low+high)/27.2.2二分查找/折半查找舉例：待查找的值K＝231702161122252739334256778179013245687910111312lowmidhighlowmidhighmidhighlowmidhighlow[1,13][1,6][4,6][4,4]逐步縮小查找范圍highlow[5,4]范圍不存在7.2.2二分查找/折半查找18intbinSearch(SeqListlist,ElemTypex) //二分查找{

intmid;

intlow=1,high=list.length; //設置初始查找范圍

while(low<=high) //若查找區(qū)間存在

{

mid=(low+high)/2;

if(list.data[mid]>x)

high=mid-1; //范圍縮小為左半?yún)^(qū)間

else

if(list.data[mid]<x)

low=mid+1; //范圍縮小為右半?yún)^(qū)間

else

returnmid; //查找成功

}

return-1;}7.2.2二分查找/折半查找二分查找算法的性能分析每次查找，都是以查找區(qū)間的中點為比較對象，并以中點將查找區(qū)間分割為兩個子區(qū)間，對定位到的子區(qū)間繼續(xù)做同樣的操作。因此，對每個數(shù)據(jù)元素的查找過程，可用二叉樹來描述，描述查找過程的這個二叉樹稱為判定樹。193129211438465235492354218二叉判定樹7.2.2二分查找/折半查找折半查找判定樹20mid左半?yún)^(qū)間右半?yún)^(qū)間Low......mid-1mid+1......high7.2.2二分查找/折半查找n=13的折半查找判定樹2171..68..133101..24..68..911..131581224691113折半查找判定樹是一棵理想的平衡樹樹的高度為H=

log2(n+1)

或H=log2n+1樹的形態(tài)取決于n值7.2.2二分查找/折半查找查找x＝39220216112225273342567781790132456879101113123973101581224691113

二分查找/折半查找查找x＝13230216112225273342567781790132456879101113123973101581224691113查找失敗，x與關鍵字的比較次數(shù)也不超過樹高。7.2.2二分查找/折半查找n=13時的平均查找長度2473101581224691113查找成功:ASL=(1×1+2×2+3×4+4×6)/13=41/13查找失敗:ASL=(3×2+4×12)/14=54/147.2.2二分查找/折半查找折半查找的ASL假設n=2h-1折半查找判定樹是高為h的滿二叉樹h=log2(n+1)25

7.2.2二分查找/折半查找ASL的推導過程折半查找算法的時間復雜度O(log2n)26

7.2.2二分查找/折半查找折半查找的前提：關鍵字有序，且為順序表；折半查找判定樹可以看出，查找每個結點所需的比較次數(shù)等于該結點在樹上的層次數(shù)；折半查找樹是一棵理想的平衡二叉樹，樹的高度為

log2n

+1；無論查找成功或失敗，與關鍵字的最大比較次數(shù)，都不超過二叉樹的高度。277.2.2二分查找/折半查找二分查找的優(yōu)點：查找的效率高。二分查找的缺點：必須按關鍵字排序，有時排序也很費時；只適用順序存儲結構，所以進行插入、刪除操作必須移動大量的結點。二分查找適用于那種一經(jīng)建立就很少改動，但是又經(jīng)常需要查找的線性表。對于那些經(jīng)常需要改動的線性表，可以采用鏈式存儲結構，進行順序查找。287.2.3分塊查找/索引順序查找分塊查找(索引順序查找)查找性能介于順序查找和折半查找之間；對表的限制也是介于順序查找和折半查找之間；查找表的特點：分塊有序，塊內(nèi)無序，塊間有序。第i塊的最大關鍵字小于第i＋1塊的最小關鍵字。除了查找表外，還需要建一個索引表，查找分兩級進行。297.2.3分塊查找/索引順序查找分塊查找表索引表是有序表在索引表中查塊號，采用順序查找或折半查找均可在查找表中找目標記錄，只能采用順序查找ASL＝索引表的ASL＋查找表的ASL3067147015941608864515945372948351508122313121110987654321151013

stadr

塊起始地址23486494key塊內(nèi)最大鍵值01234索引表：7.2.3分塊查找/索引順序查找

317.3動態(tài)查找表動態(tài)查找表的特點：在查找過程中，表中數(shù)據(jù)元素會發(fā)生變化。動態(tài)查找表在查找過程中可能會進行元素的插入、刪除或修改操作。327.3.1二叉搜索樹/二叉排序樹二叉排序樹的定義二叉排序樹要么是一棵空樹，要么是具有下列性質(zhì)的二叉樹：(1)若它的左子樹不空，則左子樹上所有結點的鍵值均小于根結點的鍵值；(2)若它的右子樹不空，則右子樹上所有結點的鍵值均大于根結點的鍵值；(3)它的左、右子樹也都是二叉排序樹。337.3.1二叉搜索樹/二叉排序樹二叉排序樹舉例二叉排序樹的重要性質(zhì)：中序序列是一個有序序列中序序列：12，19，26，29，32，34，39，44，46,48，56343248263929563412441946左子樹上所有結點均小于根；右子樹上所有結點均大于根；左、右子樹也都是二叉排序樹。7.3.1二叉搜索樹/二叉排序樹生成二叉排序樹時，新結點的插入原則若二叉樹為空，則將插入結點作為根結點。若插入結點小于根，則在左子樹中尋找插入位置；若插入結點大于根，則在右子樹中尋找插入位置；直至某個結點(假設為P結點)的左、右子樹為空。若插入的值小于P結點，插入結點作為P結點的左孩子，否則作為P結點的右孩子。357.3.1二叉搜索樹/二叉排序樹二叉排序樹的插入與生成關鍵字序列：53，24，45，85，27，1236532485271245ASL=(1×1＋2×2＋3×2＋4×1)/6=15/67.3.1二叉搜索樹/二叉排序樹關鍵字序列：45，24，27，53，12，85關鍵字序列：12，24，27，45,53，8537452453122785ASL=(1×1＋2×2＋3×3)/6=14/6124585272453ASL=(1＋2＋3＋4＋5＋6)/6=21/6二叉排序樹蛻化成了單支的線性結構！7.3.1二叉搜索樹/二叉排序樹二叉排序樹的構造過程若關鍵字序列為：33，50，42，18，39，9，77，44，2，11，24二叉排序樹的構造過程為387.3.1二叉搜索樹/二叉排序樹每次插入的新結點，都是新的葉子結點，不必移動任何結點，僅需修改原有結點的某個指針即可。39452453122785Tqp257.3.1二叉搜索樹/二叉排序樹——刪除操作二叉排序樹中刪除一個結點的三種情況（1）刪除的結點是葉子結點將其父結點與該結點相連接的指針設為NULL；如圖要刪除結點11，則只需將其父結點9的右指針設為NULL。4016112528199201316252819920137.3.1二叉搜索樹/二叉排序樹——刪除操作二叉排序樹中刪除一個結點的三種情況（2）刪除的結點只有一棵子樹將被刪除結點的子樹向上提升，用子樹的根結點取代被刪除結點。如圖要刪除結點9，則用結點11取代結點9。41161125281992013162528191120137.3.1二叉搜索樹/二叉排序樹——刪除操作二叉排序樹中刪除一個結點的三種情況（3）刪除的結點有兩棵子樹(有兩種方法)

中序直接前驅(qū)替代法：將被刪除結點的中序遍歷的直接前驅(qū)結點取代被刪除結點。如圖若要刪除結點20，則將結點19和結點20的值交換，然后再刪除20。4216112528199201316112528919137.3.1二叉搜索樹/二叉排序樹——刪除操作二叉排序樹中刪除一個結點的三種情況（3）刪除的結點有兩棵子樹(有兩種方法)

中序直接后繼替代法：將被刪除結點的中序遍歷的直接后繼結點替代被刪除的結點。如圖若要刪除結點20，則將結點20和結點25的值交換，然后再刪除20。4316112528199201316112819925137.3.1二叉搜索樹/二叉排序樹——查找操作從bt所指二叉樹中，查找給定值x當x<bt->key時，在bt的左子樹上繼續(xù)查找當x>bt->key時，在bt的右子樹上繼續(xù)查找當x==bt->key時，查找成功443248263929563412441946bt7.3.1二叉搜索樹/二叉排序樹——查找操作從bt所指二叉樹中，查找給定值xx＝34x＝18查找成功：自樹根沿樹枝到達目標結點查找失?。鹤詷涓貥渲Φ竭_一個空樹的結點成功或失敗的最大比較次數(shù)，都不超過樹的高度453248263929563412441946bt7.3.1二叉搜索樹/二叉排序樹——查找性能分析查找成功時：ASL＝(1×1＋2×2＋3×4

＋4×3＋5×1)/11

＝34/11查找失敗時：ASL＝(3×5＋4×5＋5×2)/12＝45/124632482639295634124419467.3.1二叉搜索樹/二叉排序樹——查找性能分析在二叉排序樹中查找關鍵字等于給定值的結點的過程，恰是走了一條從根到該結點的路徑。含有n個結點的二叉樹是不唯一的，如何進行查找分析呢？(a)的高度為3，ASL(a)=14/6

(b)的高度為6，ASL(b)=21/6

47302540153520153530402520(a)(b)ASL與二叉排序樹的形態(tài)有關!7.3.1二叉搜索樹/二叉排序樹——查找性能分析二叉排序樹的ASL和其形態(tài)有關在最壞情況下，二叉排序樹是通過一個有序表的n個結點依次插入生成，此時所得的二叉排序樹蛻化為一棵深度為n的單支樹，它的ASL和單向鏈表的順序查找相同，都為(n+1)/2。在最好情況下，生成的二叉排序樹，每棵左右子樹都比較均勻，其最終得到的是一棵形態(tài)與二分查找判定樹相似的二叉排序樹，樹的高度約為log2n，查找時的最大比較次數(shù)不會超過樹的高度。當n較大時，log2n可能遠小于(n+1)/2均勻的二叉排序樹，插入或刪除結點后，可能需要對其形態(tài)進行調(diào)整，使其左右子樹依然保持均勻。487.3.2平衡二叉樹/

AVL樹平衡二叉樹是指任一結點的左、右子樹高度大致相等的二叉樹。平衡二叉樹有很多種，最著名的是由前蘇聯(lián)數(shù)學家Adelse-Velskil和Landis在1962年提出的，稱為AVL樹。平衡二叉樹或者是一棵空樹，或者是具有以下性質(zhì)的二叉排序樹：它的左子樹和右子樹的高度之差（稱為平衡因子）的絕對值不超過1；它的左子樹和右子樹又都是平衡二叉樹。497.3.2平衡二叉樹/

AVL樹結點的平衡因子在平衡二叉樹上插入或刪除結點后，可能使樹失去平衡，可能需要對失去平衡的樹進行平衡化處理。50(a)平衡二叉樹70603585407542101-110070609035854065507542470300-320-2010(b)非平衡二叉樹7.3.2平衡二叉樹/

AVL樹平衡二叉樹的插入及調(diào)整先按二叉排序樹的方式，插入新結點X然后找到離插入點最近的不平衡祖先，即A結點根據(jù)X和A結點的相對位置，判定不平衡形態(tài)LL型，X位于A結點的左子樹Left的左子樹Left中此時應將以A結點為根的整棵二叉樹，單向右旋。RR型，X位于A結點的右子樹Right的右子樹Right中此時應將以A結點為根的整棵二叉樹，單向左旋。LR型，X位于A結點的左子樹Left的右子樹Right中此時應先局部單向左旋，后整體單向右旋。RL型，X位于A結點的右子樹Right的左子樹Left中此時應先局部單向右旋，后整體單向左旋。517.3.2平衡二叉樹/

AVL樹LL型——單向右旋(以A為根的子樹)527.3.2平衡二叉樹/

AVL樹LR型——先局部左旋，后整體右旋局部指以B為根的子樹，整體指以A為根的子樹。537.3.2平衡二叉樹/

AVL樹RR型——單向左旋(以A為根的子樹)547.3.2平衡二叉樹/

AVL樹RL型——先局部右旋，后整體左旋局部指以B為根的子樹，整體指以A為根的子樹。557.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，265642429142539142539142539142539129RL型先局部右旋后整體左旋7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，265742539129LR型4253912917LL型2953911742295391174249單向右旋7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，2658LR型295391174249425391294917425391294917先局部左旋后整體右旋7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，26594253912949174253912949173542539129491735747.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，2660425391294917357442539129491735742383425391294917357423LR型7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，2661425391294917357423837442539129491735832342538329491735742391LR型先局部左旋后整體右旋7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，26624253832949173574239142538329491735742391117.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，2663624253832949173574239111RL型42538329491735742391117.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，2664624253832949173574239111425374294917356223831191RL型先局部右旋7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，2665425374294917356223831191427483295317352391114962后整體左旋7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，266642748329531735239111496242748329531735239111496226LR型7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，26674274832953173523911149622642748329532335269117496211LR型先局部左旋7.3.2平衡二叉樹/

AVL樹畫出按如下順序插入，建立平衡二叉樹的過程42，91，53，29，17，49，35，74，23，83，11，62，26684274832953233526911749621142748323531729911149623526后整體右旋LR型所有結點，已全部插入！7.4平衡多路查找樹

697.4平衡多路查找樹平衡二叉樹的特點每次插入或刪除結點都可能會破壞其平衡，而要保持平衡則需要進行旋轉，而這些重新調(diào)整為平衡的操作則會影響整個結構的性能。除非是在樹的結構變化特別少的情況下，否則調(diào)整為平衡所帶來的搜索性能提升，可能還不足以彌補維持其平衡的性能損耗。在數(shù)據(jù)量很大的情況下，可以將平衡二叉樹，改為平衡多路查找樹適當增加樹結點中的元素數(shù)量，從而控制樹的高度；將樹結點中的元素數(shù)量控制在一定范圍而不是取某個固定值，從而減少維持其平衡的操作次數(shù)。數(shù)據(jù)庫等涉及磁盤I/O的大規(guī)模查找算法，廣泛采用了平衡多叉樹。707.4平衡多路查找樹平衡多叉樹即平衡多路樹，如果樹中結點允許擁有的最多孩子數(shù)為M（M≥3），則稱其為M階B樹(BalancedTreeofOrderM)。B樹(BalancedTree)中的結點2型結點：包含1個元素和2個指針域；3型結點：包含2個元素和3個指針域；4型結點：包含3個元素和4個指針域；……以上各種類型結點的多個指針域，要么都為空，要么都不為空。717.4平衡多路查找樹——3階B樹（2-3樹）3階B樹（2-3樹）所有結點必為2型或3型，因此又稱其為2-3樹（讀作：二三樹）。每個分支結點必有2個或3個孩子。727.4平衡多路查找樹——3階B樹（2-3樹）2-3樹若不為空，則必須滿足如下性質(zhì)：（1）對于2型結點，和普通的二叉搜索樹結點一樣，其中有一個數(shù)據(jù)域和兩個孩子結點的指針域。兩個孩子指針域要么都為空，要么也都是2-3樹，當前結點數(shù)據(jù)域的值必須大于左子樹中所有結點的值，并且必須小于右子樹中所有結點的值。（2）對于3型結點，有兩個數(shù)據(jù)域a和b，以及三個孩子結點的指針域。左子樹中所有結點的值要小于a，中子樹中所有結點的值要大于a且小于b，右子樹中所有結點的值要大于b。（3）2-3樹的所有葉子點必須在同一層。737.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中查找指定元素63747.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中查找指定元素12757.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（1）向2型結點中插入新元素767.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（2）向一棵只含3型結點的樹中插入新元素777.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（3）向一個父結點為2型結點的3型結點中插入新元素787.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（3）向一個父結點為2型結點的3型結點中插入新元素797.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（3）向一個父結點為2型結點的3型結點中插入新元素807.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（4）向一個父結點為3型的3型結點中插入新元素817.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（4）向一個父結點為3型的3型結點中插入新元素827.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（4）向一個父結點為3型的3型結點中插入新元素837.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（4）向一個父結點為3型的3型結點中插入新元素847.4平衡多路查找樹——3階B樹（2-3樹）向2-3樹中插入元素，主要分為4種情況：（4）向一個父結點為3型的3型結點中插入新元素857.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中刪除元素，主要有3種情形（1）刪除非葉子結點中的元素867.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中刪除元素，主要有3種情形（1）刪除非葉子結點中的元素877.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中刪除元素，主要有3種情形（1）刪除非葉子結點中的元素887.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中刪除元素，主要有3種情形（2）刪除3型葉子結點中的元素。897.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中刪除元素，主要有3種情形（2）刪除3型葉子結點中的元素。907.4平衡多路查找樹——3階B樹（2-3樹）從2-3樹中刪除元素，主要有3種情形（3）刪除2型葉子結點中的元素刪除2型葉子結點中的元素，步驟相對比較復雜，刪除結點后可能需根據(jù)不同情況調(diào)整樹的結構。主要分為如下四種情形：①若刪除元素的相鄰兄弟結點中存在3型結點②刪除元素的相鄰兄弟結點為2型，但其父結點為3型③刪除元素的相鄰兄弟結點為2型，父結點也為2型④所有結點均為2型結點（即2-3樹類似于滿二叉樹）以上四種情形的刪除圖示，參見教材。917.4平衡多路查找樹——4階B樹（2-3-4樹）4階B樹4階B樹為3階B樹的擴展，其定義和操作均與3階的情況類似。在4階B樹中，除了2型和3型結點之外，還允許有4型結點。4階B樹也稱為2-3-4樹，其每個分支結點必有2個、3個或4個孩子927.4平衡多路查找樹——4階B樹（2-3-4樹）B樹的簡化表示937.4平衡多路查找樹——4階B樹（2-3-4樹）4階B樹的生成過程947.4平衡多路查找樹——M階B樹

957.4平衡多路查找樹——M階B樹B樹的小結B樹是在平衡二叉樹的基礎上，允許每個結點中存放多個數(shù)據(jù)元素，將平衡二叉樹改造成平衡多叉樹，使其形態(tài)從“高瘦”變得“矮胖”，從而減少了調(diào)整為平衡的操作次數(shù)和開銷，提高了插入和刪除元素的效率。雖然4階B樹中已允許存在3型和4型結點，但是仍可能存在大量的2型結點。極端情況下，如果所有結點均為2型，則4階B樹將退化為滿的平衡二叉樹，B樹的優(yōu)勢將無法體現(xiàn)，即便是更高階的B樹，也可能存在大量結點中存儲元素過少的類似問題。因此，M階B樹的一般定義中限定了每個分支結點中數(shù)據(jù)域的最少個數(shù)。967.4平衡多路查找樹——B+樹B+樹是B樹的一種變體，其大體結構與B樹相同。B+樹也屬于平衡多路查找樹，也主要用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)。但是B+樹和B樹有如下兩個明顯不同：（1）B+樹的所有分支結點中不保存元素的數(shù)據(jù)，只保存元素的關鍵字，B+樹中所有元素的數(shù)據(jù)都存儲在葉子節(jié)點。（2）B+樹中底部的所有葉子結點通過指針鏈接，可通過葉子結點實現(xiàn)順序查找。977.4平衡多路查找樹——B+樹例如：將集合{42，91，53，29，17，49，35，74，23，11}中的元素依次插入，生成一棵4階B+樹的過程如下圖。98圖7-34(a)依次插入元素42，91，53，29，17；插入29后執(zhí)行了分裂操作。圖7-34(b)繼續(xù)插入元素49和35；插入35后執(zhí)行了分裂操作。7.4平衡多路查找樹——B+樹例如：將集合{42，91，53，29，17，49，35，74，23，11}中的元素依次插入，生成一棵4階B+樹的過程如下圖。99圖7-34(c)繼續(xù)插入元素74；插入74后執(zhí)行了分裂操作。圖7-34(d)繼續(xù)插入元素23；因為23小于35，所以將其插入到35左子樹中的合適位置。7.4平衡多路查找樹——B+樹例如：將集合{42，91，53，29，17，49，35，74，23，11}中的元素依次插入，生成一棵4階B+樹的過程如下圖。100圖7-34(e)繼續(xù)插入元素11；插入11后將執(zhí)行分裂操作。圖7-34(f)分裂元素11所在的結點之后；需繼續(xù)對根結點也執(zhí)行分裂操作。7.4平衡多路查找樹——B+樹例如：將集合{42，91，53，29，17，49，35，74，23，11}中的元素依次插入，生成一棵4階B+樹的過程如下圖。101圖7-34(g)分裂根結點之后，得到最終生成的B+樹。特別注意：（1）圖7-34(f)中最后一次分裂的不是葉子結點，而是索引結點，因此分裂產(chǎn)生的右孩子結點74中無需包含根結點的關鍵字53。因為圖7-34(a)~(e)中每次分裂的都是葉子結點，而葉子結點中存放的都是待查找的元素，所以每次分裂產(chǎn)生的左右孩子結點中，必須包含分裂之前結點中的所有元素。（2）B+樹的所有分支結點中存放的都只是關鍵字，即所有分支結點均為索引結點。因此，在B+樹中執(zhí)行查找操作時，無論查找成功或失敗，都必須從根找到最底層的葉子結點。7.5哈希表哈希表與哈希方法以上查找方法，由于數(shù)據(jù)元素的存儲位置與關鍵字之間，不存在確定的對應關系。因此，查找時，需要進行一系列關鍵字的比較，即“查找算法”是建立在比較的基礎上，查找效率由比較一次縮小的查找范圍決定。理想的情況是，依據(jù)關鍵字直接得到數(shù)據(jù)元素的存放位置，即要求關鍵字與數(shù)據(jù)元素間存在一一對應關系，通過這個關系，能很快地由關鍵字得到對應數(shù)據(jù)元素的位置。1027.5哈希表哈希表與哈希方法例如，11個元素的關鍵字分別為：18，27，1，20，22，6，10，13，41，15，25。選取關鍵字與元素位置間的函數(shù)為：f(key)=key%11通過這個哈希函數(shù)，可以建立如下查找表：查找時，對給定值kx通過這個函數(shù)計算出地址，再將kx與該地址對應單元中元素的關鍵字比較，若相等，則查找成功。103關鍵字與函數(shù)的對應關系10204118627152513122f(key)key012

3456789107.5哈希表哈希表與哈希方法選取某個函數(shù)，依該函數(shù)按關鍵字計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值kx計算地址，將kx與地址單元中元素關鍵字進行比較，確定查找是否成功，這就是哈希方法。哈希方法中使用的轉換函數(shù)，稱為哈希函數(shù)。按此思想構造的表，稱為哈希表。1047.5哈希表經(jīng)過哈希函數(shù)的變換后，可能將不同的關鍵字映射到同一個哈希地址上，這種現(xiàn)象稱為沖突(collision)。沖突不可能避免，只能盡可能減少。因此，哈希方法需要解決以下兩個問題：①構造好的哈希函數(shù)所選哈希函數(shù)盡可能簡單，以便提高轉換速度。所選函數(shù)對關鍵字計算出的地址，在哈希地址集合中，應該大致均勻分布，以便盡可能減少沖突。②制定沖突的解決方案。1057.5哈希表哈希函數(shù)的構造方法直接定址法Hash(key)=a·key+b(其中a、b為常數(shù))即取關鍵字的某個線性函數(shù)值為哈希地址；這類函數(shù)是一一對應函數(shù)，不會產(chǎn)生沖突，但是要求地址集合與關鍵字集合大小相同；因此，對于較大的關鍵字集合并不適用。1067.5哈希表哈希函數(shù)的構造方法除留余數(shù)法

Hash(key)=key%p(p是一個整數(shù))即取關鍵字除以p的余數(shù)，作為哈希地址。使用除留余數(shù)法，選取合適的p很重要若哈希表表長為m，則要求p≤m，且接近m或等于m。p一般選取質(zhì)數(shù)，也可以是不包含小于20質(zhì)因子的合數(shù)。1077.5哈希表哈希函數(shù)的構造方法平方取中法即對關鍵字進行平方運算后，按哈希表的大小，取中間的若干位，作為哈希函數(shù)值。例如：若存儲區(qū)域可以存儲100條記錄，關鍵字=47314731×4731=22382361，則哈希值為82。108哈希函數(shù)值，在地址空間中，應隨機均勻分布（目的是盡可能地減少沖突）！7.5哈希表——處理沖突的方法開放定址法所謂開放定址法，就是一旦產(chǎn)生了沖突(Hash函數(shù)算出的地址已經(jīng)存放了別的數(shù)據(jù)元素)；就去尋找下一個空的存儲單元。只要哈希表的存儲單元足夠多，新的空的存儲單元就總能找到，然后將當前數(shù)據(jù)元素存入。1097.5.3處理沖突的方法——線性探測法

110△229%11=77.5.3處理沖突的方法——線性探測法開放定址法線性探測法舉例：關鍵字集合為{47，7，29，11，16，92，22，8，3}，哈希表的表長為11，哈希函數(shù)如下：Hash(key)=key%11用線性探測法處理沖突，建立的Hash表如下：111924722118297316△222%11=0△28%11=8▲43%11=30123456789107.5.3處理沖突的方法——線性探測法

112924722118297316012345678910△229%11=7△222%11=0△28%11=8▲43%11=37.5.3處理沖突的方法——線性探測法

113△229%11=7924722118297316△222%11=0△28%11=8▲43%11=30123456789107.5.3處理沖突的方法——二次探測法開放定址法線性探測法可能使第i個單元的同義詞，存入第i+1個單元，這樣本應存入第i+1個單元的元素變成了第i+2個單元的同義詞，……因此，可能出現(xiàn)很多元素在相鄰的單元連續(xù)沖突，引起“堆積”的現(xiàn)象，大大降低了查找效率。為此，可采用二次探測法，或雙哈希函數(shù)探測法，以改善“堆積”問題。114※※※※※※012345678910※連續(xù)