信管第八章查找_第1頁
信管第八章查找_第2頁
信管第八章查找_第3頁
信管第八章查找_第4頁
信管第八章查找_第5頁
已閱讀5頁,還剩95頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、第8章 查 找 第第8 8章章 查找查找(Search) (Search) 8.1 8.1 基本概念基本概念 8.2 8.2 靜態(tài)查找靜態(tài)查找8.3 8.3 動態(tài)查找動態(tài)查找8.4 8.4 哈希表哈希表第8章 查 找 8.1.1 8.1.1 術(shù)語術(shù)語1 1、查找表(、查找表(Search TableSearch Table):):由同一類型的數(shù)據(jù)元素由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。(或記錄)構(gòu)成的集合。 涉及的操作:涉及的操作:查詢某個查詢某個“特定的特定的”數(shù)據(jù)元素是否在查找表中數(shù)據(jù)元素是否在查找表中檢索某個檢索某個“特定的特定的”數(shù)據(jù)元素的各種屬性數(shù)據(jù)元素的各種屬性在查找表中插入

2、一個原來沒有的數(shù)據(jù)元素在查找表中插入一個原來沒有的數(shù)據(jù)元素在查找表中刪除一個已存在的數(shù)據(jù)元素在查找表中刪除一個已存在的數(shù)據(jù)元素 8.1 8.1 基本概念基本概念第8章 查 找 基于以上四種操作,可以把查找表分為:基于以上四種操作,可以把查找表分為:靜態(tài)查找表靜態(tài)查找表(Static Search Table)(Static Search Table)和動態(tài)查找表和動態(tài)查找表(Dynamic Search Table) (Dynamic Search Table) 2 2、關(guān)鍵字、關(guān)鍵字(Key)(Key):是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值,用它可以標識(識別

3、)一個數(shù)據(jù)元素(或記錄)。的值,用它可以標識(識別)一個數(shù)據(jù)元素(或記錄)。本章所討論的查找方法都是基于關(guān)鍵字的檢索。本章所討論的查找方法都是基于關(guān)鍵字的檢索。 3 3、主關(guān)鍵字、主關(guān)鍵字(Primary Key)(Primary Key):可以唯一地表示一個記錄可以唯一地表示一個記錄的關(guān)鍵字。對于不同的記錄,主關(guān)鍵字均不同。的關(guān)鍵字。對于不同的記錄,主關(guān)鍵字均不同。 第8章 查 找 4 4、次關(guān)鍵字、次關(guān)鍵字(Secondary Key)(Secondary Key):有時為了檢索具有某種有時為了檢索具有某種性質(zhì)的記錄,需要按指定的數(shù)據(jù)項性質(zhì)的記錄,需要按指定的數(shù)據(jù)項( (組組) )值進行檢

4、索,該值進行檢索,該數(shù)據(jù)項數(shù)據(jù)項( (組組) )值并不能惟一確定一個記錄。值并不能惟一確定一個記錄。 5 5、查找、查找(Searching)(Searching):根據(jù)給定的某個值,在查找表中根據(jù)給定的某個值,在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。 若表中存在這樣的一個記錄,若表中存在這樣的一個記錄,則稱查找成功則稱查找成功,此時,此時查找結(jié)果為給出整個記錄的信息,或指示該記錄在查找查找結(jié)果為給出整個記錄的信息,或指示該記錄在查找表中的位置;若表中不存在關(guān)鍵字等于給定值的記錄,表中的位置;若表中不存在關(guān)鍵字等于給定值的記錄,則稱則稱

5、查找不成功查找不成功,此時查找結(jié)果可給出一個,此時查找結(jié)果可給出一個“空空”記錄記錄或或“空空”指針。指針。 第8章 查 找 8.1.2 8.1.2 查找分類查找分類 1 1、靜態(tài)查找:針對、靜態(tài)查找:針對兩種操作。兩種操作。 指查詢某個指查詢某個“特定的特定的”數(shù)據(jù)元素是否在查找表中,數(shù)據(jù)元素是否在查找表中,或檢索某個或檢索某個“特定的特定的”數(shù)據(jù)元素的各種屬性;靜態(tài)查找數(shù)據(jù)元素的各種屬性;靜態(tài)查找主要在靜態(tài)查找表中進行。主要在靜態(tài)查找表中進行。 2 2、動態(tài)查找:針對、動態(tài)查找:針對兩種操作。兩種操作。 在查找過程中同時插入查找表中不存在的數(shù)據(jù)元在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素

6、,或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素。素,或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素。動態(tài)查找主要在動態(tài)查找表中進行。動態(tài)查找主要在動態(tài)查找表中進行。 3 3、散列查找、散列查找 利用哈希函數(shù),通過計算求取待查元素的存儲地利用哈希函數(shù),通過計算求取待查元素的存儲地址。散列查找在散列表中進行址。散列查找在散列表中進行。 第8章 查 找 8.1.3 8.1.3 各種查找算法的衡量標準各種查找算法的衡量標準 利用算法的平均查找長度(利用算法的平均查找長度(ASLAverage ASLAverage Search LengthSearch Length)作為衡量標準,即確定一基本元素)作為衡量標準

7、,即確定一基本元素在結(jié)構(gòu)中的位置所進行的比較次數(shù)的期望值。在結(jié)構(gòu)中的位置所進行的比較次數(shù)的期望值。 設(shè)某一數(shù)據(jù)結(jié)構(gòu)中共有設(shè)某一數(shù)據(jù)結(jié)構(gòu)中共有n n個數(shù)據(jù)元素,則查找此個數(shù)據(jù)元素,則查找此結(jié)構(gòu)中某一元素的平均查找長度為:結(jié)構(gòu)中某一元素的平均查找長度為: 第8章 查 找 niiicpASL1其中:其中: p pi i是查找第是查找第i i個數(shù)據(jù)元素的概率,且個數(shù)據(jù)元素的概率,且 ;11niipc ci i是找到第是找到第i i個數(shù)據(jù)元素所需要進行的比較次數(shù)。個數(shù)據(jù)元素所需要進行的比較次數(shù)。顯然顯然c ci i隨查找過程不同而不同。隨查找過程不同而不同。第8章 查 找 8.2 8.2 靜態(tài)查找靜態(tài)查

