數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容講義

1、數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容講義28.1 8.1 基本概念基本概念8.2 8.2 靜態(tài)查找表靜態(tài)查找表8.3 8.3 動(dòng)態(tài)查找表動(dòng)態(tài)查找表8.4 8.4 教材第教材第8 8、1111和和1212章省略，因章省略，因操作系統(tǒng)操作系統(tǒng)課程會(huì)涉及。課程會(huì)涉及。3若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找表 查查 找找查找成功查找成功查找不成功查找不成功靜態(tài)查找靜態(tài)查找動(dòng)態(tài)查找動(dòng)態(tài)查找關(guān)鍵字關(guān)鍵字主關(guān)鍵字主關(guān)鍵字次關(guān)鍵字次關(guān)鍵字由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)

2、成的集合。由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查詢查詢(Searching)特定元素是否在表中。特定元素是否在表中。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。既查找，又改變集合內(nèi)的數(shù)據(jù)元素。既查找，又改變集合內(nèi)的數(shù)據(jù)元素。記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(shí)別一個(gè)記錄記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(shí)別一個(gè)記錄 ( 預(yù)先確定的記錄的某種標(biāo)志預(yù)先確定的記錄的某種標(biāo)志 ) 可以唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字例如例如“學(xué)號(hào)學(xué)號(hào)”例如例如“女女”是一種數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu)識(shí)別若干記錄的關(guān)鍵字識(shí)別若干記錄的關(guān)鍵字4（2）對(duì)查找表常用的操作有）對(duì)查找表常用的操作有

3、哪些？哪些？ v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性；v在查找表中插入一元素；在查找表中插入一元素；v從查找表中刪除一元素。從查找表中刪除一元素。 （3) 有哪些查找方法？有哪些查找方法？ 查找方法取決于表中數(shù)據(jù)的排列方式查找方法取決于表中數(shù)據(jù)的排列方式;（1）查找的過(guò)程是怎樣的？）查找的過(guò)程是怎樣的？ 給定一個(gè)值給定一個(gè)值K K，在含有，在含有n n個(gè)記錄的文件中進(jìn)行搜索，尋找個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于一個(gè)關(guān)鍵字值等于K K的記錄，如找到則輸出該記錄，否則輸出的記錄，

4、如找到則輸出該記錄，否則輸出查找不成功的信息。查找不成功的信息。例如查字典例如查字典針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同。針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同?！疤囟ǖ奶囟ǖ摹?關(guān)鍵關(guān)鍵字字5明確：明確：查找的過(guò)程就是將給定的查找的過(guò)程就是將給定的K K值與文件中各記錄的關(guān)鍵字值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)劣。稱為平均查找長(zhǎng)度（劣。稱為平均查找長(zhǎng)度（ASLASL：average search lengthaverage search length）。）。其中：其中：n n是

5、文件記錄個(gè)數(shù)；是文件記錄個(gè)數(shù)；P Pi i是查找第是查找第i i個(gè)記錄的查找概率（通常取等概率個(gè)記錄的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。統(tǒng)計(jì)意義上的統(tǒng)計(jì)意義上的數(shù)學(xué)期望值數(shù)學(xué)期望值物理意義：物理意義：假設(shè)每一元素被查找的概率相同，則查找每假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為一元素所需的比較次數(shù)之總和再取平均，即為ASLASL。顯然，顯然，ASLASL值越小，時(shí)間效率越高。值越小，時(shí)間效率越高。 6針對(duì)靜態(tài)查找表的查找算法主要有：針

6、對(duì)靜態(tài)查找表的查找算法主要有： 靜態(tài)查找表的抽象數(shù)據(jù)類型參見(jiàn)教材靜態(tài)查找表的抽象數(shù)據(jù)類型參見(jiàn)教材P216。一、一、順序查找（線性查找）順序查找（線性查找）二、二、折半查找（二分或?qū)Ψ植檎遥┱郯氩檎遥ǘ只驅(qū)Ψ植檎遥┤?、三、靜態(tài)樹(shù)表的查找靜態(tài)樹(shù)表的查找四、四、分塊查找（索引順序查找）分塊查找（索引順序查找）7（1）順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：）順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：typedef struct ElemType *elem; /表基址，表基址，0 0號(hào)單元留空。表容量為全部元素號(hào)單元留空。表容量為全部元素 int length; /表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)SSTable;順序查

