9.2靜態(tài)查找表9.3動態(tài)查找樹表9.4哈希表9.1基本概念第九章查找表一、二叉排序樹（二叉查找樹）1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析由關(guān)鍵字序列3，1，2，5，4構(gòu)造一顆二叉排序樹由關(guān)鍵字序列1，2，3，4，5構(gòu)造一顆二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.25．查找性能的分析由關(guān)鍵字序列3，1，2，5，4構(gòu)造一顆二叉排序樹由關(guān)鍵字序列1，2，3，4，5構(gòu)造一顆二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.25．查找性能的分析問題1：怎樣選擇關(guān)鍵字的輸入次序？問題2：如果輸入次序不變，如何構(gòu)造二叉排序樹？一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹9.3動態(tài)查找樹表五、鍵樹一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹9.3動態(tài)查找樹表五、鍵樹二、二叉平衡樹1.二叉平衡樹定義2.平衡旋轉(zhuǎn)技術(shù)3.二叉平衡樹的插入4.二叉平衡樹的刪除5.二叉平衡樹的高度問題：二叉排序樹的缺點是無法事先預料樹的結(jié)構(gòu)，隨意性很大，樹結(jié)構(gòu)只與結(jié)點的值和插入的次序有關(guān)，有時會得到一顆很不平衡的二叉樹。當二叉樹與理想的平衡樹相差越遠，樹的高度越高時，其運算的時間就越長。最壞的情況下，二叉樹退化成單鏈表，其時間復雜度由O(log2n)變?yōu)镺(n)。1.二叉平衡樹定義

二叉平衡樹（又稱AVL樹）一棵二叉平衡樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：1。左子樹和右子樹都是二叉平衡樹，2。左子樹和右子樹的高度之差的絕對值不超過1。例如:458254821

二叉排序樹非平衡樹1510325126045非平衡樹

結(jié)點的平衡因子：

左子樹的高度減右子樹的高度。011001220001-101-2構(gòu)造平衡的二叉排序樹的方法是：

根據(jù)初始序列，從空樹開始插入新結(jié)點，插入過程中，在保持二叉排序樹特性的前提下，采用平衡旋轉(zhuǎn)技術(shù)，對最小不平衡子樹進行調(diào)整，使其平衡。如何構(gòu)造“二叉平衡樹”?1548215103260450122001-2-20二、二叉平衡樹1.二叉平衡樹定義2.平衡旋轉(zhuǎn)技術(shù)3.二叉平衡樹的插入4.二叉平衡樹的刪除5.二叉平衡樹的高度2.平衡旋轉(zhuǎn)技術(shù)

如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡。平衡旋轉(zhuǎn)有兩類：單旋轉(zhuǎn)(左旋和右旋)

雙旋轉(zhuǎn)(左平衡和右平衡)右單旋轉(zhuǎn)左單旋轉(zhuǎn)

左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)右單旋轉(zhuǎn)

如果在左子樹根結(jié)點的左子樹上插入結(jié)點,

引起不平衡，則需要進行右單旋轉(zhuǎn)。以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)。hhh+1CEABD00hhhACEBD01hh+1BACEDh12543543左單旋轉(zhuǎn)