8、找8.2.18.2.1、靜態(tài)查找表的定義、靜態(tài)查找表的定義 查找表事先已經(jīng)存在,而且在查找過程中表查找表事先已經(jīng)存在,而且在查找過程中表的長度不發(fā)生變化。的長度不發(fā)生變化。 第8章 查 找 8.2.28.2.2、查找方法、查找方法 1 1順序查找順序查找(Sequential Search)(Sequential Search) 當(dāng)靜態(tài)查找表采用順序表或線性鏈表表示時,使當(dāng)靜態(tài)查找表采用順序表或線性鏈表表示時,使用順序查找用順序查找。 這是一種最簡單的查找方法,從表的一端開始,這是一種最簡單的查找方法,從表的一端開始,順序掃描查找表,依次將掃描到的數(shù)據(jù)元素的關(guān)鍵字順序掃描查找表,依次將掃描到的

9、數(shù)據(jù)元素的關(guān)鍵字和給定的關(guān)鍵字比較,若相等,則查找成功。若一直和給定的關(guān)鍵字比較,若相等,則查找成功。若一直掃描到表的另一端仍未找到關(guān)鍵字等于給定值的數(shù)據(jù)掃描到表的另一端仍未找到關(guān)鍵字等于給定值的數(shù)據(jù)元素,則查找不成功。元素,則查找不成功。 第8章 查 找 typedef struct typedef struct ElemType ElemType * *elemelem; /數(shù)據(jù)元素存儲空間基址,建表時按實際長度數(shù)據(jù)元素存儲空間基址,建表時按實際長度分配,分配,0 0號單元留空。號單元留空。 int lengthint length; /表長度表長度SSTableSSTable; /順序表

10、的定義順序表的定義第8章 查 找 算法實現(xiàn):算法實現(xiàn):int Search_seq(SSRable ST,KeyType key) int Search_seq(SSRable ST,KeyType key) /在順序表在順序表STST中順序查找其關(guān)鍵字等于中順序查找其關(guān)鍵字等于keykey的數(shù)據(jù)元素。的數(shù)據(jù)元素。/若找到,則函數(shù)值為該元素在表中的位置,否則為若找到,則函數(shù)值為該元素在表中的位置,否則為0 0,/即順序表的即順序表的0 0號位置號位置ST.elem0.key=key ST.elem0.key=key ; /“/“哨兵哨兵”for (i=ST.lengthfor (i=ST.le

11、ngth;!EQ(ST.elemi.key,key)!EQ(ST.elemi.key,key);-i)-i); /從后往前找從后往前找Return iReturn i; /找不到時,找不到時,i i為為0 0/Search_seq/Search_seq 設(shè)置哨兵的目的在于免去查找過程中每一步都要檢設(shè)置哨兵的目的在于免去查找過程中每一步都要檢測整個表是否查找完畢,起到監(jiān)視的作用。測整個表是否查找完畢,起到監(jiān)視的作用。第8章 查 找 算法分析:算法分析:查找成功時:查找成功時: 在順序查找過程中,在順序查找過程中,c ci i取決于所查記錄在表中的位取決于所查記錄在表中的位置。如查找表中最后一個記

12、錄時,僅需要比較一次;而置。如查找表中最后一個記錄時,僅需要比較一次;而查找表中第一個記錄時,則需要比較查找表中第一個記錄時,則需要比較n n次。次。一般情況下一般情況下c ci i等于等于n-i+1n-i+1。 21)1(111ninncpASLniniiiss 假定各記錄的查找機會均等,即假定各記錄的查找機會均等,即P Pi i1/n1/n,則在等概,則在等概率的情況下順序查找的平均查找長度為:率的情況下順序查找的平均查找長度為: 從上式可以看出,順序查找的平均查找長度較大,特從上式可以看出,順序查找的平均查找長度較大,特別是當(dāng)別是當(dāng)n n很大時,查找效率較低。而且有時表中各個記錄很大時,

13、查找效率較低。而且有時表中各個記錄的查找概率并不相等,的查找概率并不相等,因此為了提高查找效率,可以將查因此為了提高查找效率,可以將查找頻率較高的記錄放在表的尾部。找頻率較高的記錄放在表的尾部。 第8章 查 找 查找不成功時:查找不成功時: 在順序查找中,不論給定值在順序查找中,不論給定值keykey為何值,查找不成功為何值,查找不成功時和給定值進行比較的關(guān)鍵字個數(shù)均為時和給定值進行比較的關(guān)鍵字個數(shù)均為c ci i=n+1=n+1,因此在假,因此在假設(shè)每個記錄查找概率相等的情況下,其平均查找長度為:設(shè)每個記錄查找概率相等的情況下,其平均查找長度為: 1) 1(111nnncpASLniniii

14、ss第8章 查 找 2 2折半查找折半查找(Binary Search)(Binary Search) 折半查找方法使用時有一個前提條件,折半查找方法使用時有一個前提條件,即:靜即:靜態(tài)查找表必須是有序順序表(按由小到大,或者由態(tài)查找表必須是有序順序表(按由小到大,或者由大到小的順序)。大到小的順序)。 折半查找也叫二分查找折半查找也叫二分查找,是一種效率很高的查,是一種效率很高的查找方法。顧名思義,折半查找時將表一分為二,查找方法。顧名思義,折半查找時將表一分為二,查找可以不必從表的一端開始逐個比較,而是采用跳找可以不必從表的一端開始逐個比較,而是采用跳躍的方式,從表的中間開始查找。躍的方式

15、,從表的中間開始查找。 第8章 查 找 折半查找的過程:折半查找的過程: 先確定待查記錄所在的范圍(區(qū)間),然后逐步縮先確定待查記錄所在的范圍(區(qū)間),然后逐步縮小范圍直到找到或找不到該記錄為止。首先取區(qū)間小范圍直到找到或找不到該記錄為止。首先取區(qū)間low.highlow.high的中間位置的關(guān)鍵字的中間位置的關(guān)鍵字ST.elemmid.keyST.elemmid.key和和給定的給定的keykey相比較,若相等,則查找成功,否則按照它們相比較,若相等,則查找成功,否則按照它們的大小確定下一個查找區(qū)間。若的大小確定下一個查找區(qū)間。若ST.elemmid.keykeyST.elemmid.key

16、21 low=1 high=11 mid=6 ST.elemmid.key=5621 下一個查找區(qū)間為下一個查找區(qū)間為low,mid-1low,mid-1 low=1 high=5 mid=3 ST.elemmid.key=1921 low=1 high=5 mid=3 ST.elemmid.key=1921 下一個查找區(qū)間為下一個查找區(qū)間為mid+1,highmid+1,high low=4 high=5 mid=4 ST.elemmid.key=21=21 low=4 high=5 mid=4 ST.elemmid.key=21=21 查找成功查找成功 (05,13,19,21,37,56

17、,64,75,80,88,92)第8章 查 找 2 2)查找)查找8585 low=1 high=11 mid=6 ST.elemmid.key=5685 low=1 high=11 mid=6 ST.elemmid.key=5685 下一個查找區(qū)間為下一個查找區(qū)間為mid+1,highmid+1,high Low=7 high=11 mid=9 ST.elemmid.key=8085 Low=7 high=11 mid=9 ST.elemmid.key=8085 low=10 high=11 mid=10 ST.elemmid.key=8885 下一個查找區(qū)間為下一個查找區(qū)間為low,mid

