數(shù)據(jù)結(jié)構(gòu)查表找實(shí)用教案實(shí)用教案

1、1何謂(hwi)查找表 ？ 查找表是由同一類型的數(shù)據(jù)查找表是由同一類型的數(shù)據(jù)(shj)元素元素(或記錄或記錄)構(gòu)成的集合。構(gòu)成的集合。 由于由于“集合集合”中的數(shù)據(jù)元素之中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此間存在著松散的關(guān)系，因此(ync)查找表是一種應(yīng)用靈便的結(jié)構(gòu)。查找表是一種應(yīng)用靈便的結(jié)構(gòu)。第1頁(yè)/共150頁(yè)第一頁(yè)，共150頁(yè)。2對(duì)查找表經(jīng)常進(jìn)行對(duì)查找表經(jīng)常進(jìn)行(jnxng)(jnxng)的操作的操作: :1. 查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素是否數(shù)據(jù)元素是否在查找表中；在查找表中；2. 檢索某個(gè)檢索某個(gè)“特定的特定的”數(shù)據(jù)元素的各數(shù)據(jù)元素的各種屬性種屬性(shxng)；3. 在

2、查找表中插入一個(gè)數(shù)據(jù)元素；在查找表中插入一個(gè)數(shù)據(jù)元素；4. 從查找表中刪去某個(gè)數(shù)據(jù)元素。從查找表中刪去某個(gè)數(shù)據(jù)元素。第2頁(yè)/共150頁(yè)第二頁(yè)，共150頁(yè)。3僅作僅作 前兩種即查詢和檢索操作的查找表。前兩種即查詢和檢索操作的查找表。即檢索的前后不會(huì)即檢索的前后不會(huì)(b hu)改變查找表的內(nèi)容。改變查找表的內(nèi)容。在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素元素,此類表為動(dòng)態(tài)查找表。即檢索過(guò)程中可能此類表為動(dòng)態(tài)查找表。即檢索過(guò)程中可能會(huì)改變數(shù)據(jù)元素的存儲(chǔ)會(huì)改變數(shù)據(jù)元素的存儲(chǔ)(cn

3、ch)位置。位置。查找表可分為兩類查找表可分為兩類:第3頁(yè)/共150頁(yè)第三頁(yè)，共150頁(yè)。4第4頁(yè)/共150頁(yè)第四頁(yè)，共150頁(yè)。5是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別值，用以標(biāo)識(shí)（識(shí)別(shbi)）一個(gè)數(shù)）一個(gè)數(shù)據(jù)元素（或記錄）。據(jù)元素（或記錄）。 若此關(guān)鍵字可以識(shí)別唯一若此關(guān)鍵字可以識(shí)別唯一(wi y)的的一個(gè)記錄，則稱之謂一個(gè)記錄，則稱之謂“主關(guān)鍵字主關(guān)鍵字”。 若此關(guān)鍵字能識(shí)別若干若此關(guān)鍵字能識(shí)別若干(rugn)記錄，則稱記錄，則稱之謂之謂“次關(guān)鍵字次關(guān)鍵字”。第5頁(yè)/共150頁(yè)第五頁(yè)，共150頁(yè)。6 根據(jù)給定的某個(gè)根據(jù)給定的某個(gè)(mu

4、 )值，在查找表中確值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）（記錄） 查找查找(ch zho) 若查找表中存在這樣一個(gè)記錄，則稱若查找表中存在這樣一個(gè)記錄，則稱“查查找成功找成功(chnggng)”，查找結(jié)果：給出整，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找表中的個(gè)記錄的信息，或指示該記錄在查找表中的位置；位置； 否則稱否則稱“查找不成功查找不成功(chnggng)”，查，查找結(jié)果：給出找結(jié)果：給出“空記錄空記錄”或或“空指針空指針”。第6頁(yè)/共150頁(yè)第六頁(yè)，共150頁(yè)。7如果查找表中的數(shù)據(jù)元素如果查找表中的數(shù)據(jù)元素(yun s

5、)之間之間不存在明顯的組織規(guī)律，則不便于查找。不存在明顯的組織規(guī)律，則不便于查找。 例：查閱英文單詞時(shí)，由于字典是按例：查閱英文單詞時(shí)，由于字典是按單詞的字母在字母表中的次序編排的，單詞的字母在字母表中的次序編排的，因此查找時(shí)不需要從字典中第一個(gè)單詞因此查找時(shí)不需要從字典中第一個(gè)單詞比較起，而只要根據(jù)待查單詞的每個(gè)字比較起，而只要根據(jù)待查單詞的每個(gè)字母在字母表中的位置查到該單詞。母在字母表中的位置查到該單詞。如何進(jìn)行如何進(jìn)行(jnxng)查找？查找？查找的方法取決于查找表的結(jié)構(gòu)。即取決查找的方法取決于查找表的結(jié)構(gòu)。即取決于數(shù)據(jù)元素于數(shù)據(jù)元素(yun s)依何種關(guān)系組織在依何種關(guān)系組織在一起。一

6、起。第7頁(yè)/共150頁(yè)第七頁(yè)，共150頁(yè)。8第8頁(yè)/共150頁(yè)第八頁(yè)，共150頁(yè)。99.1 靜靜 態(tài)態(tài) 查查 找找 表表第9頁(yè)/共150頁(yè)第九頁(yè)，共150頁(yè)。10數(shù)據(jù)數(shù)據(jù)(shj)對(duì)象對(duì)象D：數(shù)據(jù)數(shù)據(jù)(shj)關(guān)系關(guān)系R：D是具有相同特性的數(shù)是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型據(jù)元素含有類型(lixng)相同的相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。據(jù)元素。 數(shù)據(jù)元素同屬一個(gè)集合。數(shù)據(jù)元素同屬一個(gè)集合。ADT StaticSearchTable /P216第10頁(yè)/共150頁(yè)第十頁(yè)，共150頁(yè)。11 Create(&ST, n);Destroy