如果在右子樹根結(jié)點的右子樹上插入結(jié)點，引起不平衡，則需要進行左單旋轉(zhuǎn)以結(jié)點C為旋轉(zhuǎn)軸，讓結(jié)點A逆時針旋轉(zhuǎn)。hhhACEBD-10hhh+1BACED-2-1hhh+1CEABD00543435先左后右雙旋轉(zhuǎn)如果在左子樹根結(jié)點的右子樹上插入結(jié)點，引起不平衡，則需要進行先左后右雙旋轉(zhuǎn)。534543543左右0012-11插入左單旋轉(zhuǎn)先左后右雙旋轉(zhuǎn)001右單旋轉(zhuǎn)先右后左雙旋轉(zhuǎn)如果在右子樹根結(jié)點的左子樹上插入結(jié)點引起不平衡，則需要進行先右后左雙旋轉(zhuǎn)。435543534右左+1001-1-2插入右單旋轉(zhuǎn)先右后左雙旋轉(zhuǎn)001右單旋轉(zhuǎn)二、二叉平衡樹1.二叉平衡樹定義2.平衡旋轉(zhuǎn)技術(shù)3.二叉平衡樹的插入4.二叉平衡樹的刪除5.二叉平衡樹的高度例如:依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)3.二叉平衡樹的插入426589426895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9二、二叉平衡樹1.二叉平衡樹定義2.平衡旋轉(zhuǎn)技術(shù)3.二叉平衡樹的插入4.二叉平衡樹的刪除5.二叉平衡樹的高度4.二叉平衡樹的刪除1.首先不考慮平衡問題，按二叉排序樹的刪除原理對二叉平衡樹進行刪除。2.然后再考慮平衡問題，沿被刪除結(jié)點通向根的路徑反向追蹤檢查路徑上各個結(jié)點平衡因子的變化。分三種情況考慮：case1:當前結(jié)點p的平衡因子為0。如果它的左子樹或右子樹被縮短，則只需要修改它的

平衡因子為

1

或-1。不需要旋轉(zhuǎn)。0hhh-1刪除一個結(jié)點,高度不變不旋轉(zhuǎn)1hh-1ppcase2:結(jié)點p的平衡因子不為0，且較高的子樹被縮短，則p的平衡因子改為0。不需要旋轉(zhuǎn)。1h+1hh刪除一個結(jié)點,高度降低一層不旋轉(zhuǎn)0hhpp高度減1case3:結(jié)點p的平衡因子不為0，且較矮的子樹又被縮短，則在結(jié)點p發(fā)生不平衡。需要進行平衡化旋轉(zhuǎn)來恢復平衡。令結(jié)點

p的較高的子樹的根為

q,根據(jù)q的平衡因子，有如下3種平衡化操作：hhh-1phq

六種狀態(tài)：

p

q-1-1-10-111-110

11相同—aq為0—b相反—ccase3—a:

如果q的平衡因子與p的平衡因子相同， 則執(zhí)行一個單旋轉(zhuǎn)來恢復平衡,結(jié)點p和q的平衡因子均改為0。-1hh-1刪除結(jié)點左單旋ph-1qh-10h-1phq0h-1case3—b:

如果q

(較高的子樹)的平衡因子為0， 執(zhí)行一個單旋轉(zhuǎn)來恢復結(jié)點p的平衡。左單旋-1hh-1phq1-1hhh-1刪除結(jié)點ph0qcase3—c:

如果p與q的平衡因子相反,

則執(zhí)行一個雙旋轉(zhuǎn)來恢復平衡,先圍繞q轉(zhuǎn)再圍繞p轉(zhuǎn);

新根結(jié)點的平衡因子置為0，其它結(jié)點的平衡因子相應處理。-1hh-1刪除結(jié)點p1qh-1h-2h-1r0h-1h-2h-1h-100pqr右左雙旋高度減1ABCDEFGHIJKLMNOPQRST00000001111111-1-1-1-1-1樹的初始狀態(tài)舉例：刪除結(jié)點PABCDEFGHIJKLMNOPQRST00000001111111-1-1-1-1-1刪除結(jié)點P尋找結(jié)點P在中序下的直接前驅(qū)O,用O頂替P,刪除O。用O取代PABCDEFGHIJKLMNOQRST0000001111111-1-1-1-1-1刪除結(jié)點P左單旋轉(zhuǎn)

case3a：O與R的平衡因子同號,以R為旋轉(zhuǎn)軸做左單旋轉(zhuǎn),M的右子樹高度減1。qpABCDEFGHIJKLMNOQRST0000001111111-100-1刪除結(jié)點Pcase3c：M的右子樹高度減1,M發(fā)生不平衡。M與E的平衡因子反號,做左右雙旋轉(zhuǎn)。0向上繼續(xù)調(diào)整qpABCDEFGHIJNKLMOR0000010011110-100刪除結(jié)點P00TQ0S二、二叉平衡樹1.二叉平衡樹定義2.平衡旋轉(zhuǎn)技術(shù)3.二叉平衡樹的插入4.二叉平衡樹的刪除5.二叉平衡樹的高度

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)