18、-1low,mid-1 low=10 high=9 lowhigh low=10 high=9 lowhigh 查找不成功查找不成功 當(dāng)下界當(dāng)下界low大于上界大于上界high時,則說明表中沒有關(guān)鍵時,則說明表中沒有關(guān)鍵字等于字等于Key的元素,查找不成功。的元素,查找不成功。(05,13,19,21,37,56,64,75,80,88,92)第8章 查 找 算法實現(xiàn):算法實現(xiàn):int Search_bin(SSTable ST,KeyType key) int Search_bin(SSTable ST,KeyType key) low=1 low=1; high=ST.lengthhigh

19、=ST.length;/置區(qū)間初值置區(qū)間初值 while(low=high)while(low=high) mid=(low+high)/2 mid=(low+high)/2; if EQ(key,ST.elemmid.key) return midif EQ(key,ST.elemmid.key) return mid; /找到待查元素找到待查元素 else if LT(key,ST.elemmid.key) high=mid-1else if LT(key,ST.elemmid.key) high=mid-1; /繼續(xù)在前半?yún)^(qū)間進行查找繼續(xù)在前半?yún)^(qū)間進行查找 else low=mid+1e

20、lse low=mid+1; /繼續(xù)在后半?yún)^(qū)間進行查找繼續(xù)在后半?yún)^(qū)間進行查找 return 0 return 0; /順序表中不存在待查元素順序表中不存在待查元素/Search_bin /Search_bin 第8章 查 找 從上述查找過程可知,找到第從上述查找過程可知,找到第6 6個元素僅需要比較個元素僅需要比較1 1次,找到第次,找到第3 3和和9 9個元素需要比較個元素需要比較2 2次,找到第次,找到第1 1、4 4、7 7、1010個元素需要比較個元素需要比較3 3次,找到第次,找到第2 2、5 5、8 8、1111個元素需個元素需要比較要比較4 4次。次。這個查找過程可以用二叉樹來描

21、述。這個查找過程可以用二叉樹來描述。 算法分析:算法分析: 樹中每個結(jié)點表示表中一個記錄,結(jié)點中的值為樹中每個結(jié)點表示表中一個記錄,結(jié)點中的值為該記錄在表中的位置,通常稱這個二叉樹為該記錄在表中的位置,通常稱這個二叉樹為判定樹判定樹。 (05,13,19,21,37,56,64,75,80,88,92)第8章 查 找 從判定樹上可見,查找從判定樹上可見,查找2121的過程恰好是走了一條從的過程恰好是走了一條從根到結(jié)點根到結(jié)點4 4的路徑,和給定值進行比較的關(guān)鍵字個數(shù)為該的路徑,和給定值進行比較的關(guān)鍵字個數(shù)為該路徑上的結(jié)點數(shù)或結(jié)點路徑上的結(jié)點數(shù)或結(jié)點4 4在判定樹上的層次數(shù)。類似地,在判定樹上的

22、層次數(shù)。類似地,找到有序表中任何一個記錄的過程就是走了一條從根結(jié)找到有序表中任何一個記錄的過程就是走了一條從根結(jié)點到該記錄相應(yīng)的結(jié)點的路徑,點到該記錄相應(yīng)的結(jié)點的路徑,和給定值進行比較的關(guān)和給定值進行比較的關(guān)鍵字個數(shù)恰為該結(jié)點在判定樹上的層次數(shù)。鍵字個數(shù)恰為該結(jié)點在判定樹上的層次數(shù)。 第8章 查 找 因此,折半查找法在查找成功時進行比較的關(guān)鍵因此,折半查找法在查找成功時進行比較的關(guān)鍵字個數(shù)最多不超過樹的深度,而具有字個數(shù)最多不超過樹的深度,而具有n n個結(jié)點的判定樹個結(jié)點的判定樹的深度為的深度為 ,所以,所以,折半查找在查找成功時折半查找在查找成功時和給定值進行比較的關(guān)鍵字個數(shù)至多為和給定值進

23、行比較的關(guān)鍵字個數(shù)至多為 。 1log2n1log2n第8章 查 找 稱方形結(jié)點為判定樹的外部結(jié)點,相應(yīng)地稱圓形結(jié)稱方形結(jié)點為判定樹的外部結(jié)點,相應(yīng)地稱圓形結(jié)點為內(nèi)部結(jié)點,點為內(nèi)部結(jié)點,那末折半查找時查找不成功的過程就是那末折半查找時查找不成功的過程就是走了一條從根結(jié)點到外部結(jié)點的路徑,走了一條從根結(jié)點到外部結(jié)點的路徑,和給定值進行比和給定值進行比較的關(guān)鍵字個數(shù)等于該路徑上內(nèi)部結(jié)點個數(shù)較的關(guān)鍵字個數(shù)等于該路徑上內(nèi)部結(jié)點個數(shù)。 因此折半查找在查找不成功時和給定值進行比較的因此折半查找在查找不成功時和給定值進行比較的關(guān)鍵字個數(shù)最多也不超過關(guān)鍵字個數(shù)最多也不超過 。 1log2n(05,13,19,

24、21,37,56,64,75,80,88,92)56562121808005051919131388886464373775759292第8章 查 找 折半查找的平均查找長度折半查找的平均查找長度 假定有序表的長度假定有序表的長度 ,則描述折半查找的判,則描述折半查找的判定樹時深度為定樹時深度為h h的滿二叉的滿二叉樹樹,樹中層次為,樹中層次為1 1的結(jié)點有的結(jié)點有1 1個,個,層次為層次為2 2的結(jié)點有的結(jié)點有2 2個,個,層次為,層次為h h的結(jié)點有的結(jié)點有2 2h-1h-1個。個。假設(shè)表中每個記錄的查找概率相等,則查找成功時折半假設(shè)表中每個記錄的查找概率相等,則查找成功時折半查找的平均查