7、(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P：next ADT StaticSearchTable第11頁(yè)/共150頁(yè)第十一頁(yè)，共150頁(yè)。12構(gòu)造一個(gè)含構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素(yun s)的靜態(tài)查找表的靜態(tài)查找表ST。 Create(&ST, n);操作操作(cozu)結(jié)果：結(jié)果：第12頁(yè)/共150頁(yè)第十二頁(yè)，共150頁(yè)。13銷毀銷毀(xiohu)表表ST。Destroy(&ST);初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：靜態(tài)查找靜態(tài)查找(ch zho)表表ST存在；存在；第13頁(yè)/共150頁(yè)第十三頁(yè)，共15

8、0頁(yè)。14若若 ST 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的數(shù)據(jù)的數(shù)據(jù)(shj)元素，則元素，則函數(shù)值為該元素的值或在表中函數(shù)值為該元素的值或在表中的位置，否則為的位置，否則為“空空”。 Search(ST, key);初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：靜態(tài)靜態(tài)(jngti)查找表查找表ST存在，存在，key 為和查找表中元素的關(guān)為和查找表中元素的關(guān)鍵字類型相同的給定值；鍵字類型相同的給定值；第14頁(yè)/共150頁(yè)第十四頁(yè)，共150頁(yè)。15按某種次序?qū)Π茨撤N次序?qū)T的每個(gè)元的每個(gè)元素素(yun s)調(diào)用函數(shù)調(diào)用函數(shù)Visit()一次且僅一次，一一次且僅一次，一旦旦V

9、isit()失敗，則操作失失敗，則操作失敗。敗。Traverse(ST, Visit();初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：靜態(tài)查找表靜態(tài)查找表ST存在，存在，Visit是對(duì)元素操作是對(duì)元素操作(cozu)的應(yīng)用函數(shù)；的應(yīng)用函數(shù)；第15頁(yè)/共150頁(yè)第十五頁(yè)，共150頁(yè)。16typedef struct / 數(shù)據(jù)數(shù)據(jù)(shj)元素存儲(chǔ)空間基址，建表時(shí)元素存儲(chǔ)空間基址，建表時(shí) / 按實(shí)際長(zhǎng)度分配，按實(shí)際長(zhǎng)度分配，0號(hào)單元留空號(hào)單元留空 int length; / 表的長(zhǎng)度表的長(zhǎng)度 SSTable;假設(shè)靜態(tài)假設(shè)靜態(tài)(jngti)查找表的順序存查找表的順序存儲(chǔ)結(jié)構(gòu)為儲(chǔ)結(jié)構(gòu)為Elem

10、Type *elem;第16頁(yè)/共150頁(yè)第十六頁(yè)，共150頁(yè)。17數(shù)據(jù)元素?cái)?shù)據(jù)元素(yun s)類型的定義為類型的定義為:typedef struct keyType key; / 關(guān)鍵字域 / 其它(qt)屬性域 ElemType ; , TElemType ;第17頁(yè)/共150頁(yè)第十七頁(yè)，共150頁(yè)。18一、順序一、順序(shnx)查找表查找表二、有序查找二、有序查找(ch zho)表表三、索引三、索引(suyn)順序表順序表第18頁(yè)/共150頁(yè)第十八頁(yè)，共150頁(yè)。19 以順序表或線性鏈表表示靜以順序表或線性鏈表表示靜態(tài)查找表。態(tài)查找表。從表的一端開(kāi)始，順序（逐個(gè)）從表的一端開(kāi)始，順序

11、（逐個(gè)）掃描線性表，依次將掃描到的掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值結(jié)點(diǎn)關(guān)鍵字和給定值Key相比相比較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與字與Key相等相等(xingdng)，則檢索成功；若掃描結(jié)束后，則檢索成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于仍未找到關(guān)鍵字等于Key的結(jié)的結(jié)點(diǎn)，則檢索失敗。點(diǎn)，則檢索失敗。 一、順序一、順序(shnx)查找表查找表第19頁(yè)/共150頁(yè)第十九頁(yè)，共150頁(yè)。20i0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找6464監(jiān)視哨iiii比較(bjio)次數(shù)=5比較次數(shù)

12、：查找(ch zho)第n個(gè)元素： 1查找(ch zho)第n-1個(gè)元素：2.查找(ch zho)第1個(gè)元素： n查找(ch zho)第i個(gè)元素： n+1-i查找(ch zho)失?。?n+1查找過(guò)程：從表的一端開(kāi)始逐個(gè)查找過(guò)程：從表的一端開(kāi)始逐個(gè)(zhg)進(jìn)行記錄的關(guān)鍵字和給定值的比較。進(jìn)行記錄的關(guān)鍵字和給定值的比較。例如：例如：第20頁(yè)/共150頁(yè)第二十頁(yè)，共150頁(yè)。2121 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92 05 64 56 80 75 13 0

13、 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64第21頁(yè)/共150頁(yè)第二十一頁(yè)，共150頁(yè)。22int Search_Seq(SSTable ST, KeyType key) / 在順序在順序(shnx)表表ST中順序中順序(shnx)查找其關(guān)鍵字等于查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵哨兵” for (i=ST.length; ST.elemi.key!=k

14、ey; -i); / 從后往前找從后往前找 return i; / 找不到時(shí)，找不到時(shí)，i為為0 / Search_Seq第22頁(yè)/共150頁(yè)第二十二頁(yè)，共150頁(yè)。23 定義：定義： 查找算法的平均查找長(zhǎng)度查找算法的平均查找長(zhǎng)度 (Average Search Length) 也就是為確定某一結(jié)點(diǎn)在數(shù)據(jù)集合中的位置，給定也就是為確定某一結(jié)點(diǎn)在數(shù)據(jù)集合中的位置，給定(i dn)值值與集合中的結(jié)點(diǎn)關(guān)鍵字所需進(jìn)行的比較次數(shù)。與集合中的結(jié)點(diǎn)關(guān)鍵字所需進(jìn)行的比較次數(shù)。其中其中: n 為表長(zhǎng)，為表長(zhǎng)，Pi 為查找表中第為查找表中第i個(gè)記錄的概率，個(gè)記錄的概率， 且且 Ci為找到該記錄時(shí)，曾和給定為找到該