要求完成以下操作：例題：若對表中元素先進行排序，構(gòu)成有序表，并求其在等概率的情況下，對此有序表查找成功時的平均查找長度；按表中元素的順序依次插入生成一顆二叉排序樹(初始為空)，并求其在等概率的情況下查找成功時的平均查找長度；按表中元素的順序構(gòu)造一顆二叉平衡樹，并求其在等概率的情況下查找成功的平均查找長度；例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)ASL=(1×1+2×2+3×4+4×5

)/12=37/121.有序表先排序，然后采用折半查找(Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep)

34

234

134

2

434例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)JanFebMarAprMayJunJulAugSepOctNovDecASL=(1×1+2×2+3×3+4×3+5×2+6×1)/12=42/122.求二叉排序樹例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)JanFebMarAprMayJunJulAug3.求平衡二叉排序樹例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)AugAprJanMarMayJunJul3.求平衡二叉排序樹FebSepOct例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)Oct3.求平衡二叉排序樹AugAprJanMarJunJulFebSepMayNov例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)ASL=(1×1+2×2+3×4+4×4+5×1

)/12=38/123.求平衡二叉排序樹AugAprJanFebSepOctMarMayNovJunJulDec

例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)ASL=(1×1+2×2+3×3+4×3+5×2+6×1)/12=42/122.求二叉排序樹1.有序表，排序后采用折半查找ASL=(1×1+2×2+3×4+4×5

)/12=37/123.求平衡二叉排序樹ASL=(1×1+2×2+3×4+4×4+5×1

)/12=38/12二、二叉平衡樹1.二叉平衡樹定義2.平衡旋轉(zhuǎn)技術(shù)3.二叉平衡樹的插入4.二叉平衡樹的刪除5.二叉平衡樹的高度對于AVL樹來說，如果結(jié)點個數(shù)為n，最大深度h？設(shè)AVL樹的高度為h，這個AVL樹中最少含有多少個結(jié)點？記最少結(jié)點個數(shù)為Nh，則：

h＝0，空樹： N0=0

h＝1，僅有根結(jié)點：N1=1

h>1：Nh

=？5.二叉平衡樹的高度Nh-1+Nh-2+1Nh-1+Nh-1+1Nh-1+Nh-2+1Nh

的定義與斐波那契數(shù)列的定義非常相似。

F0=0,F1=1,

Fh

=Fh-1+Fh-2

可以證明,對于h

0,有Nh=Fh+2-1成立。012345678910111201123581321345589144kF(k)h＝0N0=0h＝1N1=1h>1：Nh=Nh-1+Nh-2+1N3＝F5-1=4N4＝F6-1=7Nh+1=(Nh-1+1)+(Nh-2+1)有n個結(jié)點的AVL樹的高度不超過：

≈1.44*log2(n+1)一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹9.3動態(tài)查找樹表五、鍵樹三、有序查找表一、靜態(tài)查找表數(shù)據(jù)類型定義二、順序查找表9.2靜態(tài)查找表四、靜態(tài)查找樹表五、索引順序表靜態(tài)索引結(jié)構(gòu)當數(shù)據(jù)表中的記錄個數(shù)n很大時,由于內(nèi)存容量的限制，不能全部存入內(nèi)存。因此在查找過程中需要反復與外存交換信息，此時前面介紹的各種算法的效率都很低。折半查找：記錄必須全部在內(nèi)存。靜態(tài)查找樹表：記錄必須全部在內(nèi)存。二叉平衡樹：記錄必須全部在內(nèi)存。

順序查找：記錄不必全部在內(nèi)存，但搜索效率極低。1.索引順序表2.m叉靜態(tài)搜索樹采用索引方法來實現(xiàn)記錄的存儲和搜索后面要討論的B樹和鍵樹是動態(tài)索引結(jié)構(gòu)例：有一個存放職工信息的數(shù)據(jù)表.每一個職工數(shù)據(jù)10M字節(jié),