25、找長度為:查找的平均查找長度為: 12 hn1) 1(log2nASLbs1) 1(log1212111nnnjncpASLhjjniiibs第8章 查 找 第8章 查 找 所以,折半查找的平均查找長度數(shù)量級所以,折半查找的平均查找長度數(shù)量級( (算法時間算法時間復(fù)雜度復(fù)雜度) )亦為亦為O(logO(logn n) )。 由以上分析可知,折半查找的優(yōu)點是比較的次數(shù)少,由以上分析可知,折半查找的優(yōu)點是比較的次數(shù)少,查找比順序查找快。但這種速度是以預(yù)先對記錄按關(guān)鍵查找比順序查找快。但這種速度是以預(yù)先對記錄按關(guān)鍵字大小排序為代價的。另外,由于存儲結(jié)構(gòu)必須是數(shù)組,字大小排序為代價的。另外,由于存儲結(jié)

26、構(gòu)必須是數(shù)組,因此對經(jīng)常要進行插入和刪除操作的表,不宜采用這種因此對經(jīng)常要進行插入和刪除操作的表,不宜采用這種方法。方法。 第8章 查 找 3 3分塊查找分塊查找(Blocking search)(Blocking search) 分塊查找時要求靜態(tài)查找表以索引順序表存儲,因分塊查找時要求靜態(tài)查找表以索引順序表存儲,因此又稱為此又稱為索引順序查找,索引順序查找,是對順序查找的一種改進方法,是對順序查找的一種改進方法,性能介于順序查找和折半查找之間。性能介于順序查找和折半查找之間。 分塊查找要求把線性表分成若干塊,每一塊中的元分塊查找要求把線性表分成若干塊,每一塊中的元素存儲順序是任意的,但塊與

27、塊之間必須按關(guān)鍵字大小素存儲順序是任意的,但塊與塊之間必須按關(guān)鍵字大小遞增分塊,即前一塊的最大關(guān)鍵字值小于后一塊中最小遞增分塊,即前一塊的最大關(guān)鍵字值小于后一塊中最小關(guān)鍵字值。關(guān)鍵字值。 第8章 查 找 此外,還需建立一個此外,還需建立一個索引表索引表,索引表中的每一項,索引表中的每一項稱作稱作索引項,索引項,一個索引項對應(yīng)線性表中的一塊,一個索引項對應(yīng)線性表中的一塊,索引索引項由鍵域和鏈域組成,鍵域存放相應(yīng)塊的最大關(guān)鍵字項由鍵域和鏈域組成,鍵域存放相應(yīng)塊的最大關(guān)鍵字值,鏈域存放指向本塊第一個結(jié)點的存儲位置,值,鏈域存放指向本塊第一個結(jié)點的存儲位置,顯然顯然索引表是按關(guān)鍵字值遞增順序排列的有序

28、表,滿足上索引表是按關(guān)鍵字值遞增順序排列的有序表,滿足上述條件的線性表稱為述條件的線性表稱為分塊有序表。分塊有序表。 第8章 查 找 例如:例如:0909,2222,1212,1414,3535,4242,4444,3838,4848,6060,5858,4747,7878,8080,7777,8282 第8章 查 找 分塊查找法的查找過程分兩步進行:分塊查找法的查找過程分兩步進行:1 1、首先確定待查的結(jié)點屬于哪一塊,即查找所在的塊。、首先確定待查的結(jié)點屬于哪一塊,即查找所在的塊。2 2、然后在塊內(nèi)查找欲查找的結(jié)點。、然后在塊內(nèi)查找欲查找的結(jié)點。 由于索引表是遞增有序的,因此確定塊的查找由于

29、索引表是遞增有序的,因此確定塊的查找可以可以用順序查找,也可以用折半查找用順序查找,也可以用折半查找,而塊內(nèi)的元素個數(shù)較,而塊內(nèi)的元素個數(shù)較少,且塊中元素是任意排列的,少,且塊中元素是任意排列的,采用順序法在塊內(nèi)查找,采用順序法在塊內(nèi)查找,不會對執(zhí)行速度有太大的影響。所以,分塊查找的算法不會對執(zhí)行速度有太大的影響。所以,分塊查找的算法即為這兩種查找算法的簡單合成。即為這兩種查找算法的簡單合成。第8章 查 找 wbbsLLASL 其中:其中:Lb為查找索引表確定待查結(jié)點所在塊的平為查找索引表確定待查結(jié)點所在塊的平均查找長度,均查找長度,Lw為在塊中查找元素的平均查找長度。為在塊中查找元素的平均查

30、找長度。性能分析:性能分析: 由于分塊查找實際上是進行了兩次查找過程,即由于分塊查找實際上是進行了兩次查找過程,即確定記錄所在的塊和確定記錄在塊中的具體位置,因確定記錄所在的塊和確定記錄在塊中的具體位置,因此分塊查找的平均查找長度是兩次查找的平均查找長此分塊查找的平均查找長度是兩次查找的平均查找長度之和。度之和。第8章 查 找 一般情況下,為進行分塊查找,可以將長度為一般情況下,為進行分塊查找,可以將長度為n n的的表均勻地分成表均勻地分成b b塊,每塊含有塊,每塊含有s s個記錄,即個記錄,即b=n/sb=n/s;又;又假定表中每個記錄的查找概率相等,則每塊查找的概假定表中每個記錄的查找概率

31、相等,則每塊查找的概率為率為1/b1/b,塊中每個記錄的查找概率為,塊中每個記錄的查找概率為1/s1/s。 1) 1)若用順序查找確定所在塊,則分塊查找的平均若用順序查找確定所在塊,則分塊查找的平均查找長度為查找長度為 1ssn2121s21bis1jb1LLASLs1ib1jwbn 可見,此時的平均查找長度不僅和表長可見,此時的平均查找長度不僅和表長n n有關(guān),而有關(guān),而且和每一塊中的記錄個數(shù)且和每一塊中的記錄個數(shù)s s有關(guān)。在給定有關(guān)。在給定n n的前提下,的前提下,s s是可以選擇的。容易證明,當(dāng)是可以選擇的。容易證明,當(dāng)s s取取 時,時,ASLASL取最小取最小值值 。這個值比順序查