15、記錄時(shí)，曾和給定(i dn)值值 比較過(guò)的關(guān)鍵字的個(gè)數(shù)比較過(guò)的關(guān)鍵字的個(gè)數(shù)分析順序查找分析順序查找(ch zho)的時(shí)間性能。的時(shí)間性能。niiiCPASL111niiP第23頁(yè)/共150頁(yè)第二十三頁(yè)，共150頁(yè)。24在等概率查找的情況在等概率查找的情況(qngkung)下，下， 順序表查找的平均查找長(zhǎng)度為：順序表查找的平均查找長(zhǎng)度為：對(duì)順序?qū)樞?shnx)表而言，表而言，Ci = n-i+1nPi121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+Pn第24頁(yè)/共150頁(yè)第二十四頁(yè)，共150頁(yè)。25 若查找概率無(wú)法若查找概率無(wú)法(wf)事先測(cè)定，事

16、先測(cè)定，則查找過(guò)程采取的改進(jìn)辦法是，可以則查找過(guò)程采取的改進(jìn)辦法是，可以在記錄中附設(shè)一個(gè)訪問(wèn)頻度域，使查在記錄中附設(shè)一個(gè)訪問(wèn)頻度域，使查找概率大的記錄在查找過(guò)程中不斷后找概率大的記錄在查找過(guò)程中不斷后移，以便在以后的查找過(guò)程中減少比移，以便在以后的查找過(guò)程中減少比較次數(shù)較次數(shù)在不等概率在不等概率(gil)查找的情況下，查找的情況下，ASLss 在在 PnPn-1P2P1時(shí)取極小值時(shí)取極小值A(chǔ)SL = nP1 +(n-1)P2 + +2Pn-1+Pn第25頁(yè)/共150頁(yè)第二十五頁(yè)，共150頁(yè)。26 上述順序上述順序(shnx)查找表的查找算法簡(jiǎn)單，查找表的查找算法簡(jiǎn)單， 但平均查找長(zhǎng)度較大，特別

17、不適用于表長(zhǎng)較大的查找表。但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表。二、有序查找二、有序查找(ch zho)表表 若以有序表表示靜態(tài)若以有序表表示靜態(tài)(jngti)查找表，則查找過(guò)程可以基于查找表，則查找過(guò)程可以基于“折半折半”進(jìn)行。進(jìn)行。第26頁(yè)/共150頁(yè)第二十六頁(yè)，共150頁(yè)。271.設(shè)表長(zhǎng)為設(shè)表長(zhǎng)為n，low、high和和mid分別指向待分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn)查元素所在區(qū)間的上界、下界和中點(diǎn),k為給為給定值。定值。2.初始時(shí)，令初始時(shí)，令low=1,high=n,mid=(low+high)/2讓讓k與與mid指向的記錄比較指向的記錄比較若若k=rmid.k

18、ey，查找成功，查找成功(chnggng)若若krmid.key，則，則low=mid+13.重復(fù)上述操作，直至重復(fù)上述操作，直至lowhigh時(shí)，查找失時(shí)，查找失敗。敗。折半折半(zhbn)查找算查找算法實(shí)現(xiàn)法實(shí)現(xiàn)第27頁(yè)/共150頁(yè)第二十七頁(yè)，共150頁(yè)。2805 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找的查找(ch zho)過(guò)程如下過(guò)程如下lowhighmidlow mid high midlow 指示查找指示查找(ch zho)區(qū)間的下界區(qū)間的下界;h

19、igh 指示查找指示查找(ch zho)區(qū)間的上界區(qū)間的上界;mid = (low+high)/2。第28頁(yè)/共150頁(yè)第二十八頁(yè)，共150頁(yè)。29int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值置區(qū)間初值 while (low 50時(shí)，可得近似時(shí)，可得近似(jn s)結(jié)果結(jié)果 一般情況下，表長(zhǎng)為一般情況下，表長(zhǎng)為 n 的折半查的折半查找的判定樹的深度和含有找的判定樹的深度和含有 n 個(gè)結(jié)個(gè)結(jié)點(diǎn)點(diǎn)(ji din)的完全二叉樹的深度的完全二叉樹的深度相同。因此具有相同。因此具有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)

20、(ji din)的判定樹的深度為的判定樹的深度為 +1。為了方便起見(jiàn)，以滿二叉樹為例，為了方便起見(jiàn)，以滿二叉樹為例，樹中層次為樹中層次為1的結(jié)點(diǎn)的結(jié)點(diǎn)(ji din)有有1個(gè)，層次為個(gè)，層次為2的結(jié)點(diǎn)的結(jié)點(diǎn)(ji din)有有2個(gè)，層次為個(gè)，層次為h的結(jié)點(diǎn)的結(jié)點(diǎn)(ji din)有有2h1個(gè)個(gè).n2log1) 1(log2nASLbs1) 1(log1) 1(log12111),1(log, 122211112nnnnjncncpASLnphnhnhjjniiniiiih則：概率相等設(shè)表中每個(gè)記錄的查找的滿二叉樹即判定樹是深度為設(shè)表長(zhǎng)第31頁(yè)/共150頁(yè)第三十一頁(yè)，共150頁(yè)。32在在 n50

21、時(shí)，可得近似時(shí)，可得近似(jn s)結(jié)果結(jié)果 1) 1(log2nASLbs可見(jiàn)，可見(jiàn)，折半折半(zhbn)查找的效率比順序查找高。查找的效率比順序查找高。折半折半(zhbn)查找只能適用于有序表，并且以查找只能適用于有序表，并且以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。第32頁(yè)/共150頁(yè)第三十二頁(yè)，共150頁(yè)。33順序表順序表有序表有序表表的特性表的特性無(wú)序無(wú)序有序有序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序順序 或或 鏈?zhǔn)芥準(zhǔn)巾樞蝽樞虿鍎h操作插刪操作易于進(jìn)行易于進(jìn)行需移動(dòng)元素需移動(dòng)元素ASL的值的值大大小小順序順序(shnx)表和有序表和有序表的比較表的比較第33頁(yè)/共150頁(yè)第三十三頁(yè)，共150頁(yè)。34三、索