假設(shè)有10000個職工，則數(shù)據(jù)表共占100G。但內(nèi)存只有2G。keyaddr8310008140031809522024260473001734051360索引表100140180220260300340380職工號

姓名

性別

職務(wù)

婚否

83

張珊

女

教師已婚

…

08

李斯

男

教師已婚...

03

王魯

男

教務(wù)員已婚...

95

劉琪

女

實驗員未婚...

24

岳跋

男

教師已婚...

47

周斌

男

教師已婚...

17

胡江

男

實驗員未婚...

51

林青

女

教師未婚...

數(shù)據(jù)表采用索引表，每個索引項可索引一個職工記錄，且占8個字節(jié),則10000個索引項需要80K個字節(jié)。1.索引順序表索引項記錄稠密索引：一個索引項對應數(shù)據(jù)表中一個記錄的索引結(jié)構(gòu)。

2212133029333642444839406074567980669282889894

子表1子表2子表3子表4數(shù)據(jù)區(qū)33488098索引表1234max_keymax_addr

稀疏索引：當記錄在外存中有序(塊)存放時，可以把所有n個記錄分為b個子表(塊)存放，一個索引項對應數(shù)據(jù)表中一組記錄(子表)。在子表中,記錄可能按關(guān)鍵碼有序地存放,也可能無序地存放。但所有這些子表必須分塊有序,即：后一個子表中所有記錄的關(guān)鍵碼均大于前一個子表中所有記錄的關(guān)鍵碼。索引順序表的查找一般分為兩級搜索:先在索引表中搜索給定值K,查找確定滿足范圍

ID[i-1].max_key<K

ID[i].max_key

的

i值,即待查記錄可能在的子表的序號。

然后在第i個子表中按給定值搜索要求的記錄。索引表是按max_key有序的,且長度也不大,可以折半搜索，也可以順序搜索。各子表中的記錄如果也按對象關(guān)鍵碼有序,可以采用折半查找或順序查找;如果不是按記錄關(guān)鍵碼有序,只能順序查找。查找成功時的平均查找長度

ASLIndexSeq=ASLIndex+ASLSubList

其中：

ASLIndex：在索引表中搜索子表位置的平均查找長度

ASLSubList：在子表中查找記錄位置的查找成功時的平均查找長度。設(shè)把長度為n

的表分成均等的

b個子表，每個子表有s個記錄，則b=n/s。又設(shè)表中每個記錄的查找概率相等，則在索引表中查找的概率為1/b，在子表中查找的概率為1/s。若對索引表和子表都用順序查找，則查找成功時的平均查找長度為:ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+1

＝(n/s+s)/2+1索引順序查找的平均查找長度與表中的記錄個數(shù)n有關(guān)，與每個子表中的記錄個數(shù)s有關(guān)。在給定n的情況下，s應選擇多大？用數(shù)學方法可導出,當s=時,ASLIndexSeq取極小值:ASLIndexSeq=+1。這個值比順序查找強，但比折半查找差。六.靜態(tài)索引結(jié)構(gòu)當數(shù)據(jù)表中的記錄個數(shù)n很大時,由于內(nèi)存容量的限制，不能全部存入內(nèi)存。因此在查找過程中需要反復與外存交換信息，此時前面介紹的各種算法的效率都很低。折半查找：記錄必須全部在內(nèi)存。靜態(tài)查找樹表：記錄必須全部在內(nèi)存。二叉平衡樹：記錄必須全部在內(nèi)存。

順序查找：記錄不必全部在內(nèi)存，但搜索效率極低。1.索引順序表2.m叉靜態(tài)搜索樹采用索引方法來實現(xiàn)記錄的存儲和搜索后面要討論的B樹和鍵樹是動態(tài)索引結(jié)構(gòu)當數(shù)據(jù)記錄數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。此時,可以建立索引的索引(二級索引)。二級索引可以常駐內(nèi)存，二級索引中一個索引項對應一個索引塊，它記錄下一級索引塊的存儲地址及索引塊中的最大關(guān)鍵碼。2.m叉靜態(tài)搜索樹02061115182329323841454952607795(23,)(49,)(95,)(06,)(15,)(23,)(32,)(41,)(49,)(60,)(95,)一級索引二級索引(06,)(15,)(23,)(32,)(41,)(49,)(60,)(95,)m叉靜態(tài)搜索樹特點：