32、找有了很大的改進,但遠不。這個值比順序查找有了很大的改進,但遠不及折半查找。及折半查找。 1n 第8章 查 找 2) 2) 若用折半查找確定所在塊,則分塊查找的平若用折半查找確定所在塊,則分塊查找的平均長度為均長度為 21snlogASLs第8章 查 找 8.3 8.3 動態(tài)查找動態(tài)查找 前面討論的查找方法主要適用于具有固定大小前面討論的查找方法主要適用于具有固定大小的表,表的長度在查找過程中不發(fā)生變化,這類查找的表,表的長度在查找過程中不發(fā)生變化,這類查找屬于靜態(tài)查找。下面我們討論動態(tài)查找。屬于靜態(tài)查找。下面我們討論動態(tài)查找。 動態(tài)查找的特點是:動態(tài)查找的特點是:表結(jié)構(gòu)本身是在查找過程中表結(jié)

33、構(gòu)本身是在查找過程中動態(tài)生成的,即對于給定值動態(tài)生成的,即對于給定值keykey,若表中存在其關(guān)鍵字,若表中存在其關(guān)鍵字等于等于keykey的記錄,則查找成功返回,否則插入關(guān)鍵字等的記錄,則查找成功返回,否則插入關(guān)鍵字等于于keykey的記錄。的記錄。 第8章 查 找 8.3.1 8.3.1、二叉排序樹(、二叉排序樹(Binary Sort TreeBinary Sort Tree) 定義:二叉排序樹或者是一棵空樹;或者是定義:二叉排序樹或者是一棵空樹;或者是具有下列性質(zhì)的二叉樹:具有下列性質(zhì)的二叉樹: 若它的左子樹不空,則左子樹上所有結(jié)點的值若它的左子樹不空,則左子樹上所有結(jié)點的值均小于它的

34、根結(jié)點的值;均小于它的根結(jié)點的值; 若它的右子樹不空,則右子樹上所有結(jié)點的值若它的右子樹不空,則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值;均大于它的根結(jié)點的值; 它的左、右子樹也分別為二叉排序樹它的左、右子樹也分別為二叉排序樹。 第8章 查 找 圖圖 二叉排序樹示例二叉排序樹示例 264513(a)261(b)354123456(c)caocaozhaozhaodingdingchenchenwangwangmamaxiaxiaadudunini(d)第8章 查 找 1) 二叉排序樹的查找二叉排序樹的查找 二叉排序樹又稱二叉查找樹,它的查找過程為:二叉排序樹又稱二叉查找樹,它的查找過程為:當(dāng)二