22、引三、索引(suyn)順序表順序表以索引順序以索引順序(shnx)(shnx)表表示靜態(tài)查表表示靜態(tài)查找表，找表，searchsearch操作可用分塊查找來(lái)實(shí)操作可用分塊查找來(lái)實(shí)現(xiàn)。現(xiàn)。分塊查找又稱索引順序分塊查找又稱索引順序(shnx)(shnx)查查找，這是順序找，這是順序(shnx)(shnx)查找的一種查找的一種改進(jìn)方法。在此查找方法中，除表本改進(jìn)方法。在此查找方法中，除表本身以外，尚需建立一個(gè)身以外，尚需建立一個(gè)“索引表索引表”。第34頁(yè)/共150頁(yè)第三十四頁(yè)，共150頁(yè)。35例如(lr(lr) 表中含有1818個(gè)元素(yun s)(yun s)，可分成三個(gè)子表。對(duì)每個(gè)子表（或稱塊）

23、建立一個(gè)索引項(xiàng)，其中包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)（其值為該子表內(nèi)的最大關(guān)鍵字）和項(xiàng)指針（指示該子表的第一個(gè)元素(yun s)(yun s)在表中位置）。 索 引 表 最大關(guān)鍵字起始(q sh)地址 22 48 8617 13221213 8 9 20334244382448605874498653第35頁(yè)/共150頁(yè)第三十五頁(yè)，共150頁(yè)。36 索引表按關(guān)鍵字有序，故表或者有序，或者分塊有序。所謂(suwi)(suwi)“分塊有序” 是指一個(gè)子表中所有元素的關(guān)鍵字均大于前一個(gè)子表的最大關(guān)鍵字。 第36頁(yè)/共150頁(yè)第三十六頁(yè)，共150頁(yè)。37索引順序索引順序(shnx)表的查找過(guò)程：表的查找過(guò)程：1

24、）由索引確定）由索引確定(qudng)記錄所在區(qū)間；記錄所在區(qū)間；2）在順序）在順序(shnx)表的某個(gè)區(qū)間內(nèi)進(jìn)行查找。表的某個(gè)區(qū)間內(nèi)進(jìn)行查找。注意：索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造。注意：索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造?？梢?jiàn)，可見(jiàn)， 索引順序查找索引順序查找的過(guò)程也是一個(gè)的過(guò)程也是一個(gè)“縮小區(qū)間縮小區(qū)間”的查找過(guò)程。的查找過(guò)程。第37頁(yè)/共150頁(yè)第三十七頁(yè)，共150頁(yè)。381 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引

25、(suyn)表查38例如例如(lr)第38頁(yè)/共150頁(yè)第三十八頁(yè)，共150頁(yè)。39索引順序索引順序(shnx)查找的平均查找長(zhǎng)度查找的平均查找長(zhǎng)度 = 查找查找“索引索引”的平均查找長(zhǎng)度的平均查找長(zhǎng)度 + 查找查找“順序順序(shnx)表表”的平均查的平均查找長(zhǎng)度找長(zhǎng)度第39頁(yè)/共150頁(yè)第三十九頁(yè)，共150頁(yè)。40分塊查找方法分塊查找方法(fngf)評(píng)價(jià)評(píng)價(jià)121)(21212111)1( 211ssnssnsbisjbASLsbnLLLLASLsibjbswbwbbs：用順序查找確定所在塊率相等，則：表中每個(gè)記錄的查找概個(gè)記錄，并設(shè)塊，每塊含的表平均分成若將表長(zhǎng)為查找長(zhǎng)度在塊中查找元素的

26、平均的平均查找長(zhǎng)度查找索引表確定所在塊其中：ns n第40頁(yè)/共150頁(yè)第四十頁(yè)，共150頁(yè)。41查找方法查找方法(fngf)比較比較ASL最大最大最小最小兩者之間兩者之間表結(jié)構(gòu)表結(jié)構(gòu)有序表、無(wú)序表有序表、無(wú)序表有序表有序表分塊有序表分塊有序表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或線性鏈表或線性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或線性鏈表或線性鏈表順序順序(shnx)查找查找折半折半(zhbn)查找查找 分塊查找分塊查找第41頁(yè)/共150頁(yè)第四十一頁(yè)，共150頁(yè)。429.2 動(dòng)動(dòng) 態(tài)態(tài) 查查 找找 表表第42頁(yè)/共150頁(yè)第四十二頁(yè)，共150頁(yè)。43動(dòng)態(tài)查找表的特點(diǎn)動(dòng)態(tài)查

27、找表的特點(diǎn):表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成。表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成。若表中存在其關(guān)鍵字等于給定值若表中存在其關(guān)鍵字等于給定值key的記錄的記錄,表明查找成功表明查找成功(chnggng)；否則插入關(guān)鍵字等于；否則插入關(guān)鍵字等于key的記錄。的記錄。第43頁(yè)/共150頁(yè)第四十三頁(yè)，共150頁(yè)。44ADT DynamicSearchTable 抽象數(shù)據(jù)類型動(dòng)態(tài)抽象數(shù)據(jù)類型動(dòng)態(tài)(dngti)查找表的定義如下：查找表的定義如下：數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象(duxing)D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 數(shù)據(jù)元素同屬數(shù)據(jù)元素同屬(tn sh)一個(gè)集合。一個(gè)集合。D是具有相同特性的數(shù)據(jù)是具有相同特性的數(shù)據(jù)元素的

28、集合。元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字，的關(guān)鍵字， 可唯一標(biāo)識(shí)數(shù)可唯一標(biāo)識(shí)數(shù)據(jù)元素。據(jù)元素。第44頁(yè)/共150頁(yè)第四十四頁(yè)，共150頁(yè)。45InitDSTable(&DT)/構(gòu)造一個(gè)空的動(dòng)態(tài)查找構(gòu)造一個(gè)空的動(dòng)態(tài)查找表表DT。DestroyDSTable(&DT)/銷毀動(dòng)態(tài)查找表銷毀動(dòng)態(tài)查找表DT。SearchDSTable(DT, key);/查找查找 DT 中與中與關(guān)鍵字關(guān)鍵字key等值的元素。等值的元素。InsertDSTable(&DT, e);/若若 DT 中不存在中不存在其關(guān)鍵字等于其關(guān)鍵字等于 e.key 的的 數(shù)據(jù)元素，則插入數(shù)據(jù)元素，則插入

29、e 到到 DT。DeleteDSTable(&T, key);/刪除刪除DT中關(guān)鍵中關(guān)鍵字等于字等于key的數(shù)據(jù)元素。的數(shù)據(jù)元素。TraverseDSTable(DT, Visit();/按某種次按某種次序序(cx)對(duì)對(duì)DT的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) Visit() 一次且至多一次。一次且至多一次?；静僮鳎夯静僮鳎簄extADT DynamicSearchTable第45頁(yè)/共150頁(yè)第四十五頁(yè)，共150頁(yè)。46一、二叉排序一、二叉排序(pi x)樹（二叉查找樹）樹（二叉查找樹）二、二叉平衡二、二叉平衡(pnghng)樹樹三、三、B - 樹樹四、四、B+樹樹第46頁(yè)/共150頁(yè)第

30、四十六頁(yè)，共150頁(yè)。47一、二叉排序一、二叉排序(pi x)樹樹（二叉查找樹）（二叉查找樹）1定義定義(dngy)2查找查找(ch zho)算法算法3插入算法插入算法4刪除算法刪除算法5查找性能的分析查找性能的分析第47頁(yè)/共150頁(yè)第四十七頁(yè)，共150頁(yè)。48（1）若它的左子樹不空，則左子樹上）若它的左子樹不空，則左子樹上 所有所有(suyu)結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1定義定義(dngy)： 二叉排序二叉排序(pi x)樹或者是一棵空樹；或者樹或者是一棵空樹；或者是具有如下特性的二叉樹：是具有如下特性的二叉樹：（3）它的左、右子樹）它的左、右子樹也都也都分別分別

31、是二叉是二叉 排序樹排序樹。（2）若它的右子樹不空，則右子樹上）若它的右子樹不空，則右子樹上 所有所有結(jié)點(diǎn)的值結(jié)點(diǎn)的值均大于均大于根結(jié)點(diǎn)的值；根結(jié)點(diǎn)的值；第48頁(yè)/共150頁(yè)第四十八頁(yè)，共150頁(yè)。49503080209010854035252388例如例如(lr):是二叉排序是二叉排序(pi x)樹樹66不不第49頁(yè)/共150頁(yè)第四十九頁(yè)，共150頁(yè)。50 通常，取二叉鏈表作為通常，取二叉鏈表作為二叉排序二叉排序(pi x)樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) struct BiTNode *lchild, *rchild; / 左右孩子(hi

32、zi)指針 BiTNode, *BiTree;TElemType data;第50頁(yè)/共150頁(yè)第五十頁(yè)，共150頁(yè)。511）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；則查找成功；2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)則繼續(xù)(jx)在左子樹上進(jìn)行查找；在左子樹上進(jìn)行查找；3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)則繼續(xù)(jx)在右子樹上進(jìn)行查找。在右子樹上進(jìn)行查找。否則否則(fuz)若二叉排序樹若二叉排序樹為空為空，則查找不成功；，則查找不成功；第51頁(yè)/共150頁(yè)第五十一頁(yè)，共150頁(yè)。52503080209