7、找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。直接的辦法。 v 對(duì)順序結(jié)構(gòu)如何線性查找？對(duì)順序結(jié)構(gòu)如何線性查找？見(jiàn)下頁(yè)之例見(jiàn)下頁(yè)之例或教材或教材P216P216；v 對(duì)單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易對(duì)單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易編寫；只要知道頭指針編寫；只要知道頭指針headhead就可以就可以“順藤摸瓜順藤摸瓜”；v 對(duì)非線性樹(shù)結(jié)構(gòu)如何順序查找對(duì)非線性樹(shù)結(jié)構(gòu)如何順序查找? ?可借助各種遍歷操作！可借助各種遍歷操作！8技巧：技巧：把待查關(guān)鍵字把待查關(guān)鍵字keykey存入表頭或表尾（俗稱存入

8、表頭或表尾（俗稱“哨兵哨兵”），），這樣可以加快執(zhí)行速度。這樣可以加快執(zhí)行速度。例：例：若將待查找的特定值若將待查找的特定值keykey存入順序表的首部（如存入順序表的首部（如0 0號(hào)單號(hào)單元），則順序查找的實(shí)現(xiàn)方案為：從后向前逐個(gè)比較！元），則順序查找的實(shí)現(xiàn)方案為：從后向前逐個(gè)比較！int Search_Seq( SSTable ST , KeyType key ) /在順序表在順序表STST中，查找關(guān)鍵字與中，查找關(guān)鍵字與keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位置信息，否則返回置信息，否則返回0 0 ST.elem0.key =key; /設(shè)立哨兵，可免去查找過(guò)

9、程中每一步設(shè)立哨兵，可免去查找過(guò)程中每一步都要檢測(cè)是否查找完畢。當(dāng)都要檢測(cè)是否查找完畢。當(dāng)n1000n1000時(shí)，查找時(shí)間將減少一半。時(shí)，查找時(shí)間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+) return i; /若到達(dá)若到達(dá)0 0號(hào)單元才結(jié)束循環(huán)，說(shuō)明不成功，返回號(hào)單元才結(jié)束循環(huán)，說(shuō)明不成功，返回0 0值值(i=0)(i=0)。成功時(shí)則返回找到的那個(gè)元素的位置。成功

10、時(shí)則返回找到的那個(gè)元素的位置i i。 / Search_Seq9返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨哨兵兵”，就是將關(guān)鍵字送入末地址，就是將關(guān)鍵字送入末地址ST.elem0.keyST.elem0.key使之結(jié)束并返回使之結(jié)束并返回 i=0i=0。討論討論 查找效率怎樣計(jì)算？查找效率怎樣計(jì)算？用平均查找長(zhǎng)度用平均查找長(zhǎng)度ASL衡量。衡量。討論討論 如何計(jì)算如何計(jì)算ASL？分析：分析：查找第查找第1個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為1；查找第查找第2個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為2；查找第查找第n個(gè)元素所

11、需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為n；總計(jì)全部比較次數(shù)為：總計(jì)全部比較次數(shù)為：12n = (1+n)n/2未考慮查找不成功的未考慮查找不成功的情況：查找哨兵所需情況：查找哨兵所需的比較次數(shù)為的比較次數(shù)為n+1n+1這是查找成功的情況這是查找成功的情況若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），（等概率），即：即： ASL（1n）/2 ，時(shí)間效率為，時(shí)間效率為 O(n)思考不成功的計(jì)算思考不成功的計(jì)算10優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：缺點(diǎn)： ASL 太長(zhǎng)，時(shí)間效率太低。太長(zhǎng)，時(shí)