35、叉排序樹不空時,首先將給定值和根結(jié)點的關(guān)鍵當(dāng)二叉排序樹不空時,首先將給定值和根結(jié)點的關(guān)鍵字比較,若相等,則查找成功,否則將依據(jù)給定值和字比較,若相等,則查找成功,否則將依據(jù)給定值和根結(jié)點的關(guān)鍵字之間的大小關(guān)系,分別在左子樹和右根結(jié)點的關(guān)鍵字之間的大小關(guān)系,分別在左子樹和右子樹上繼續(xù)進行查找。換言之,每次只需查找左或右子樹上繼續(xù)進行查找。換言之,每次只需查找左或右子樹的一枝便夠了,效率明顯提高。子樹的一枝便夠了,效率明顯提高。 通常二叉排序樹通常二叉排序樹采用二叉鏈表存儲。采用二叉鏈表存儲。第8章 查 找 查找算法描述:查找算法描述:BiTree SearchBST(BiTree T,Keyty

36、pe key) BiTree SearchBST(BiTree T,Keytype key) /在根指針在根指針T T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于所指二叉排序樹中遞歸地查找某關(guān)鍵字等于keykey的數(shù)據(jù)元素。若查找成功,則返回指向該數(shù)據(jù)元素結(jié)點的指的數(shù)據(jù)元素。若查找成功,則返回指向該數(shù)據(jù)元素結(jié)點的指針,否則返回空指針。針,否則返回空指針。 if(!T)|EQ(key,Tdata.key) return (T)if(!T)|EQ(key,Tdata.key) return (T);/查找結(jié)束查找結(jié)束 else if LT(key,Tdata.key) else if LT(key,Td

37、ata.key) return (SearchBST(Tlchild,key) return (SearchBST(Tlchild,key); /在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找 else return (SearchBST(Trchild,key)else return (SearchBST(Trchild,key); /在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找/SearchBST/SearchBST 第8章 查 找 2 2)二叉排序樹的插入)二叉排序樹的插入 由于二叉排序樹是一種動態(tài)樹表,特點是樹的結(jié)由于二叉排序樹是一種動態(tài)樹表,特點是樹的結(jié)構(gòu)通常不是一次生成的,而是在查找過程中,當(dāng)樹中構(gòu)

38、通常不是一次生成的,而是在查找過程中,當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點時再進行插入。新插不存在關(guān)鍵字等于給定值的結(jié)點時再進行插入。新插入的結(jié)點一定是一個新添加的葉子結(jié)點,并且是查找入的結(jié)點一定是一個新添加的葉子結(jié)點,并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子。右孩子。 因此插入的原則為:因此插入的原則為:若二叉排序樹為空,則插若二叉排序樹為空,則插入結(jié)點作為新的根結(jié)點,否則繼續(xù)在其左子樹或右入結(jié)點作為新的根結(jié)點,否則繼續(xù)在其左子樹或右子樹中進行查找,直到某個葉子結(jié)點,則插入結(jié)點子樹中進行查找,直到某個葉子結(jié)點,則插入結(jié)點應(yīng)為該

39、葉子結(jié)點的左子樹或右子樹。應(yīng)為該葉子結(jié)點的左子樹或右子樹。 第8章 查 找 Status InsertBST(BiTree &T,Elemtype e)Status InsertBST(BiTree &T,Elemtype e) /當(dāng)二叉排序樹當(dāng)二叉排序樹T T中不存在關(guān)鍵字等于中不存在關(guān)鍵字等于e.keye.key的數(shù)據(jù)元素時,插入的數(shù)據(jù)元素時,插入e e元素并返回元素并返回TRUETRUE,否則返回,否則返回FALSEFALSEif(!SearchBST(T,e.key,NULL,p)if(!SearchBST(T,e.key,NULL,p) / /查找不成功查找不成功 s

40、=(BiTree)malloc(sizeof(BiNode) s=(BiTree)malloc(sizeof(BiNode); /新建結(jié)點新建結(jié)點s s sdata=e sdata=e; slchild=srchild=NULLslchild=srchild=NULL; if(!p) T=sif(!p) T=s; /空樹時,被插結(jié)點空樹時,被插結(jié)點* *s s為新的根結(jié)點為新的根結(jié)點 else if LT(e.key,pdata.key) else if LT(e.key,pdata.key) plchild=s plchild=s; /被插結(jié)點被插結(jié)點* *s s為左孩子為左孩子 else

41、prchild=selse prchild=s; /被插結(jié)點被插結(jié)點* *s s為右孩子為右孩子 return TRUEreturn TRUE; else return FALSE else return FALSE; /樹中已有關(guān)鍵字相同的結(jié)點,不再插入樹中已有關(guān)鍵字相同的結(jié)點,不再插入/InsertBST/InsertBST第8章 查 找 若從空樹出發(fā),經(jīng)過一系列的查找插入操作之后,若從空樹出發(fā),經(jīng)過一系列的查找插入操作之后,可以生成一棵二叉樹??梢陨梢豢枚鏄洹?例如給定關(guān)鍵字序列為:例如給定關(guān)鍵字序列為:4545,2424,5353,1212,3636,9090。 從給定的例子可以看

42、出,中序遍歷二叉排序樹可以從給定的例子可以看出,中序遍歷二叉排序樹可以得到一個關(guān)鍵字的有序序列。得到一個關(guān)鍵字的有序序列。因此一個無序序列可以通因此一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列,構(gòu)造樹的過構(gòu)造一棵二叉排序樹而變成一個有序序列,構(gòu)造樹的過程就是進行排序的過程。過程就是進行排序的過程。 第8章 查 找 3) 3) 二叉排序樹查找分析二叉排序樹查找分析 二叉排序樹的查找過程和二叉判定樹類似,在二二叉排序樹的查找過程和二叉判定樹類似,在二叉排序樹上查找其關(guān)鍵字等于給定值的結(jié)點的過程,叉排序樹上查找其關(guān)鍵字等于給定值的結(jié)點的過程,恰好走了一條從根結(jié)點到該結(jié)點的路徑,和給定值比

43、恰好走了一條從根結(jié)點到該結(jié)點的路徑,和給定值比較的關(guān)鍵字個數(shù)等于該結(jié)點所在的層次。較的關(guān)鍵字個數(shù)等于該結(jié)點所在的層次。 因此和折半查找類似,與給定值比較的關(guān)鍵字個因此和折半查找類似,與給定值比較的關(guān)鍵字個數(shù)不超過樹的深度。但是,數(shù)不超過樹的深度。但是,以中間結(jié)點劃分的長度為以中間結(jié)點劃分的長度為n n的判定樹是唯一的,而含有的判定樹是唯一的,而含有n n個結(jié)點的二叉排序樹卻是個結(jié)點的二叉排序樹卻是不唯一的。不唯一的。 第8章 查 找 例例1 1:按如下關(guān)鍵字的插入順序構(gòu)造一棵二叉排序樹:按如下關(guān)鍵字的插入順序構(gòu)造一棵二叉排序樹(4040,1717,5757,0909,5353,2222,898

44、9,3838,1515,4545) 40401717575709095353222289891515383845459 . 2)4443333221 (101)(sucASL查找成功時:查找成功時:4040171757570909535322228989151538384545查找不成功時:查找不成功時:9 . 3)4*63*5(101)(unsucASL第8章 查 找 例例2 2:按如下關(guān)鍵字的插入順序構(gòu)造一棵二叉排序樹:按如下關(guān)鍵字的插入順序構(gòu)造一棵二叉排序樹(1515,5757,0909,5353,8989,4545,4040,2828,2222,1717) 15150909575753

45、53898945454040282822221717查找不成功時:查找不成功時:1 . 5)2*87651*43*32*2(101)(unsucASL查找成功時:查找成功時:1 . 4)8765433221 (101)(sucASL1515090957575353898945454040282822221717第8章 查 找 從以上兩個形狀不同的二叉排序樹能直觀看到:如果在從以上兩個形狀不同的二叉排序樹能直觀看到:如果在關(guān)鍵字不斷插入過程中,樹的形態(tài)始終保持比較勻稱,則平關(guān)鍵字不斷插入過程中,樹的形態(tài)始終保持比較勻稱,則平均查找長度相對較小,反之,如果由于插入一系列的關(guān)鍵字均查找長度相對較小,

46、反之,如果由于插入一系列的關(guān)鍵字而使排序樹沿某一分支畸形生長,則平均查找長度就大,特而使排序樹沿某一分支畸形生長,則平均查找長度就大,特別當(dāng)先后插入的關(guān)鍵字有序時,構(gòu)成的二叉排序樹蛻變?yōu)閱蝿e當(dāng)先后插入的關(guān)鍵字有序時,構(gòu)成的二叉排序樹蛻變?yōu)閱沃?。樹的深度為支樹。樹的深度為n n,其平均查找長度為,其平均查找長度為n+1/2n+1/2,和順序查找,和順序查找相同,這是最差的情況。顯然最好的情況是二叉排序樹的形相同,這是最差的情況。顯然最好的情況是二叉排序樹的形態(tài)和折半查找的判定樹相同,其平均查找長度和態(tài)和折半查找的判定樹相同,其平均查找長度和loglogn n成正比。成正比。因此我們希望二叉排序

47、樹在構(gòu)造過程中始終保持比較勻稱的因此我們希望二叉排序樹在構(gòu)造過程中始終保持比較勻稱的樹形。樹形。 因此含有因此含有n n個結(jié)點的二叉排序樹的平均查找長度和樹的個結(jié)點的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)。形態(tài)有關(guān)。第8章 查 找 在構(gòu)造二叉排序樹的過程中,希望在動態(tài)查找在構(gòu)造二叉排序樹的過程中,希望在動態(tài)查找過程中永遠保持其平衡性(勻稱性),以獲得較好過程中永遠保持其平衡性(勻稱性),以獲得較好的的ASLASL,但又不能苛求輸入的順序,只能人為地改造,但又不能苛求輸入的順序,只能人為地改造樹,即二叉排序樹的動態(tài)調(diào)平衡問題,也就是需要樹,即二叉排序樹的動態(tài)調(diào)平衡問題,也就是需要在構(gòu)成二叉排序樹

48、的過程中進行在構(gòu)成二叉排序樹的過程中進行“平衡化平衡化”處理,處理,稱為平衡二叉樹。稱為平衡二叉樹。 第8章 查 找 8.3.2 8.3.2、平衡二叉樹(、平衡二叉樹(Balanced Binary TreeBalanced Binary Tree) 1 1)定義:)定義:它或者是一棵空樹,或者是具有下列性質(zhì)它或者是一棵空樹,或者是具有下列性質(zhì)的二叉樹:它的左子樹和右子樹都是平衡二叉樹,且的二叉樹:它的左子樹和右子樹都是平衡二叉樹,且左子樹和右子樹的深度之差的絕對值不超過左子樹和右子樹的深度之差的絕對值不超過1 1,又稱,又稱為為AVLAVL樹樹。 平衡因子平衡因子BFBF(Banlance

49、FactorBanlance Factor):):該結(jié)點的左子樹的該結(jié)點的左子樹的深度減去它的右子樹的深度。深度減去它的右子樹的深度。 平衡二叉樹上所有結(jié)點的平衡因子只可能是平衡二叉樹上所有結(jié)點的平衡因子只可能是-1-1、0 0和和1 1。只要二叉樹上有一個結(jié)點的平衡因子的絕對值。只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于大于1 1,則該二叉樹就是不平衡的。,則該二叉樹就是不平衡的。 第8章 查 找 -1-11 1-1-10 00 01 10 0 平衡二叉樹平衡二叉樹 -1-10 0-2-20 001 10 0 不平衡的二叉樹不平衡的二叉樹 第8章 查 找 如何使構(gòu)成的二叉排序樹成為平衡二叉