33、08540358832例如例如(lr):二叉排序二叉排序(pi x)樹樹查找查找(ch zho)關(guān)鍵字關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 第52頁(yè)/共150頁(yè)第五十二頁(yè)，共150頁(yè)。53從上述查找從上述查找(ch zho)過(guò)程可見(jiàn)，過(guò)程可見(jiàn)，在查找過(guò)程在查找過(guò)程(guchng)中，生成了一條查找路徑中，生成了一條查找路徑: 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于層向下直至關(guān)鍵字等于(dngy)給定值的給定值的結(jié)點(diǎn)結(jié)點(diǎn);或者或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直

34、至指針指向空樹為止。逐層向下直至指針指向空樹為止。 查找成功查找成功 查找不成功查找不成功第53頁(yè)/共150頁(yè)第五十三頁(yè)，共150頁(yè)。54BiTree SearchBST( BiTree T, KeyType key) /在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字 /等于Key的數(shù)據(jù)元素，若查找成功(chnggng)，則返回指向 /該數(shù)據(jù)元素的指針，否則返回空指針 if (!T)| EQ(key, T-data.key) return (T);/查找結(jié)束 else if LT(key, T-data.key) return(SearchBST(T-lchild, key) else retu

35、rn (SearchBST(T-rchild, key); /SearchBST第54頁(yè)/共150頁(yè)第五十四頁(yè)，共150頁(yè)。55二叉排序樹是一種動(dòng)態(tài)樹表，其特點(diǎn)二叉排序樹是一種動(dòng)態(tài)樹表，其特點(diǎn)(tdin)是，樹的結(jié)構(gòu)通常不是一次生成是，樹的結(jié)構(gòu)通常不是一次生成的，而是在查找的過(guò)程中，當(dāng)樹中不存在的，而是在查找的過(guò)程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)進(jìn)行插入。關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。的最后一個(gè)結(jié)點(diǎn)的左孩

36、子或右孩子結(jié)點(diǎn)。為此將二叉樹的查找算法改為如下算法為此將二叉樹的查找算法改為如下算法第55頁(yè)/共150頁(yè)第五十五頁(yè)，共150頁(yè)。56算法描述算法描述(mio sh)如下：如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹中遞歸地查找所指二叉排序樹中遞歸地查找其其 / 關(guān)鍵字等于關(guān)鍵字等于 key 的數(shù)據(jù)元素，若查找成功，的數(shù)據(jù)元素，若查找成功， / 則返回指針則返回指針 p 指向指向(zh xin)該數(shù)據(jù)元素該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回的結(jié)點(diǎn)，并返回 / 函數(shù)值為函數(shù)值為 TR

37、UE; / SearchBST 否則否則(fuz)表明查找不成功，返回表明查找不成功，返回 / 指針指針 p 指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)， / 并返回函數(shù)值為并返回函數(shù)值為FALSE, 指針指針 f 指向當(dāng)前訪問(wèn)指向當(dāng)前訪問(wèn) / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULL第56頁(yè)/共150頁(yè)第五十六頁(yè)，共150頁(yè)。5730201040352523fT設(shè)設(shè) key = 48fTfT22pfTfTTTTfffp第57頁(yè)/共150頁(yè)第五十七頁(yè)，共150頁(yè)。58if (!T)else if ( EQ(key, T-data.key) ) e