12、間效率太低。這是一種容易想到的查找方法。這是一種容易想到的查找方法。先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將keykey與正中元素相比，若與正中元素相比，若keykey小，則縮小至左半部?jī)?nèi)查找；再取其中小，則縮小至左半部?jī)?nèi)查找；再取其中值比較，每次縮小值比較，每次縮小1/21/2的范圍，直到查找成功或失敗為止。的范圍，直到查找成功或失敗為止。v 對(duì)順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)折半查找算法？對(duì)順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)折半查找算法？ 見(jiàn)下頁(yè)之例，或見(jiàn)教材（見(jiàn)下頁(yè)之例，或見(jiàn)教材（P219P219）v 對(duì)單鏈表結(jié)構(gòu)如何折半查找？對(duì)單鏈表結(jié)構(gòu)如何折

13、半查找？ 無(wú)法實(shí)現(xiàn)！因全部元素的定位只能從頭指針無(wú)法實(shí)現(xiàn)！因全部元素的定位只能從頭指針headhead開(kāi)始開(kāi)始v 對(duì)非線性對(duì)非線性(樹(shù)樹(shù))結(jié)構(gòu)如何折半查找？結(jié)構(gòu)如何折半查找？ 可借助二叉排序樹(shù)來(lái)查找（屬動(dòng)態(tài)查找表形式）?？山柚媾判驑?shù)來(lái)查找（屬動(dòng)態(tài)查找表形式）。 如何改進(jìn)？如何改進(jìn)？討論討論 順序查找的特點(diǎn)：順序查找的特點(diǎn)：11 運(yùn)算步驟運(yùn)算步驟：(1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范圍是，待查范圍是 1,111,11；(2) (2) 若若 ST.elemmid.key keyST.elemmid.key ke

14、yST.elemmid.key key，說(shuō)明，說(shuō)明keykey low ,mid-1low ,mid-1， 則令：則令：high =midhigh =mid1;1;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key = keyST.elem mid .key = key，說(shuō)明查找成功，元素序號(hào)，說(shuō)明查找成功，元素序號(hào)=mid;=mid;結(jié)束條件：結(jié)束條件： （1 1）查找成功）查找成功 ： ST.elemmid.key = keyST.elemmid.key = key （2 2）查找不成功）查找不成功 ： highlow highlow （意即區(qū)間長(zhǎng)度小于（意即區(qū)

15、間長(zhǎng)度小于0 0）解：解： 先設(shè)定先設(shè)定3個(gè)輔助標(biāo)志個(gè)輔助標(biāo)志: low,high,midlow,high,mid，LowLow指向待查元素指向待查元素所在區(qū)間的下界所在區(qū)間的下界highhigh指向待查元素所指向待查元素所在區(qū)間的上界在區(qū)間的上界midmid指向待查元素所在指向待查元素所在區(qū)間的中間位置區(qū)間的中間位置 已知如下已知如下11個(gè)元素的有序表：個(gè)元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)查找關(guān)鍵字為請(qǐng)查找關(guān)鍵字為21 和和85的數(shù)據(jù)元素。的數(shù)據(jù)元素。顯然有：顯然有：mid= (low+high)/2 12mjjj112典型標(biāo)志是：當(dāng)查找

16、范圍的上界典型標(biāo)志是：當(dāng)查找范圍的上界下界時(shí)停止查找。下界時(shí)停止查找。討論討論 二分查找的效率（二分查找的效率（ASLASL）1次比較就查找成功的元素有次比較就查找成功的元素有1個(gè)（個(gè)（20），即中間值；），即中間值；2次比較就查找成功的元素有次比較就查找成功的元素有2個(gè)（個(gè)（21），即），即1/4處（或處（或3/4）處；）處；3次比較就查找成功的元素有次比較就查找成功的元素有4個(gè)（個(gè)（22），即），即1/8處（或處（或3/8）處）處 4次比較就查找成功的元素有次比較就查找成功的元素有8個(gè)（個(gè)（23），即），即1/16處（或處（或3/16）處）處 則第則第m次比較時(shí)查找成功的元素會(huì)有（次比較時(shí)