由多級索引結(jié)構(gòu)形成一種m叉樹。樹中每一個內(nèi)部結(jié)點表示一個索引塊；每個索引塊中最多存放m個索引項；索引項分別給出各子樹結(jié)點的最大關(guān)鍵碼和結(jié)點地址。數(shù)據(jù)區(qū)一級索引二級索引三級索引四級索引一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹9.3動態(tài)查找樹表五、鍵樹三、B-樹1．定義2．查找算法3．插入操作4．刪除操作5．查找性能的分析1．B-樹的定義B-樹是一種滿足以下特性的m叉動態(tài)搜索樹：FFFFFFFFFFFFFFF1）根結(jié)點至少有兩個子樹；2）除根結(jié)點外，所有內(nèi)部結(jié)點至少有m/2個子樹，

最多有m棵子樹；3）所有外部結(jié)點位于同一層上；m=?4

在

m

階的B-樹上，每個內(nèi)部結(jié)點可能含有：

n

個關(guān)鍵字Ki（1≤i≤n）m/2-1≤n≤m-1n+1

個指向子樹的指針Ai（0≤i≤n）;多叉特性FFFFFFFFFFFFFFFB-樹結(jié)構(gòu)的C語言描述如下:typedefstructBTNode{int

keynum;//結(jié)點中關(guān)鍵字個數(shù)，結(jié)點大小

structBTNode*parent;

//指向雙親結(jié)點的指針

KeyTypekey[m+1];//關(guān)鍵字（0號單元不用）

structBTNode*ptr[m+1];//子樹指針向量

Record*recptr[m+1];//記錄指針（0號單元不用）}BTNode,*BTree;//B-樹結(jié)點和B-樹的類型關(guān)鍵字個數(shù)雙親指針子樹指針關(guān)鍵字記錄指針…

…A0K1D1n內(nèi)部結(jié)點中的多個關(guān)鍵字均從小到大有序排列,

即：K1<K2<…<Kn;Ai-1所指子樹上所有關(guān)鍵字均小于Ki;Ai所指子樹上所有關(guān)鍵字均大于Ki;查找特性FFFFFFFFFFFFFFF平衡特性樹中所有葉子(外部)結(jié)點均在樹的同一層次上;根結(jié)點或為葉子結(jié)點，或至少含有兩棵子樹;其余所有非葉結(jié)點均至少含有m/2棵子樹，至少m/2-1個關(guān)鍵字，至多含有m

棵子樹;FFFFFFFFFFFFFFF三、B-樹1．定義2．查找算法3．插入操作4．刪除操作5．查找性能的分析從根結(jié)點出發(fā)，沿指針搜索內(nèi)部結(jié)點和在結(jié)點內(nèi)進行順序（或折半）查找

兩個過程交叉進行。2.查找算法：若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點的指針和關(guān)鍵字在結(jié)點中的位置

若查找不成功，則返回插入位置。FFFFFFFFFFFFFFFq給定值＝62

ppqp返回Result=(p,2,1)q返回結(jié)果(pt,i,tag)FFFFFFFFFFFFFFFq給定值＝60

ppqpq返回Result=(q,1,0)pq返回結(jié)果(pt,i,tag)ResultSearchBTree(BTreeT,KeyTypeK){//q指向p的雙親}//SearchBTreep=T;q=NULL;found=FALSE;i=0;

while(p&&!found){

i=Search(p,K);

//在p->key[1..keynum]中查找i，p->key[i]≤K＜p->key[i+1]

if(i>0&&p->key[i]==K)found=TRUE;else{q=p;p=p->ptr[i];}//q指示p的雙親

}

if(found)return

(p,i,1);//查找成功

elsereturn

(q,i,0);//