38、lse if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找查找(ch zho)不成功不成功 p = T; return TRUE; / 查找查找(ch zho)成功成功SearchBST (T-lchild, key, T, p ); / 在左子樹中繼續(xù)在左子樹中繼續(xù)(jx)查找查找SearchBST (T-rchild, key, T, p ); / 在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / SearchB

39、ST第58頁(yè)/共150頁(yè)第五十八頁(yè)，共150頁(yè)。59根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作(cozu)在查找不成功時(shí)才進(jìn)行;3二叉排序二叉排序(pi x)樹的樹的插入算法插入算法 若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過(guò)程(guchng)得到。第59頁(yè)/共150頁(yè)第五十九頁(yè)，共150頁(yè)。60303020302040302040103020401025302040102545第60頁(yè)/共150頁(yè)第六十頁(yè)，共150頁(yè)。61第61頁(yè)/共150頁(yè)第六十一頁(yè)，共150頁(yè)。62Status Insert BST(BiTree &T, ElemT

40、ype e ) if (!SearchBST ( T, e.key, NULL, p ) s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點(diǎn)為新結(jié)點(diǎn) 分配空間分配空間(kngjin)s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入插入 s 為新的根結(jié)點(diǎn)為新的根結(jié)點(diǎn)else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入插入 *s 為為 *p 的的左孩子左孩子else p-rchild = s; / 插入插入 *s 為為 *p 的右的右

41、孩子孩子return TRUE; / 插入成功插入成功 else return FALSE; / Insert BST第62頁(yè)/共150頁(yè)第六十二頁(yè)，共150頁(yè)。63（1）被刪除的結(jié)點(diǎn)是葉子；）被刪除的結(jié)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有）被刪除的結(jié)點(diǎn)只有(zhyu)左子樹或者只有左子樹或者只有(zhyu)右子樹；右子樹；（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。可分三種情況可分三種情況(qngkung)討論：討論： 和插入相反，刪除在和插入相反，刪除在查找成功查找成功之后進(jìn)行，并且之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，要求在刪除二叉排序樹上某個(gè)

42、結(jié)點(diǎn)之后，仍然保仍然保持二叉排序樹的特性持二叉排序樹的特性。第63頁(yè)/共150頁(yè)第六十三頁(yè)，共150頁(yè)。6450308020908540358832（1）被刪除的結(jié)點(diǎn)）被刪除的結(jié)點(diǎn)(ji din)是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn)(ji din)例如例如(lr):被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針其雙親結(jié)點(diǎn)中相應(yīng)指針(zhzhn)域的值改為域的值改為“空空”第64頁(yè)/共150頁(yè)第六十四頁(yè)，共150頁(yè)。6550308020908540358832（2）被刪的結(jié)點(diǎn)）被刪的結(jié)點(diǎn)(ji din)只有左子樹或只有只有左子樹或只有右子樹右子樹 其雙親其雙親(shungqn)結(jié)點(diǎn)的相應(yīng)指針域結(jié)點(diǎn)的相應(yīng)

43、指針域的值改為的值改為 “指向被刪除結(jié)點(diǎn)的左子樹或右指向被刪除結(jié)點(diǎn)的左子樹或右子樹子樹”。被刪關(guān)鍵字被刪關(guān)鍵字 = 4080第65頁(yè)/共150頁(yè)第六十五頁(yè)，共150頁(yè)。6650308020908540358832（3）被刪除）被刪除(shnch)的結(jié)點(diǎn)既有左子樹，也有右子樹的結(jié)點(diǎn)既有左子樹，也有右子樹4040按中序遍歷寫出序列，按中序遍歷寫出序列， 以被刪結(jié)點(diǎn)其前驅(qū)以被刪結(jié)點(diǎn)其前驅(qū)(qinq)替代之，然后再刪除該前驅(qū)替代之，然后再刪除該前驅(qū)(qinq)結(jié)結(jié)點(diǎn)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)(ji din)前驅(qū)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字被刪關(guān)鍵字 = 50第66頁(yè)/共150頁(yè)第六十六頁(yè)，共150頁(yè)。67第67頁(yè)/

44、共150頁(yè)第六十七頁(yè)，共150頁(yè)。68Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序樹若二叉排序樹 T 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的的 / 數(shù)據(jù)元素?cái)?shù)據(jù)元素(yun s)，則刪除該數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素(yun s)結(jié)點(diǎn)，并返回結(jié)點(diǎn)，并返回 / 函數(shù)值函數(shù)值 TRUE，否則返回函數(shù)值，否則返回函數(shù)值 FALSE if (!T) return FALSE; else / DeleteBST算法算法(sun f)描述如下：描述如下：(p230) 第68頁(yè)/共150頁(yè)第六十八頁(yè)，共150頁(yè)。69if ( EQ (key,

45、T-data.key) ) / 找到關(guān)鍵字等于找到關(guān)鍵字等于key的數(shù)據(jù)的數(shù)據(jù)(shj)元素元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 繼續(xù)繼續(xù)(jx)在左子樹中進(jìn)行查找在左子樹中進(jìn)行查找DeleteBST ( T-rchild, key ); / 繼續(xù)繼續(xù)(jx)在右子樹中進(jìn)行查找在右子樹中進(jìn)行查找第69頁(yè)/共150頁(yè)第六十九頁(yè)，共150頁(yè)。70void Delete ( BiTree &p ) / 從二叉排序從二叉排序(pi x)樹中刪除結(jié)樹中