17、查找成功的元素會(huì)有（2m-1）個(gè)；）個(gè)；為方便起見(jiàn)，假設(shè)表中全部為方便起見(jiàn)，假設(shè)表中全部n個(gè)元素個(gè)元素 2m-1個(gè)，此時(shí)就不討論第個(gè)，此時(shí)就不討論第m次比較后還有剩余元素的情況了。次比較后還有剩余元素的情況了。全部比較總次數(shù)為全部比較總次數(shù)為120221322423m2m1 推推導(dǎo)導(dǎo)過(guò)過(guò)程程13（詳細(xì)推導(dǎo)過(guò)程見(jiàn)教材（詳細(xì)推導(dǎo)過(guò)程見(jiàn)教材P221的附錄）的附錄）課堂練習(xí)（多項(xiàng)選擇）：課堂練習(xí)（多項(xiàng)選擇）：nnnnjnASLmjj2211log1) 1(log121使用折半查找算法時(shí)，要求被查文件：使用折半查找算法時(shí)，要求被查文件：思考：思考：假設(shè)在有序線性表假設(shè)在有序線性表a20上進(jìn)行折半查找，則

18、上進(jìn)行折半查找，則平均查找長(zhǎng)度為平均查找長(zhǎng)度為 。14查找過(guò)程可用二叉樹(shù)描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為查找過(guò)程可用二叉樹(shù)描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為該記錄在表中位置，這個(gè)描述查找過(guò)程的二叉樹(shù)稱為判定樹(shù)。該記錄在表中位置，這個(gè)描述查找過(guò)程的二叉樹(shù)稱為判定樹(shù)。n個(gè)個(gè)元素的表的折半查找的判定樹(shù)是唯一的，即：判定樹(shù)由表中元素個(gè)元素的表的折半查找的判定樹(shù)是唯一的，即：判定樹(shù)由表中元素個(gè)數(shù)決定。數(shù)決定。 找到有序表中任一記錄的過(guò)程就是：走了一條從根結(jié)點(diǎn)到與該記錄找到有序表中任一記錄的過(guò)程就是：走了一條從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑。相應(yīng)的結(jié)點(diǎn)的路徑。 比較的關(guān)鍵字個(gè)數(shù)：為該結(jié)點(diǎn)在

19、判定樹(shù)上的層次數(shù)。比較的關(guān)鍵字個(gè)數(shù)：為該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)。 查找成功時(shí)比較的關(guān)鍵字個(gè)數(shù)最多不超過(guò)樹(shù)的深度查找成功時(shí)比較的關(guān)鍵字個(gè)數(shù)最多不超過(guò)樹(shù)的深度 d : d = log2 n + 1 若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的指針，稱若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的指針，稱方形結(jié)點(diǎn)為判定樹(shù)的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。方形結(jié)點(diǎn)為判定樹(shù)的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。 查找不成功的過(guò)程查找不成功的過(guò)程 就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑。就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑。做習(xí)題做習(xí)題新建新建 Microsoft Word 文檔文檔.doc1

20、5討論討論2：當(dāng)有序表中各記錄的查找概率不相等時(shí)，該如何查？：當(dāng)有序表中各記錄的查找概率不相等時(shí)，該如何查？首先要明確，此時(shí)用折半查找法未必最優(yōu)?。▍⒁?jiàn)教材首先要明確，此時(shí)用折半查找法未必最優(yōu)?。▍⒁?jiàn)教材P222例）例）改進(jìn)：若將各記錄概率看作是二叉樹(shù)之權(quán)值，則轉(zhuǎn)為研究帶改進(jìn)：若將各記錄概率看作是二叉樹(shù)之權(quán)值，則轉(zhuǎn)為研究帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)（類似最優(yōu)二叉樹(shù)）。權(quán)路徑長(zhǎng)度最小的二叉樹(shù)（類似最優(yōu)二叉樹(shù)）。討論討論1：對(duì)有序表還有其他查找算法嗎？：對(duì)有序表還有其他查找算法嗎？靜態(tài)最優(yōu)查找樹(shù)算法靜態(tài)最優(yōu)查找樹(shù)算法時(shí)間代價(jià)高；時(shí)間代價(jià)高；實(shí)用算法：近似最優(yōu)查找樹(shù)（次優(yōu)查找樹(shù)）實(shí)用算法：近似最優(yōu)查找樹(shù)