50、樹?如何使構(gòu)成的二叉排序樹成為平衡二叉樹?第8章 查 找 2) 2) 動態(tài)平衡技術(shù)動態(tài)平衡技術(shù) 如何構(gòu)造出一棵平衡二叉排序樹呢?如何構(gòu)造出一棵平衡二叉排序樹呢?Adelson-Adelson-VelskiiVelskii和和LandisLandis提出了一個動態(tài)地保持二叉排序樹平衡提出了一個動態(tài)地保持二叉排序樹平衡的方法。的方法。 其基本思想是:在構(gòu)造二叉排序樹的過程中,每當(dāng)插其基本思想是:在構(gòu)造二叉排序樹的過程中,每當(dāng)插入一個結(jié)點時,首先檢查是否因插入而破壞了樹的平衡性,入一個結(jié)點時,首先檢查是否因插入而破壞了樹的平衡性,如果是因插入結(jié)點而破壞了樹的平衡性,則找出其中最小如果是因插入結(jié)點而破

51、壞了樹的平衡性,則找出其中最小不平衡子樹,在保持二叉排序樹特性的前提下,調(diào)整不平衡子樹,在保持二叉排序樹特性的前提下,調(diào)整最小最小不平衡子樹不平衡子樹中各結(jié)點之間的連接關(guān)系,以達到新的平衡。中各結(jié)點之間的連接關(guān)系,以達到新的平衡。通常將這樣得到的平衡二叉排序樹簡稱為通常將這樣得到的平衡二叉排序樹簡稱為AVLAVL樹。樹。第8章 查 找 所謂最小不平衡子樹是指以離插入結(jié)點最近、且平所謂最小不平衡子樹是指以離插入結(jié)點最近、且平衡因子絕對值大于衡因子絕對值大于1 1的結(jié)點作根結(jié)點的子樹。的結(jié)點作根結(jié)點的子樹。 為了簡化討論,假設(shè)二叉排序樹的最小不平衡子樹為了簡化討論,假設(shè)二叉排序樹的最小不平衡子樹的

52、根結(jié)點為的根結(jié)點為A A,則調(diào)整該子樹的規(guī)律可歸納為下列四種,則調(diào)整該子樹的規(guī)律可歸納為下列四種情況:情況: 1 1)LLLL型平衡旋轉(zhuǎn)(單向右旋平衡處理)型平衡旋轉(zhuǎn)(單向右旋平衡處理) 2 2)RRRR型平衡旋轉(zhuǎn)(單向左旋平衡處理)型平衡旋轉(zhuǎn)(單向左旋平衡處理) 3 3)LRLR型平衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先左后右)型平衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先左后右) 4 4)RLRL型平衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先右后左)型平衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先右后左) 第8章 查 找 (1) LL(1) LL型平衡旋轉(zhuǎn)(單向右旋平衡處理)型平衡旋轉(zhuǎn)(單向右旋平衡處理) 向右旋轉(zhuǎn),說明左面的子樹高了,需調(diào)整變低一些。由于在向右旋轉(zhuǎn),說明左

53、面的子樹高了,需調(diào)整變低一些。由于在A A的左子樹根結(jié)點的左子樹上插入結(jié)點,的左子樹根結(jié)點的左子樹上插入結(jié)點,A A的平衡因子由的平衡因子由1 1增至增至2 2,致,致使以使以A A為根的子樹失去平衡,則需進行一次向右的順時針旋轉(zhuǎn)操作。為根的子樹失去平衡,則需進行一次向右的順時針旋轉(zhuǎn)操作。圖中帶陰影的小框表示被插入的結(jié)點,長方大框圖中帶陰影的小框表示被插入的結(jié)點,長方大框ALAL,ARAR,BLBL,BRBR,CLCL,CRCR分別表示左、右子樹,虛線下面是平衡因子示意。分別表示左、右子樹,虛線下面是平衡因子示意。 調(diào)整規(guī)則是:將調(diào)整規(guī)則是:將A A的左子樹的左子樹B B提升為新二叉樹的根,將