46、刪除結(jié)點(diǎn)點(diǎn) p， / 并重接它的左子樹或右子樹并重接它的左子樹或右子樹 if (!p-rchild) else if (!p-lchild) else / Delete其中刪除操作過(guò)程如下其中刪除操作過(guò)程如下(rxi)所描述：所描述： 第70頁(yè)/共150頁(yè)第七十頁(yè)，共150頁(yè)。71 / 右子樹為空樹則只需重接它的左子樹右子樹為空樹則只需重接它的左子樹q = p; p = p-lchild; free(q); pq第71頁(yè)/共150頁(yè)第七十一頁(yè)，共150頁(yè)。72/ 左子樹為空樹只需重接它的右子樹左子樹為空樹只需重接它的右子樹q = p; p = p-rchild; free(q);pq第72頁(yè)/

47、共150頁(yè)第七十二頁(yè)，共150頁(yè)。73q = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)指向被刪結(jié)點(diǎn)(ji din)的前驅(qū)的前驅(qū)/ 左右左右(zuyu)子樹均不空子樹均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接重接*q的左子樹的左子樹free(s);第73頁(yè)/共150頁(yè)第七十三頁(yè)，共150頁(yè)。74 對(duì)于每一棵特定的二叉排序樹，均可按照平均查找對(duì)于每一棵特定的二叉排序樹，均可按照平均查找(c

48、h zho)長(zhǎng)度的定義來(lái)求它的長(zhǎng)度的定義來(lái)求它的 ASL 值，顯然，由值相同的值，顯然，由值相同的 n 個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找找(ch zho)長(zhǎng)長(zhǎng) 度的值不同，甚至可能差別很大。度的值不同，甚至可能差別很大。第74頁(yè)/共150頁(yè)第七十四頁(yè)，共150頁(yè)。75由關(guān)鍵字序列由關(guān)鍵字序列(xli) 3，1，2，5，4構(gòu)造而得的二叉排序樹構(gòu)造而得的二叉排序樹由關(guān)鍵字序列由關(guān)鍵字序列(xli) 1，2，3，4，5構(gòu)造而得的二叉排序樹，構(gòu)造而得的二叉排序樹，例如例如(lr)：2134535412ASL =（1+2+3+4+

49、5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2第75頁(yè)/共150頁(yè)第七十五頁(yè)，共150頁(yè)。76第76頁(yè)/共150頁(yè)第七十六頁(yè)，共150頁(yè)。77101iiicp310/ )3443221 (第77頁(yè)/共150頁(yè)第七十七頁(yè)，共150頁(yè)。78二、二叉平衡(pnghng)樹何謂何謂(hwi)“二叉平衡二叉平衡樹樹”？ 如何構(gòu)造如何構(gòu)造(guzo)“二叉平衡二叉平衡樹樹”第78頁(yè)/共150頁(yè)第七十八頁(yè)，共150頁(yè)。79是平衡二叉樹，不是(b shi)完全二叉樹不是(b shi)平衡二叉樹第79頁(yè)/共150頁(yè)第七十九頁(yè)，共150頁(yè)。80 二叉平衡樹是二叉查找樹的另一種(y zhn)形

50、式，其特點(diǎn)為：樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差（平衡因子BF）的絕對(duì)值不大于1 1RLhh例如例如(lr):548254821是平衡是平衡(pnghng)樹樹不是平衡樹不是平衡樹平衡二叉樹平衡二叉樹BF值011001220失去平衡的最小子樹第80頁(yè)/共150頁(yè)第八十頁(yè)，共150頁(yè)。81v 構(gòu)造二叉平衡（查找）樹的方法：v在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)(jsh)。v例如:依次插入的關(guān)鍵字為5, 4, 3, 8, 19,1,2，25，2354543BF值10102（1）由于插入節(jié)點(diǎn)3使得樹不再平衡，而3是插入在失去平衡的最小子樹根節(jié)點(diǎn)5的左子樹根節(jié)點(diǎn)4的左子樹上。定義(dngy)失去平衡的最小子樹

51、根節(jié)點(diǎn)為a，則該類不平衡可歸納為，在a的左子樹根節(jié)點(diǎn)的左子樹上插入導(dǎo)致的不平衡可使用單向右旋平衡處理，可以記為左左-右。543000第81頁(yè)/共150頁(yè)第八十一頁(yè)，共150頁(yè)。82435843584358190-10-100-1-2-24358190000-1（2）由于插入節(jié)點(diǎn)19使得樹不再平衡，而19是插入在失去平衡的最小子樹根節(jié)點(diǎn)5的右子樹根節(jié)點(diǎn)8的右子樹上。該類不平衡可歸納為，在a的右子樹根節(jié)點(diǎn)的右子樹上插入導(dǎo)致的不平衡可使用單向(dn xin)左旋平衡處理，可以記為右右-左。第82頁(yè)/共150頁(yè)第八十二頁(yè)，共150頁(yè)。83458190003211-1204581900032121104

52、58190003002010先向左旋(zu xun)再向右旋（3）在3的左子樹根節(jié)點(diǎn)(ji din)1的右子樹上插入節(jié)點(diǎn)(ji din)2導(dǎo)致不平衡，可使用雙向旋轉(zhuǎn)：先使其子樹左旋再整棵樹右旋，可記為左右-左右。第83頁(yè)/共150頁(yè)第八十三頁(yè)，共150頁(yè)。8445819-2-2030-2201025231045819-2-2030-220102325-10先向右旋458230-1030-12010251900再向左旋(zu xun)（4）在19的右子樹根節(jié)點(diǎn)25的左子樹上插入(ch r)節(jié)點(diǎn)23導(dǎo)致不平衡，可使用雙向旋轉(zhuǎn)：先使其子樹右旋再整棵樹左旋，可記為右左-右左。第84頁(yè)/共150頁(yè)第八十

53、四頁(yè)，共150頁(yè)。85 構(gòu)造二叉平衡（查找）樹的方法構(gòu)造二叉平衡（查找）樹的方法(fngf)是：是：在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)。在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)。例如例如(lr):依次插入的關(guān)鍵字為依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)向右旋轉(zhuǎn)(xunzhun)一次一次先向右旋轉(zhuǎn)先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)再向左旋轉(zhuǎn)第85頁(yè)/共150頁(yè)第八十五頁(yè)，共150頁(yè)。86426589642895向左旋轉(zhuǎn)(xunzhun)一次繼續(xù)繼續(xù)(jx)插入關(guān)鍵插入關(guān)鍵字字 9第86頁(yè)/共150頁(yè)第八十六頁(yè)，共150頁(yè)。87單向(dn xin)右旋轉(zhuǎn)A2B1BLBrArhhh