21、（次優(yōu)查找樹(shù)） （參見(jiàn)教材（參見(jiàn)教材P222225）有，如斐波那契查找和插值查找等（參見(jiàn)教材有，如斐波那契查找和插值查找等（參見(jiàn)教材P221222）16這是一種順序查找的另一種改進(jìn)方法。這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)先讓數(shù)據(jù)分塊有序分塊有序，即分成若干子表，要求每個(gè)子表中的數(shù)，即分成若干子表，要求每個(gè)子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值?。ǖ颖韮?nèi)部未必值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值小（但子表內(nèi)部未必有序）。有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表索引表，表中還要包，表中還要包含每個(gè)子表的起始地址（即頭指針）。含每個(gè)子表的起

22、始地址（即頭指針）。索引表索引表最大關(guān)鍵字起始地址第第1 1塊塊第第2 2塊塊第第3 3塊塊224886例：例：特點(diǎn)：塊間有特點(diǎn)：塊間有序，塊內(nèi)無(wú)序序，塊內(nèi)無(wú)序17 對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?；?duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無(wú)序表）；查找法（因?yàn)楦髯颖韮?nèi)部是無(wú)序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w對(duì)索引表查找的對(duì)索引表查找的ASL對(duì)塊內(nèi)查找的對(duì)塊內(nèi)查找的ASL)21(log2) 1(log22nASLnssnASL

23、bsbsS為每塊內(nèi)部的記錄個(gè)數(shù)，為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的數(shù)目即塊的數(shù)目例如當(dāng)例如當(dāng)n=9n=9，s=3s=3時(shí)，時(shí)，ASLASLbsbs=3.5,=3.5,而折半法為而折半法為3.1,3.1,順序法為順序法為5 51819特點(diǎn)：特點(diǎn)：一、一、二叉排序樹(shù)的定義二叉排序樹(shù)的定義二、二、二叉排序樹(shù)的插入與刪除二叉排序樹(shù)的插入與刪除三、三、二叉排序樹(shù)的查找分析二叉排序樹(shù)的查找分析四、平衡二叉樹(shù)四、平衡二叉樹(shù)表結(jié)構(gòu)在查找過(guò)程中動(dòng)態(tài)生成。表結(jié)構(gòu)在查找過(guò)程中動(dòng)態(tài)生成。要求：要求： 對(duì)于給定值對(duì)于給定值key,key,若表中存在其關(guān)鍵字等于若表中存在其關(guān)鍵字等于keykey的記錄，則查找成功返回；的

24、記錄，則查找成功返回；典型的動(dòng)態(tài)表典型的動(dòng)態(tài)表二叉排序樹(shù)二叉排序樹(shù)20（a）（b）練：下列練：下列2種圖形中，哪個(gè)不是二叉排序樹(shù)種圖形中，哪個(gè)不是二叉排序樹(shù) ？-或是一棵空樹(shù)；或者是具有如下性質(zhì)的非空二叉樹(shù)：或是一棵空樹(shù)；或者是具有如下性質(zhì)的非空二叉樹(shù)： （1 1）左子樹(shù)的所有結(jié)點(diǎn)均小于根的值；）左子樹(shù)的所有結(jié)點(diǎn)均小于根的值； （2 2）右子樹(shù)的所有結(jié)點(diǎn)均大于根的值；）右子樹(shù)的所有結(jié)點(diǎn)均大于根的值； （3 3）它的左右子樹(shù)也分別為二叉排序樹(shù)。）它的左右子樹(shù)也分別為二叉排序樹(shù)。21將數(shù)據(jù)元素構(gòu)造成二叉排序樹(shù)的優(yōu)點(diǎn)：將數(shù)據(jù)元素構(gòu)造成二叉排序樹(shù)的優(yōu)點(diǎn)： 查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找相似，查找

25、效率高；查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高； 中序遍歷此二叉樹(shù)，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)中序遍歷此二叉樹(shù)，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）；了排序運(yùn)算）； 如果查找不成功，能夠方便地將被查元素插入到二叉樹(shù)的葉子如果查找不成功，能夠方便地將被查元素插入到二叉樹(shù)的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。注：若注：若數(shù)據(jù)元素的數(shù)據(jù)元素的輸入順序不同，則得到的二叉排序樹(shù)形態(tài)輸入順序不同，則得到的二叉排序樹(shù)形態(tài)也不同！也不同！這種既查找又插入的過(guò)程稱為動(dòng)態(tài)查找。這種既查找又插入的過(guò)程稱為動(dòng)態(tài)