54、原來的根提升為新二叉樹的根,將原來的根A A連同其右子樹連同其右子樹ARAR順時針方向向右旋轉(zhuǎn),使其成為順時針方向向右旋轉(zhuǎn),使其成為B B的右子樹;而的右子樹;而B B的原右子樹的原右子樹BRBR則作為左子樹接到則作為左子樹接到A A上。上。(a) LL型型100002ABXBXA第8章 查 找 向左旋轉(zhuǎn),說明右面的子樹高了,需調(diào)整變低一些。由于向左旋轉(zhuǎn),說明右面的子樹高了,需調(diào)整變低一些。由于在在A A的右子樹根結(jié)點的右子樹上插入結(jié)點,的右子樹根結(jié)點的右子樹上插入結(jié)點,A A的平衡因子由的平衡因子由-1-1增至增至-2-2,致使以,致使以A A為根的子樹失去平衡,則需進行一次向左為根的子樹失

55、去平衡,則需進行一次向左的逆時針旋轉(zhuǎn)操作。的逆時針旋轉(zhuǎn)操作。 調(diào)整規(guī)則是:將調(diào)整規(guī)則是:將A A的右子樹的右子樹B B提升為新二叉樹的根,將原提升為新二叉樹的根,將原來的根來的根A A連同其左子樹連同其左子樹ALAL逆時針方向向左旋轉(zhuǎn),使其成為逆時針方向向左旋轉(zhuǎn),使其成為B B的的左子樹;而左子樹;而B B的原左子樹的原左子樹BLBL則作為右子樹接到則作為右子樹接到A A上。上。 (2) RR(2) RR型平衡旋轉(zhuǎn)(單向左旋平衡處理)型平衡旋轉(zhuǎn)(單向左旋平衡處理) (b) RRRR型型000102ABXABX第8章 查 找 由于在由于在A A的左子樹根結(jié)點的右子樹上插入結(jié)點,的左子樹根結(jié)點的右

56、子樹上插入結(jié)點,A A的平衡因的平衡因子由子由1 1增至增至2 2,致使以,致使以A A為根結(jié)點的子樹失去平衡,則需進行兩為根結(jié)點的子樹失去平衡,則需進行兩次旋轉(zhuǎn)(先左旋后右旋)操作。次旋轉(zhuǎn)(先左旋后右旋)操作。 調(diào)整規(guī)則是:將調(diào)整規(guī)則是:將A A的孫子結(jié)點的孫子結(jié)點C C提升為二叉樹的根;提升為二叉樹的根;原原C C的雙親的雙親B B連同其左子樹連同其左子樹BLBL向左逆時針旋轉(zhuǎn),使其成為新向左逆時針旋轉(zhuǎn),使其成為新的根結(jié)點的根結(jié)點C C的左子樹,而原的左子樹,而原C C的左子樹的左子樹CLCL則成為則成為B B的右子樹;的右子樹;(3) LR(3) LR型平衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先左后右)型平

57、衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先左后右) 原根原根A A連同其右子樹連同其右子樹ARAR向右順時針旋轉(zhuǎn),使其成為新的根向右順時針旋轉(zhuǎn),使其成為新的根結(jié)點結(jié)點C C的右子樹,而原的右子樹,而原C C的右子樹的右子樹CRCR則成為則成為A A的左子樹。的左子樹。 第8章 查 找 0(c) LRLR型型B B10100212ABXAXBXBA第8章 查 找 由于在由于在A A的右子樹根結(jié)點的左子樹上插入結(jié)點,的右子樹根結(jié)點的左子樹上插入結(jié)點,A A的平衡因的平衡因子由子由-1-1增至增至-2-2,致使以,致使以A A為根結(jié)點的子樹失去平衡,則需進行為根結(jié)點的子樹失去平衡,則需進行兩次旋轉(zhuǎn)(先右旋后左旋)操作。兩

58、次旋轉(zhuǎn)(先右旋后左旋)操作。 調(diào)整規(guī)則是:將調(diào)整規(guī)則是:將A A的孫子結(jié)點的孫子結(jié)點C C提升為二叉樹的根;提升為二叉樹的根;原原C C的雙親的雙親B B連同其右子樹連同其右子樹BRBR向右順時針旋轉(zhuǎn),使其成為新向右順時針旋轉(zhuǎn),使其成為新的根結(jié)點的根結(jié)點C C的右子樹,而原的右子樹,而原C C的右子樹的右子樹CRCR則成為則成為B B的左子樹;的左子樹; (4) RL(4) RL型平衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先右后左)型平衡旋轉(zhuǎn)(雙向旋轉(zhuǎn),先右后左) 原根原根A A連同其左子樹連同其左子樹ALAL向左逆時針旋轉(zhuǎn),使其成為新的根向左逆時針旋轉(zhuǎn),使其成為新的根結(jié)點結(jié)點C C的左子樹,而原的左子樹,而原C

59、C的左子樹的左子樹CLCL則成為則成為A A的右子樹。的右子樹。 A AC CB BALALh-1h-1BRBRh-1h-1CLCLh-1h-1CRCRh-2h-2第8章 查 找 (d) RLRL型型 000-201-210ABXAXBAXB第8章 查 找 (a) LL型型100002ABXBXA(b) RRRR型型000102ABXABX0(c) LRLR型型B B10100212ABXAXBXBA(d) RLRL型型 000-201-210ABXAXBAXB平衡調(diào)整的四種類型簡圖平衡調(diào)整的四種類型簡圖( (結(jié)點旁的數(shù)字是平衡因子結(jié)點旁的數(shù)字是平衡因子) )第8章 查 找 現(xiàn)舉一例說明,設(shè)一

60、組記錄的關(guān)鍵字按以下次序進行現(xiàn)舉一例說明,設(shè)一組記錄的關(guān)鍵字按以下次序進行插入:插入:4 4、5 5、7 7、2 2、1 1、3 3、6 6,其生成及調(diào)整成二叉平衡樹,其生成及調(diào)整成二叉平衡樹的過程示如圖。的過程示如圖。 調(diào)整平衡過程調(diào)整平衡過程插入后插入后輸入結(jié)點輸入結(jié)點4 4不需要調(diào)整不需要調(diào)整4 401 14 45 50 0不需要調(diào)整不需要調(diào)整5 54 42 25 51 17 70 0RRRR型型5 50 07 70 04 40 07 75 51 17 70 04 41 12 20 0不需要調(diào)整不需要調(diào)整2 2第8章 查 找 3 30 05 52 27 74 42 22 20 01 10 00 03 3

溫馨提示

  • 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)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論