54、LL型A0B0BLBrArhhh旋轉(zhuǎn)(xunzhun)后保證中序序列不變第87頁(yè)/共150頁(yè)第八十七頁(yè)，共150頁(yè)。88A-2B-1BrBLALhhhRR型A0B0BrALBLhhh旋轉(zhuǎn)(xunzhun)后保證中序序列不變單向(dn xin)左旋轉(zhuǎn)第88頁(yè)/共150頁(yè)第八十八頁(yè)，共150頁(yè)。89雙向旋轉(zhuǎn)(xunzhun)，先左后右A2B-1ArhBLhLR型CCLh-1Crh-11A-1B0ArhBLhCLh-1Crh-1C0第89頁(yè)/共150頁(yè)第八十九頁(yè)，共150頁(yè)。90雙向旋轉(zhuǎn)(xunzhun)，先右后左B-1A0BrhALhCLh-1Crh-1C0A-2B1BrhALhRL型CLh-1C

55、rh-1C1第90頁(yè)/共150頁(yè)第九十頁(yè)，共150頁(yè)。911200120180012028013001200800300120180-1300900120180030-1900450120180030-290045-16001201800300900450600第91頁(yè)/共150頁(yè)第九十一頁(yè)，共150頁(yè)。92三、三、 B - 樹樹1定義定義(dngy)2查找查找(ch zho)過(guò)程過(guò)程3插入插入(ch r)操作操作4刪除操作刪除操作第92頁(yè)/共150頁(yè)第九十二頁(yè)，共150頁(yè)。93B-B-樹：一種平衡的多路查找樹樹：一種平衡的多路查找樹, ,一棵一棵m m階的階的B-B-樹或?yàn)榭諛?，樹或?yàn)榭諛洌?/p>

56、或?yàn)闈M足下列特性的或?yàn)闈M足下列特性的m m叉樹：叉樹：樹中每個(gè)節(jié)點(diǎn)至多樹中每個(gè)節(jié)點(diǎn)至多(zhdu)(zhdu)有有m m棵子樹棵子樹若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2m/2 棵子樹棵子樹所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,Kn,An)(n,A0,K1,A1,K2,A2,Kn,An) 其中其中Ki(i=1,n)Ki(i=1,n)為關(guān)鍵字，且為關(guān)鍵字，且KiKi+1,(i=1,n-1); KiKi+1,(i=1,n-

57、1); Aj Aj（0 0j jn n）為指向子樹根結(jié)點(diǎn)的指針，且）為指向子樹根結(jié)點(diǎn)的指針，且AjAj（0 0jnjn） 所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小kj+1; Ankj+1; An所指子樹中所指子樹中 所有結(jié)點(diǎn)的關(guān)鍵字均大于所有結(jié)點(diǎn)的關(guān)鍵字均大于kn;kn; n n（m/2m/2-1-1n nm-1m-1）為關(guān)鍵字的個(gè)數(shù)；）為關(guān)鍵字的個(gè)數(shù)；n+1n+1為子樹個(gè)為子樹個(gè)數(shù)。數(shù)。第93頁(yè)/共150頁(yè)第九十三頁(yè)，共150頁(yè)。941351182437811112713934753641994階B-樹，每個(gè)節(jié)點(diǎn)(ji din)最多4棵子樹，3個(gè)關(guān)鍵字。一棵m階B-樹每個(gè)

58、節(jié)點(diǎn)(ji din)最多有m棵子樹m-1個(gè)關(guān)鍵字,最少有m/2棵子樹m/2-1個(gè)關(guān)鍵字第94頁(yè)/共150頁(yè)第九十四頁(yè)，共150頁(yè)。95 非葉結(jié)點(diǎn)中的多個(gè)非葉結(jié)點(diǎn)中的多個(gè)(du (du )關(guān)鍵字均關(guān)鍵字均自小至大有序排列，即：自小至大有序排列，即：K1 K2 K1 K2 Kn;key1.keynum中查找(ch zho) i ，i使 得：p-Keyi=kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的雙親，在子樹中查找(ch zho) if (found) return (p,i,1); / 查找(ch zh

59、o)成功 else return (q,i,0); / 查找(ch zho)不成功 Search (Btree P , KeyType K) for (int i=0; iPkeynum &P keyi+1=k; i+); return i;第102頁(yè)/共150頁(yè)第一百零二頁(yè)，共150頁(yè)。1033插入插入(ch r)1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm， 不修改指針(zhzhn); 例如在查找不成功之后，需進(jìn)行插入(ch r)。顯然，關(guān)鍵字插入(ch r)的位置必定在最下層的非葉結(jié)點(diǎn)，有下列幾種情況：第103頁(yè)/共150頁(yè)第一百零三頁(yè)，共150頁(yè)。1042）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)）插入后，該

60、結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) n=m， 則需進(jìn)行則需進(jìn)行“結(jié)點(diǎn)分裂結(jié)點(diǎn)分裂”，令，令 s = m/2， 在原結(jié)點(diǎn)中保留在原結(jié)點(diǎn)中保留 （A0，K1，。，。， Ks-1，As-1）；）； 建新結(jié)點(diǎn)建新結(jié)點(diǎn) （As，Ks+1，。，。 ，Kn，An）；）； 將（將（Ks，p）插入雙親）插入雙親(shungqn)結(jié)點(diǎn)；例如結(jié)點(diǎn)；例如3）若雙親為空，則建新的根結(jié)點(diǎn)）若雙親為空，則建新的根結(jié)點(diǎn)(ji din)。 例如例如第104頁(yè)/共150頁(yè)第一百零四頁(yè)，共150頁(yè)。105例如例如(lr):下列為下列為 3 階階B-樹樹50 20 40 80 插入插入(ch r)關(guān)鍵字關(guān)鍵字 = 60, 60 80 90, 60 8