26、查找。二叉排序樹(shù)既有類似于折半查找的特性，又采用了鏈表存儲(chǔ)，二叉排序樹(shù)既有類似于折半查找的特性，又采用了鏈表存儲(chǔ)，它是動(dòng)態(tài)查找表的一種適宜表示。它是動(dòng)態(tài)查找表的一種適宜表示。2245452424535312129090如果待如果待查找的關(guān)鍵字序列輸入順序?yàn)椋翰檎业年P(guān)鍵字序列輸入順序?yàn)椋海?424，5353， 4545，4545，1212，2424，9090），），24245353454512129090查查找找成成功，功，返返回回查查找找成成功，功，返返回回則生成二叉排序則生成二叉排序樹(shù)的過(guò)程為：樹(shù)的過(guò)程為：例例：輸入待查找的關(guān)鍵字序列輸入待查找的關(guān)鍵字序列= =（4545，2424，5353

27、，4545，1212，2424，9090）則生成的二叉排則生成的二叉排序樹(shù)形態(tài)不同：序樹(shù)形態(tài)不同：查查找找成成功，功，返返回回查查找找成成功，功，返返回回23查找算法參見(jiàn)教材查找算法參見(jiàn)教材P228算法算法9.5（a,b）;插入算法參見(jiàn)教材插入算法參見(jiàn)教材P228算法算法9.6;24對(duì)于二叉排序樹(shù)，刪除樹(shù)上一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中對(duì)于二叉排序樹(shù)，刪除樹(shù)上一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個(gè)記錄，刪除后仍需保持二叉排序樹(shù)的特性。的一個(gè)記錄，刪除后仍需保持二叉排序樹(shù)的特性。（對(duì)鏈表進(jìn)行刪除操作是很方便的）（對(duì)鏈表進(jìn)行刪除操作是很方便的）如何刪除一個(gè)結(jié)點(diǎn)？如何刪除一個(gè)結(jié)點(diǎn)？假設(shè)：假設(shè)：* *p p

28、表示被刪結(jié)點(diǎn)的指針；表示被刪結(jié)點(diǎn)的指針； P PL和和PR 分別表示分別表示* *P P的左、右孩子指針；的左、右孩子指針；* *f f表示表示* *p p的雙親結(jié)點(diǎn)指針；并假定的雙親結(jié)點(diǎn)指針；并假定* *p p是是* *f f的左孩子；則可能有三種情況：的左孩子；則可能有三種情況：PR 為為 * * S S 的右子樹(shù)；的右子樹(shù)； S SL 為為 Q（ * * S S的雙親結(jié)點(diǎn)）右孩子的雙親結(jié)點(diǎn)）右孩子* *p p為葉子：為葉子： 刪除此結(jié)點(diǎn)時(shí)，直接修改刪除此結(jié)點(diǎn)時(shí)，直接修改* *f f指針域即可；指針域即可；* *p p只有一棵子樹(shù)（或左或右）：只有一棵子樹(shù)（或左或右）：令令P PL或或PR為為* *f f的左孩子即可；的左孩子即可；* *p p有兩棵子樹(shù)：情況最復(fù)雜有兩棵子樹(shù)：情況最復(fù)雜 25分析：分析：設(shè)刪除前的中序遍歷序列為：設(shè)刪除前的中序遍歷序列為：. s p