數(shù)據(jù)結(jié)構(gòu)課件：15、第八章 查找

1、1數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4第八章第八章 查查 找找2數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4l查找查找-即在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足條件的結(jié)點(diǎn)。即在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足條件的結(jié)點(diǎn)。l查找表查找表：是由同一類型的數(shù)據(jù)元素構(gòu)成的集合。是由同一類型的數(shù)據(jù)元素構(gòu)成的集合。l查找結(jié)果：成功、失敗。查找結(jié)果：成功、失敗。l平均查找長度平均查找長度查找一個(gè)結(jié)點(diǎn)所作的平均比較次查找一個(gè)結(jié)點(diǎn)所作的平均比較次數(shù)（衡量一個(gè)查找算法優(yōu)劣的主要標(biāo)準(zhǔn)）。數(shù)（衡量一個(gè)查找算法優(yōu)劣的主要標(biāo)準(zhǔn)）。3數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4查找算法的查找算法的四個(gè)特征四個(gè)特征：內(nèi)外有別內(nèi)外有別：分為內(nèi)查找和外查找。：分為內(nèi)查

2、找和外查找。靜態(tài)動(dòng)態(tài)靜態(tài)動(dòng)態(tài)：靜態(tài)查找時(shí)，表的內(nèi)容不變；動(dòng)態(tài)查找時(shí)，：靜態(tài)查找時(shí)，表的內(nèi)容不變；動(dòng)態(tài)查找時(shí)，表中的內(nèi)容不斷地變化。表中的內(nèi)容不斷地變化。原詞變詞原詞變詞：原詞系指用原來的關(guān)鍵詞，變詞系指使用經(jīng)：原詞系指用原來的關(guān)鍵詞，變詞系指使用經(jīng)過變換的關(guān)鍵詞。過變換的關(guān)鍵詞。數(shù)字文字?jǐn)?shù)字文字：指進(jìn)行比較的時(shí)候，是否用數(shù)字的性質(zhì)。：指進(jìn)行比較的時(shí)候，是否用數(shù)字的性質(zhì)。4數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4一、線性表的查找一、線性表的查找 8.1.1 無序表的順序查找無序表的順序查找 8.1.2 有序表的順序查找有序表的順序查找 8.2.1 對半查找對半查找 8.2.2 一致對半查找一致對半查

3、找 8.2.3 斐波那契查找斐波那契查找 8.2.4 插值查找插值查找二、樹形結(jié)構(gòu)的查找二、樹形結(jié)構(gòu)的查找三、散列三、散列5數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4一、線性表的查找一、線性表的查找8.1.1 無序表的順序查找無序表的順序查找l現(xiàn)實(shí)生活中現(xiàn)實(shí)生活中順序查找順序查找的例子很多。比如，在一個(gè)班級(jí)的的例子很多。比如，在一個(gè)班級(jí)的名冊中查找某個(gè)學(xué)生的名字。通常的做法是，順序比較名冊中查找某個(gè)學(xué)生的名字。通常的做法是，順序比較名冊中的每個(gè)名字。這就是順序查找名冊中的每個(gè)名字。這就是順序查找。l順序查找的基本思想順序查找的基本思想：從線性表的起始結(jié)點(diǎn)開始，逐個(gè)：從線性表的起始結(jié)點(diǎn)開始，逐個(gè)檢查每

4、個(gè)結(jié)點(diǎn)，或者找到關(guān)鍵詞檢查每個(gè)結(jié)點(diǎn)，或者找到關(guān)鍵詞 Ki=K，或者以，或者以in (i為表為表中記錄的下標(biāo)，中記錄的下標(biāo)，n為線性表的元素個(gè)數(shù)為線性表的元素個(gè)數(shù))查找失敗告終。查找失敗告終。 l順序查找很簡單、明顯，順序查找很簡單、明顯，該方法是討論查找問題的一個(gè)該方法是討論查找問題的一個(gè)有用的起點(diǎn)，因?yàn)樵S多錯(cuò)綜復(fù)雜的查找算法都是以它為有用的起點(diǎn)，因?yàn)樵S多錯(cuò)綜復(fù)雜的查找算法都是以它為基礎(chǔ)的基礎(chǔ)的。6數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4算法算法S ( N，R，K . i ) /* 給定包含給定包含N個(gè)記錄個(gè)記錄R1，R2，RN，其，其對應(yīng)的關(guān)鍵詞分別為對應(yīng)的關(guān)鍵詞分別為K1，K2，KN的一個(gè)表，

5、的一個(gè)表，S查找一個(gè)查找一個(gè)給定的變元給定的變元K . 這里假定這里假定N 1 . */S1. 初始化初始化 置置i 1 .S2. 比較關(guān)鍵詞比較關(guān)鍵詞 如果如果K Ki，則算法成功結(jié)束，則算法成功結(jié)束.S3. 推進(jìn)推進(jìn)i 置置i i 1 .S4. i N ? 若若i N，則返回步驟，則返回步驟S2；否則此算法以查找失?。环駝t此算法以查找失敗告終告終 . 7數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4算法算法S ( N，R，K . i ) /* 給定包含給定包含N個(gè)記錄個(gè)記錄R1，R2，RN，其對應(yīng)的關(guān)鍵詞，其對應(yīng)的關(guān)鍵詞分別為分別為K1，K2，KN的一個(gè)表，的一個(gè)表，S查找一個(gè)給定的查找一個(gè)給定的變

6、元變元K . 這里假定這里假定N 1 . */ S1 初始化初始化 i1 S2 比較關(guān)鍵詞比較關(guān)鍵詞 WHILE (i N) & (KKi) DO ii+1. 8數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4在表中引入一個(gè)在表中引入一個(gè)“虛擬虛擬”記錄記錄RN 1，能提高算法，能提高算法S的效率。的效率。算法算法Q ( N，R，K . i ) /* 算法算法Q與與S基本相同，區(qū)別在于基本相同，區(qū)別在于Q之表（或文件）的末之表（或文件）的末尾添加了一個(gè)尾添加了一個(gè)“虛擬虛擬”記錄記錄RN 1 . */Q1. 初始化初始化 置置i 1，并置，并置KN 1 K .Q2. 比較關(guān)鍵詞比較關(guān)鍵詞 如果如果

7、K Ki，則轉(zhuǎn)到步驟，則轉(zhuǎn)到步驟Q4 .Q3. 推進(jìn)推進(jìn)i 置置i i 1，并返回步驟，并返回步驟Q2 .Q4. i N ? 如果如果i N，則算法成功結(jié)束；，則算法成功結(jié)束； 否則以查找失敗告終否則以查找失敗告終. / 此時(shí)有此時(shí)有i N 19數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4算法算法Q（ N，R，Ki）/* 給定記錄給定記錄R1，R2，RN的表，其中的表，其中Ri的關(guān)鍵詞為的關(guān)鍵詞為Ki （1iN），本算法查找關(guān)鍵詞等于），本算法查找關(guān)鍵詞等于K的記錄的記錄*/Q1 初始化初始化 i1 KN+1K Q2 比較關(guān)鍵詞比較關(guān)鍵詞 WHILE KKi DO ii+1. 從算法從算法S到算法到算

8、法Q利用了一個(gè)重要的利用了一個(gè)重要的“加速原理加速原理”: 當(dāng)算法的當(dāng)算法的一個(gè)內(nèi)循環(huán)要測試兩個(gè)或多個(gè)條件時(shí)，應(yīng)力圖將其減少成一一個(gè)內(nèi)循環(huán)要測試兩個(gè)或多個(gè)條件時(shí)，應(yīng)力圖將其減少成一個(gè)條件。個(gè)條件。算法算法Q大約比算法大約比算法S節(jié)省百分之二十的運(yùn)行時(shí)間。節(jié)省百分之二十的運(yùn)行時(shí)間。10數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4 查找查找成功成功的平均查找長度：的平均查找長度： 查找查找失敗失敗的查找長度：的查找長度：N+1 順序查找的時(shí)間復(fù)雜度：順序查找的時(shí)間復(fù)雜度：O(N)111()12i ni niiiiii niE NP CCNNiN11數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4算法算法Q ( N，R

9、，K . i )Q 1. 初始化初始化 置置i 1 . KN 1 K .Q 2. 前進(jìn)兩步前進(jìn)兩步 置置i i 2 .Q 3. Ki : K 若若Ki K，則轉(zhuǎn)到步驟，則轉(zhuǎn)到步驟Q 5 .Q 4. Ki 1: K 若若Ki 1 K，則返回步驟，則返回步驟Q 2； 否則置否則置i i 1 . /查找成功，其位置為查找成功，其位置為i 1Q 5. i N ? 若若i N，則算法成功結(jié)束；否則算法以查找失，則算法成功結(jié)束；否則算法以查找失敗告終敗告終. / 此時(shí)此時(shí)i N 1算法算法Q還能更快嗎？還能更快嗎？將算法將算法Q中中i的增量由的增量由1變成變成2，推進(jìn)，推進(jìn)i 之操作減少將近一半。之操作減

10、少將近一半。算法算法Q 的運(yùn)行時(shí)間比算法的運(yùn)行時(shí)間比算法S減少了約百分之三十。減少了約百分之三十。12數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4l算法算法S、算法、算法Q、算法算法Q 說明：提高一個(gè)算法（或程說明：提高一個(gè)算法（或程序）之效率很可能有很大潛力。序）之效率很可能有很大潛力。l順序查找優(yōu)缺點(diǎn)順序查找優(yōu)缺點(diǎn): 優(yōu)點(diǎn)優(yōu)點(diǎn): 算法簡單，且適用面廣。算法簡單，且適用面廣。 缺點(diǎn)缺點(diǎn): 平均查找長度較大，平均查找長度較大，N很大時(shí)很大時(shí)查找效率低查找效率低。13數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4自組織表自組織表l表中各元素被查找的概率并不一定相同。把經(jīng)常出現(xiàn)的表中各元素被查找的概率并不一定相同。

11、把經(jīng)常出現(xiàn)的元素（它的發(fā)生概率較大）自動(dòng)向表的前端移動(dòng)，把不元素（它的發(fā)生概率較大）自動(dòng)向表的前端移動(dòng)，把不經(jīng)常出現(xiàn)的元素自動(dòng)向表的后端移動(dòng)，并稱以該方式組經(jīng)常出現(xiàn)的元素自動(dòng)向表的后端移動(dòng)，并稱以該方式組織的表為織的表為自組織表自組織表 。vMOVE-AHEAD-ONE vMOVE-TO-FRONT14數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4一、線性表的查找一、線性表的查找 8.1.1 無序表的順序查找無序表的順序查找 8.1.2 有序表的順序查找有序表的順序查找 8.2.1 對半查找對半查找 8.2.2 一致對半查找一致對半查找 8.2.3 斐波那契查找斐波那契查找 8.2.4 插值查找插值查找

12、15數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.1.2 有序表的順序查找有序表的順序查找算法算法T（R，n，Ki） /*表表R1，R2，Rn按照關(guān)鍵詞遞增有序按照關(guān)鍵詞遞增有序*/ T1 初始化初始化 i1 Kn+1+ . T2 順序與表中各元素比較順序與表中各元素比較 WHILE KKi DO ii+1. T3 若未找到，設(shè)若未找到，設(shè)in+1 IF KKi THEN in+1. 16數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4l算法成功結(jié)束時(shí)算法成功結(jié)束時(shí)1in，否則，否則i=n+1l與算法與算法Q相比較，對于成功的查找，算法相比較，對于成功的查找，算法T的期望復(fù)雜性為的期望復(fù)雜性為(n+1)/2，與

13、算法，與算法Q的期望復(fù)雜性相同；而對于不成功的查找的期望復(fù)雜性相同；而對于不成功的查找算法算法T的期望復(fù)雜性為的期望復(fù)雜性為(n+1)/2，而算法，而算法Q為為n+1，算法，算法T比算比算法法Q大約快一倍。大約快一倍。l先將文件排序，再查找，是一個(gè)快速的查找方法。但如果只先將文件排序，再查找，是一個(gè)快速的查找方法。但如果只需對表查找一次，則進(jìn)行順序查找比對這個(gè)表進(jìn)行完整排序需對表查找一次，則進(jìn)行順序查找比對這個(gè)表進(jìn)行完整排序要快；如果要在同一個(gè)文件中不斷進(jìn)行查找，那么要快；如果要在同一個(gè)文件中不斷進(jìn)行查找，那么將表按序?qū)⒈戆葱蚺帕性俨檎沂莻€(gè)很好的方法。排列再查找是個(gè)很好的方法。17數(shù)據(jù)結(jié)構(gòu)國家

14、精品課程2022-6-4l有序表（有序表（K1 K2 KN ）的查找，比較）的查找，比較K和和Ki 后，有后，有:K Ki ， 不必考慮子表不必考慮子表Ri，Ri 1，RN K Ki ， 查找成功結(jié)束查找成功結(jié)束 K Ki ， 不必考慮子表不必考慮子表R1，R2， ，Ri l使用不同的規(guī)則確定使用不同的規(guī)則確定i，可得到不同的查找方法。，可得到不同的查找方法。l算法算法T的改進(jìn)方法：對半查找、一致對半查找、斐的改進(jìn)方法：對半查找、一致對半查找、斐波那契查找和插值查找等。波那契查找和插值查找等。18數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.1線性表的查找線性表的查找 8.1.1 無序表的順序查找無

15、序表的順序查找 8.1.2 有序表的順序查找有序表的順序查找 8.2.1 對半查找對半查找 8.2.2 一致對半查找一致對半查找 8.2.3 斐波那契查找斐波那契查找 8.2.4 插值查找插值查找19數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.2.1 對半（折半，二分）查找對半（折半，二分）查找1、算法思想：、算法思想：K與待查表中間記錄的關(guān)鍵詞與待查表中間記錄的關(guān)鍵詞 K N/2 比較，其結(jié)果有三：比較，其結(jié)果有三：KK N/2 ，K= K N/2 ，KK N/2 由情況由情況知查找成功結(jié)束，由情況知查找成功結(jié)束，由情況和和能確定下一次能確定下一次應(yīng)到表的哪一半中去查找，即將查找范圍縮小一半；并

16、應(yīng)到表的哪一半中去查找，即將查找范圍縮小一半；并對確定的那一半重復(fù)上述過程，直至找到所查記錄或確對確定的那一半重復(fù)上述過程，直至找到所查記錄或確定該記錄不在表中。定該記錄不在表中。例例 假定有序表假定有序表A中中10個(gè)元素的關(guān)鍵詞序列：個(gè)元素的關(guān)鍵詞序列：12，23，26，37，54，60，68，75，82，96 當(dāng)給定值分別為當(dāng)給定值分別為96和和58時(shí)進(jìn)行二分查找。時(shí)進(jìn)行二分查找。20數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4 2、對半查找算法描述、對半查找算法描述算法算法B ( N，R，K . i ) /*給定關(guān)鍵詞在遞增次序下（即給定關(guān)鍵詞在遞增次序下（即K1 K2 KN）包含）包含N個(gè)記個(gè)

17、記錄錄R1, R2, , RN 的表，查找給定變元的表，查找給定變元K . 用兩個(gè)指針用兩個(gè)指針s和和e分別分別指向當(dāng)前被查找文件之最左邊和最右邊記錄的下標(biāo)。指向當(dāng)前被查找文件之最左邊和最右邊記錄的下標(biāo)。*/B1. 初始化初始化 置置s 1 . e N .B2. 取中點(diǎn)取中點(diǎn) 如果如果e s，則該算法以失敗告終；否則，置，則該算法以失敗告終；否則，置i (s + e) /2 。B3. 比較比較 如果如果K Ki，則轉(zhuǎn)步驟，則轉(zhuǎn)步驟B5；如果如果K = Ki，則算法成功結(jié)束。，則算法成功結(jié)束。B4. 調(diào)整調(diào)整e 置置e i 1，并返回，并返回B2 .B5. 調(diào)整調(diào)整s 置置s i 1，并返回，并

18、返回B2 . 21數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4查找查找k=96時(shí)二分查找過程時(shí)二分查找過程(4次比較成功）次比較成功） 1 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 9612 23 26 37 54 60 68 75 82 96s s=1=1e e=10=10e=10e=1012 23 26 37 12 23 26 37 54 54 60 68 75 82 96 60 68 75 82 96s s=1=1i i=5=5e=10e=1012 23 26 37 54 60 68 12 23 26 37 54 60 68 7575 82 96

19、82 96s=6s=6i=8i=812 23 26 37 54 60 68 7512 23 26 37 54 60 68 75 82 82 9696s=e=10s=e=10i=10i=10e=10e=1012 23 26 37 54 60 68 7512 23 26 37 54 60 68 75 82 82 96 96s=9s=9i=9i=922數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4查找查找k=58時(shí)二分查找過程時(shí)二分查找過程(3次比較失?。┐伪容^失敗） 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 9612

20、 23 26 37 54 60 68 75 82 96e=10e=1012 23 26 37 12 23 26 37 5454 60 68 75 82 96 60 68 75 82 96s=1s=1i=5i=5e=10e=1012 23 26 37 54 60 68 12 23 26 37 54 60 68 7575 82 96 82 96s=6s=6i=8i=812 23 26 37 54 60 68 75 82 9612 23 26 37 54 60 68 75 82 9612 23 26 37 54 12 23 26 37 54 6060 68 75 82 96 68 75 82 96s

21、=6s=6e=7e=7i=6i=623數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4 3、對半查找算法分析、對半查找算法分析每個(gè)圓圈結(jié)點(diǎn)表示關(guān)鍵詞比較每個(gè)圓圈結(jié)點(diǎn)表示關(guān)鍵詞比較 K : Ki4528136971054758296231226603768=24數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4二叉判定樹二叉判定樹 二叉判定樹，二叉判定樹，T（s，e）的）的遞歸定義遞歸定義如下：如下： (1)當(dāng)當(dāng)e-s+1 0時(shí)，時(shí)，T（s，e）為空樹；）為空樹； (2)當(dāng)當(dāng)e-s+10時(shí)，二叉判定樹的根結(jié)點(diǎn)是有序表中序號(hào)為時(shí)，二叉判定樹的根結(jié)點(diǎn)是有序表中序號(hào)為 (e+s)/2 的記錄，根結(jié)點(diǎn)的左子樹是與有序表的記錄，根

22、結(jié)點(diǎn)的左子樹是與有序表Rs，Rs+1，R (e+s)/2 -1相對應(yīng)的二叉判定樹，根結(jié)點(diǎn)的右子樹是與有序表相對應(yīng)的二叉判定樹，根結(jié)點(diǎn)的右子樹是與有序表R (e+s)/2 +1，R (e+s)/2 +2，Re相對應(yīng)的二叉判定樹。相對應(yīng)的二叉判定樹。25數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4T（1，10）的二叉判定樹：搜索）的二叉判定樹：搜索K=96452813697105475829623122660376826數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-44528136971054758296231226603768T（1，10）的二叉判定樹：搜索）的二叉判定樹：搜索K=5827數(shù)據(jù)結(jié)構(gòu)國家精品課程202

23、2-6-4T(1, 10)查找成功查找成功的平均查找長度的平均查找長度4528136971054758296231226603768ASLSUCC (1*1+2*2+3*4+4*3)/10 29/10 2.928數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4查找查找失敗失敗的平均查找長度：的平均查找長度： ASLUNSUCC En/(n+1) (3*5+4*6)/11 39/11452813697105475829623122660376829數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4引理引理8.1 設(shè)算法設(shè)算法B對對N個(gè)記錄的成功查找是等概率的，且對不個(gè)記錄的成功查找是等概率的，且對不成功的查找也是等概率的

24、，則成功查找的關(guān)鍵詞比較的平均成功的查找也是等概率的，則成功查找的關(guān)鍵詞比較的平均次數(shù)次數(shù)SN =1+IN/N，不成功查找的關(guān)鍵詞比較的平均次數(shù)，不成功查找的關(guān)鍵詞比較的平均次數(shù)UN=EN /(N+1)，其中，其中IN，EN為為T（1, N）的內(nèi)、外通路長度）的內(nèi)、外通路長度. 引理引理8.2 對半查找二叉判定樹對半查找二叉判定樹T（s, e）的高度是）的高度是 log2(e-s+2) . 引理引理8.3 設(shè)設(shè)T(1, N) 是是N個(gè)內(nèi)結(jié)點(diǎn)的二叉判定樹，不考慮外結(jié)點(diǎn)個(gè)內(nèi)結(jié)點(diǎn)的二叉判定樹，不考慮外結(jié)點(diǎn)T(1 , N)之高度為之高度為k，T(1 , N)之外結(jié)點(diǎn)均屬于之外結(jié)點(diǎn)均屬于k或或k 1層層

25、. 定理定理8.1 算法算法B在最壞情況下的關(guān)鍵詞比較次數(shù)為在最壞情況下的關(guān)鍵詞比較次數(shù)為 log2(N1) ，且期望復(fù)雜性等于，且期望復(fù)雜性等于O(log2N) . 30數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-44、二分查找總結(jié)、二分查找總結(jié): 優(yōu)點(diǎn)優(yōu)點(diǎn):查找效率為查找效率為O(log2N) /比順序查找高比順序查找高 缺點(diǎn)缺點(diǎn):只適用于只適用于有序表有序表，且，且限于順序存儲(chǔ)結(jié)構(gòu)，限于順序存儲(chǔ)結(jié)構(gòu)，對線性鏈表無對線性鏈表無法進(jìn)行二分查找。法進(jìn)行二分查找。31數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.1線性表的查找線性表的查找 8.1.1 無序表的順序查找無序表的順序查找 8.1.2 有序表的順序查

26、找有序表的順序查找 8.2.1 對半查找對半查找 8.2.2 一致對半查找一致對半查找 8.2.3 斐波那契查找斐波那契查找 8.2.4 插值查找插值查找32數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4當(dāng)當(dāng)N=10時(shí)一株時(shí)一株“一致一致”的二叉判定的二叉判定樹樹58002122434656878813792109 10 1 3 18.2.2 一致對半查找一致對半查找 將對半查找的指針數(shù)量由三個(gè)將對半查找的指針數(shù)量由三個(gè)( s，i和和e )減少為兩個(gè)。減少為兩個(gè)。 i= N / 2 ，m= N / 2 =5i=i+/- m / 2 ，m= m / 2 =2i=i+/- m / 2 ，m= m / 2 =

27、1i=i+/- m / 2 ，m= 033數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4一致對半查找算法一致對半查找算法 算法算法U ( N，R，K . i )/*給定包含給定包含N個(gè)記錄個(gè)記錄R1，R2，RN，其諸關(guān)鍵詞滿足，其諸關(guān)鍵詞滿足K1 K2 KN 的一張表，本算法查找變元的一張表，本算法查找變元K . 若若N為偶數(shù)，則算法有時(shí)將涉及為偶數(shù)，則算法有時(shí)將涉及一個(gè)虛擬關(guān)鍵詞一個(gè)虛擬關(guān)鍵詞K0 ，K0 被置成被置成 （或小于（或小于K的任意值）的任意值）. 我們假我們假定定N 1 .*/U1. 初始化初始化 置置i N / 2 ，m N / 2 .U2. 比比 較較 若若K Ki，轉(zhuǎn)到，轉(zhuǎn)到U3；

28、若；若K Ki，轉(zhuǎn)到，轉(zhuǎn)到U4；若；若K Ki ，則，則算法成功結(jié)束。算法成功結(jié)束。U3. 減小減小i 若若m 0，則算法以失敗告終；否則置，則算法以失敗告終；否則置i i m / 2 ；然后置然后置m m / 2 并返回并返回U2 .U4. 增大增大i 若若m = 0，則算法以失敗告終；否則置，則算法以失敗告終；否則置i i m / 2 ；然后置然后置m m / 2 并返回并返回U2 . 34數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4l算法算法U之所以被稱為是一致的，是因?yàn)?，之所以被稱為是一致的，是因?yàn)?，在層在層l上的上的一個(gè)結(jié)點(diǎn)的編號(hào)與在層一個(gè)結(jié)點(diǎn)的編號(hào)與在層l-1上其父結(jié)點(diǎn)的編號(hào)之差的上其父結(jié)

29、點(diǎn)的編號(hào)之差的絕對值，對于層絕對值，對于層l上的所有結(jié)點(diǎn)均有一致的常數(shù)上的所有結(jié)點(diǎn)均有一致的常數(shù) . 例如，上圖例如，上圖 中，對第中，對第1層均有一致的層均有一致的 3，對第，對第2層層均有一致的均有一致的 1，對第，對第3層均有一致的層均有一致的 1 .l當(dāng)查找失敗時(shí)，當(dāng)查找失敗時(shí)，U 可能在結(jié)束前作一次冗余的比較可能在結(jié)束前作一次冗余的比較，如圖中陰影結(jié)點(diǎn)所示。，如圖中陰影結(jié)點(diǎn)所示。35數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4在算法在算法 U 中，每次用來找中點(diǎn)中，每次用來找中點(diǎn)i的的 m 的序列如下：的序列如下：232220/,/,/,NNN 012,2N 011222/,22NN 012

30、123222/,222NNN 中點(diǎn)中點(diǎn)i序列如下：序列如下：于是算法于是算法 U 又可以改進(jìn)：在運(yùn)行期間，不去計(jì)算又可以改進(jìn)：在運(yùn)行期間，不去計(jì)算m及及i值，值，而是使用一張輔助表：而是使用一張輔助表：12(2) 2log2jjNDELTA jforjN36數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4算法算法C ( N，R，K . i ) /*算法算法 C 與算法與算法 U 相似，但它使用一個(gè)輔助表來代替涉相似，但它使用一個(gè)輔助表來代替涉及及 m 的計(jì)算。這個(gè)表中的項(xiàng)是的計(jì)算。這個(gè)表中的項(xiàng)是 */ C1. 初始化初始化 置置i DELTA1 . j 2 .C2. 比較比較 若若K Ki , 則轉(zhuǎn)則轉(zhuǎn)

31、C3；若；若K K i , 則轉(zhuǎn)則轉(zhuǎn) C4；若；若K K i ，則算法成功結(jié)束，則算法成功結(jié)束.C3. 減小減小i 若若 DELTA j 0，則算法以失敗告終；否則，則算法以失敗告終；否則置置 i i DELTA j . j j 1，并轉(zhuǎn)，并轉(zhuǎn) C2 .C4. 增大增大i 若若 DELTA j 0，則此算法以失敗告終；否，則此算法以失敗告終；否則，置則，置i i DELTA j . j j 1，并轉(zhuǎn)，并轉(zhuǎn)C212(2 ) log22jjNDELTA jforjN 37數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4一致對半查找算法一致對半查找算法(算法算法C) 的時(shí)間復(fù)雜度分析：的時(shí)間復(fù)雜度分析：n成功的

32、查找成功的查找：算法：算法C對應(yīng)的二叉判定樹與算法對應(yīng)的二叉判定樹與算法B對對應(yīng)的二叉應(yīng)的二叉判定判定樹有相同的內(nèi)路徑長，所以平均比較次樹有相同的內(nèi)路徑長，所以平均比較次數(shù)與算法數(shù)與算法B一樣。一樣。n不成功的查找不成功的查找：算法：算法C總是恰好進(jìn)行總是恰好進(jìn)行 log2N +1次比次比較，比算法較，比算法B的的 log2(N1) 比較次數(shù)多比較次數(shù)多。n算法算法 C 中的算術(shù)運(yùn)算僅包含加減法，且中的算術(shù)運(yùn)算僅包含加減法，且在算法運(yùn)行在算法運(yùn)行期間期間未未計(jì)算諸計(jì)算諸 m 之值，而是用一張輔助表來代替，之值，而是用一張輔助表來代替，從而明顯提高了速度。從而明顯提高了速度。算法算法C的時(shí)間花費(fèi)

33、不足算法的時(shí)間花費(fèi)不足算法B的二分之一的二分之一。 38數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4除了對除了對“待查表待查表”進(jìn)行均勻劃分之外，我們還有沒進(jìn)行均勻劃分之外，我們還有沒有新的劃分思路？就是說一定要對半劃分嗎？對半有新的劃分思路？就是說一定要對半劃分嗎？對半劃分是最好的劃分嗎？劃分是最好的劃分嗎？回答是肯定的，確實(shí)存在對半劃分的替代方案回答是肯定的，確實(shí)存在對半劃分的替代方案斐波那契劃分。斐波那契劃分。這一替代方案是更可取的，因?yàn)樗话?、減法，這一替代方案是更可取的，因?yàn)樗话印p法，連除以連除以2的除法都沒有的除法都沒有 。39數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.1線性表的

34、查找線性表的查找 8.1.1 無序表的順序查找無序表的順序查找 8.1.2 有序表的順序查找有序表的順序查找 8.2.1 對半查找對半查找 8.2.2 一致對半查找一致對半查找 8.2.3 斐波那契查找斐波那契查找 8.2.4 插值查找插值查找40數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.2.3 斐波那契查找斐波那契查找Fibonacci 序列：序列：0，1，1，2，3，5，8，13，21，34，F(xiàn)0=0，F(xiàn)1=1，F(xiàn)j=Fj-1+Fj-2 ，j2斐波那契（斐波那契（Fibonacci）查找）查找 對半查找的替代，以對半查找的替代，以Fibonacci序列的分劃代替序列的分劃代替了對半查找的均勻

35、分劃了對半查找的均勻分劃。41數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4假設(shè)有一個(gè)長度為假設(shè)有一個(gè)長度為Fk+1 1的文件，其記錄下標(biāo)的文件，其記錄下標(biāo)1，F(xiàn)k+1 1。記。記錄錄 F k 將文件分為三個(gè)部分：將文件分為三個(gè)部分： 左子文件左子文件1，F(xiàn)k 1； F k； 右子文件右子文件Fk+1，F(xiàn)k+1 1；其中，左、右子文件的大小分別為其中，左、右子文件的大小分別為Fk 1，F(xiàn)k 1 1，故左、右子，故左、右子文件還可繼續(xù)進(jìn)行上面的劃分（文件還可繼續(xù)進(jìn)行上面的劃分（黃金分割黃金分割）過程。）過程。 42數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4k 階斐波那契樹階斐波那契樹T k 的遞歸定義如下：的遞

36、歸定義如下： 當(dāng)當(dāng) k 0 , 1時(shí)，時(shí)，T k 為空樹；為空樹； 當(dāng)當(dāng) k 1 時(shí)，二叉判定樹之時(shí)，二叉判定樹之根根是有序表中序號(hào)為是有序表中序號(hào)為f k 的記錄，的記錄，根結(jié)點(diǎn)的左子樹是與有序表根結(jié)點(diǎn)的左子樹是與有序表k 階斐波那契樹有階斐波那契樹有 fk+1 1 個(gè)內(nèi)結(jié)點(diǎn)和個(gè)內(nèi)結(jié)點(diǎn)和 fk+1個(gè)外結(jié)點(diǎn)個(gè)外結(jié)點(diǎn).對應(yīng)的二叉判定樹，根為對應(yīng)的二叉判定樹，根為fk 1；根結(jié)點(diǎn)的右子樹是與有序表根結(jié)點(diǎn)的右子樹是與有序表對應(yīng)的二叉判定樹，是對應(yīng)的二叉判定樹，是k 2階且所有結(jié)點(diǎn)之編號(hào)都階且所有結(jié)點(diǎn)之編號(hào)都增加增加fk 的斐波那契樹的斐波那契樹Tk 2 fk , 其根為其根為fk+ fk 2 . 1

37、21,kfRRR 1121,kkkfffRRR43數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4f2T1T0+f2101f3T2T1+f321012二階斐波二階斐波那契樹那契樹T2三階斐波三階斐波那契樹那契樹T3Fibonacci 序列：序列：0，1，1，2，3，5，8，13，21，34，44數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4f4T3T2+f4210123434四階斐波四階斐波那契樹那契樹T4Fibonacci 序列：序列：0，1，1，2，3，5，8，13，21，34，45數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-46 階斐波那契樹，即階斐波那契樹，即N 12 f7 1 . 94262345678910111

38、20137511110128Fibonacci 序列：序列：0，1，1，2，3，5，8，13，21，34，46數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4算法算法F( N，R，K . i ) /* 給定包含給定包含N個(gè)記錄個(gè)記錄 R1，R2，RN，對應(yīng)的諸關(guān)鍵詞滿足，對應(yīng)的諸關(guān)鍵詞滿足K1 K2 KN 的表，算法的表，算法 F 查找變元查找變元 K ；為方便計(jì)，假定；為方便計(jì)，假定 N fk+1 1 ， fk+1為斐波那契數(shù)，為斐波那契數(shù)，只要適當(dāng)初始化，算法只要適當(dāng)初始化，算法 F 對任何對任何 N 都有效都有效 */F1. 初始化初始化置置 i f k ，p fk 1，q fk 2（p 和和 q

39、是兩個(gè)相鄰的斐波那契數(shù)是兩個(gè)相鄰的斐波那契數(shù)，用于尋找下一次與，用于尋找下一次與K比較的點(diǎn)）比較的點(diǎn)）.F2. 比比 較較若若K K i，則轉(zhuǎn)步驟，則轉(zhuǎn)步驟F3；若；若K K i，則轉(zhuǎn)步驟，則轉(zhuǎn)步驟F4；若若K = K i，則算法成功結(jié)束，則算法成功結(jié)束 .F3. i 減值減值 若若q 0（已到樹葉），則算法以失敗告終（已到樹葉），則算法以失敗告終;否則否則置置 i i q，t p，p q，q t q，并返回，并返回F2 .F4. i 增值增值 若若 p 1（已到樹葉），則算法以失敗告終（已到樹葉），則算法以失敗告終;否則否則置置 i i q，p p q，q q p，并返回，并返回F2.47數(shù)

40、據(jù)結(jié)構(gòu)國家精品課程2022-6-4引理引理8.4 設(shè)設(shè)m3，Tm是是m階階Fibonacci樹形，則樹形，則Tm的左子的左子樹形的高度等于右子樹形的高度加樹形的高度等于右子樹形的高度加1，且，且Tm 的高度為的高度為m-1 . 引理引理8.5 設(shè)設(shè)n= Fm+1-1，則，則m階階Fibonacci樹形的高度約等樹形的高度約等于于1. 44log2（n1） . 定理定理8.2 令令n=Fm+1-1，則算法，則算法Fibonacci在最壞情況下的在最壞情況下的時(shí)間復(fù)雜性為時(shí)間復(fù)雜性為O(log2n)，且期望復(fù)雜性亦為，且期望復(fù)雜性亦為O(log2n) .Fibonacci查找的算法分析查找的算法分

41、析48數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4Fibonacci查找算法的效率查找算法的效率l算法算法 C 的平均運(yùn)行時(shí)間大約是算法的平均運(yùn)行時(shí)間大約是算法 F 的的 1.2 倍，算倍，算法法 B 的平均運(yùn)行時(shí)間大約是算法的平均運(yùn)行時(shí)間大約是算法 F 的的 2.5 倍。倍。l最壞情況下，算法最壞情況下，算法 F 比算法比算法 C 稍稍慢一點(diǎn)。稍稍慢一點(diǎn)。49數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4小小 結(jié)結(jié)若實(shí)現(xiàn)從有序表的順序查找若實(shí)現(xiàn)從有序表的順序查找到到對半查找算法對半查找算法B的的“跳躍跳躍”, 必需必需實(shí)現(xiàn)實(shí)現(xiàn): 從只考慮從只考慮K Ki和和K Ki等兩種情況等兩種情況到到考慮考慮K Ki,

42、K Ki和和K Ki 等三種情況等三種情況; 從每次比較下一個(gè)關(guān)鍵詞從每次比較下一個(gè)關(guān)鍵詞到到每次比較被查每次比較被查找的子文件之中點(diǎn)。找的子文件之中點(diǎn)。若實(shí)現(xiàn)從算法若實(shí)現(xiàn)從算法B到到一致對半查找算法一致對半查找算法U的的“跳躍跳躍”, 需實(shí)現(xiàn)一個(gè)需實(shí)現(xiàn)一個(gè)思想轉(zhuǎn)彎思想轉(zhuǎn)彎, 即從使用即從使用s、e、i等等3個(gè)指針到僅使用個(gè)指針到僅使用i和和m兩個(gè)指針兩個(gè)指針（mm/2 ，下次被查找子文件長度之半）；，下次被查找子文件長度之半）；若實(shí)現(xiàn)從算法若實(shí)現(xiàn)從算法U到到一致對半查找算法一致對半查找算法C的的“跳躍跳躍”, 需想到用一需想到用一張表存放諸張表存放諸m值值(算法運(yùn)行時(shí)算法運(yùn)行時(shí), 省去計(jì)算諸

43、省去計(jì)算諸m的時(shí)間的時(shí)間, 用空間換時(shí)用空間換時(shí)間間);當(dāng)對半查找算法之改進(jìn)當(dāng)對半查找算法之改進(jìn)到了到了“山重水復(fù)疑無路山重水復(fù)疑無路”的時(shí)候，跳出的時(shí)候，跳出對半二叉判定樹的局限對半二叉判定樹的局限轉(zhuǎn)而去探索新的二叉判定樹轉(zhuǎn)而去探索新的二叉判定樹 斐波那斐波那契二叉判定樹，即斐波那契查找算法契二叉判定樹，即斐波那契查找算法F .50數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.1線性表的查找線性表的查找 8.1.1 無序表的順序查找無序表的順序查找 8.1.2 有序表的順序查找有序表的順序查找 8.2.1 對半查找對半查找 8.2.2 一致對半查找一致對半查找 8.2.3 斐波那契查找斐波那契查找

44、 8.2.4 插值查找插值查找51數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.2.4 插值查找插值查找 問題的提出問題的提出l前面討論的幾種查找算法是基于前面討論的幾種查找算法是基于嚴(yán)格比較嚴(yán)格比較的，即假定我的，即假定我們對線性表中元素的分布一無所知（或稱沒有啟發(fā)式信們對線性表中元素的分布一無所知（或稱沒有啟發(fā)式信息）息）. 然而實(shí)際中，很多查找問題所涉及的表滿足某些統(tǒng)然而實(shí)際中，很多查找問題所涉及的表滿足某些統(tǒng)計(jì)的特點(diǎn)。計(jì)的特點(diǎn)。l例如在一本英漢字典中尋找單詞例如在一本英漢字典中尋找單詞“worst”，我們決不會(huì)，我們決不會(huì)仿照對半查找仿照對半查找(或或Fibonacci查找查找)那樣，先查找

45、字典中間那樣，先查找字典中間的元素，然后查找字典四分之三處的元素等等的元素，然后查找字典四分之三處的元素等等. 事實(shí)上，事實(shí)上，我們是在所期望的地址我們是在所期望的地址(在字典的很靠后的地方在字典的很靠后的地方)附近開附近開始查找的，這樣的查找為始查找的，這樣的查找為插值查找插值查找.52數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4插值查找基本思想插值查找基本思想 l假定表中記錄的關(guān)鍵詞假定表中記錄的關(guān)鍵詞K1K2Kn在在(K0, Kn+1)區(qū)間上呈區(qū)間上呈均勻分布均勻分布. 變元變元K給定，且給定，且K0KKn+1 ，則由均勻分布的則由均勻分布的假定，我們可用線性插值來決定假定，我們可用線性插值來決

46、定K的期望地址的期望地址n(K-K0)/(Kn+1-K0).l若若KsK1 AND NOT(found) DO ( m s+(e-s-1)(K-Ks)/(Ke-Ks) . IF KKm THEN em . IF KKm THEN sm IF K=Km THEN foundtrue) 54數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4一、線性表的查找一、線性表的查找二、樹形結(jié)構(gòu)的查找二、樹形結(jié)構(gòu)的查找8.3 二叉查找樹二叉查找樹8.4 最優(yōu)二叉查找樹最優(yōu)二叉查找樹8.5 高度平衡樹高度平衡樹8.7 B樹及其變型樹及其變型三、散列三、散列55數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-48.3.1 二叉查找樹的基本概

47、念和性質(zhì)二叉查找樹的基本概念和性質(zhì) 由上節(jié)知道，一株隱含的二叉樹結(jié)構(gòu)有助于了解對半查找和斐波那契查由上節(jié)知道，一株隱含的二叉樹結(jié)構(gòu)有助于了解對半查找和斐波那契查找之特性。用一個(gè)顯式的找之特性。用一個(gè)顯式的(explicit)二叉樹結(jié)構(gòu)，不但能對表進(jìn)行有效查找，二叉樹結(jié)構(gòu)，不但能對表進(jìn)行有效查找，而且還能迅速插入和刪除記錄。而且還能迅速插入和刪除記錄。l定義定義8.1 二叉查找樹二叉查找樹（又稱為二叉搜索樹、排序樹）（又稱為二叉搜索樹、排序樹）TB是一棵是一棵可為空的二叉樹，若可為空的二叉樹，若TB非空則其所有結(jié)點(diǎn)之關(guān)鍵詞互異，且中非空則其所有結(jié)點(diǎn)之關(guān)鍵詞互異，且中根遍歷根遍歷TB形成按關(guān)鍵詞遞

48、增序排列的結(jié)點(diǎn)序列。形成按關(guān)鍵詞遞增序排列的結(jié)點(diǎn)序列。l定義定義: 一棵一棵二叉查找樹二叉查找樹是一棵可能為空的二叉樹形，并且是一棵可能為空的二叉樹形，并且關(guān)鍵關(guān)鍵詞各不相同。詞各不相同。二叉查找樹中的任一結(jié)點(diǎn)二叉查找樹中的任一結(jié)點(diǎn)P，它的左子樹中結(jié)點(diǎn)，它的左子樹中結(jié)點(diǎn)的關(guān)鍵詞都小于的關(guān)鍵詞都小于KEY(P)，而右子樹中結(jié)點(diǎn)的關(guān)鍵詞都大于，而右子樹中結(jié)點(diǎn)的關(guān)鍵詞都大于KEY(P)，并且結(jié)點(diǎn)，并且結(jié)點(diǎn)P的左右子樹也都是二叉查找樹。的左右子樹也都是二叉查找樹。56數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4二叉查找樹和對半查找的二叉判定樹的聯(lián)系與區(qū)別。二叉查找樹和對半查找的二叉判定樹的聯(lián)系與區(qū)別。OEAU

49、IIEAUOIAEOUIAEOUIEAUO57數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-41、二叉查找樹的結(jié)點(diǎn)結(jié)構(gòu)：、二叉查找樹的結(jié)點(diǎn)結(jié)構(gòu)： LLINK和和RLINK是鏈接字段，是鏈接字段，KEY為該結(jié)點(diǎn)的關(guān)鍵詞為該結(jié)點(diǎn)的關(guān)鍵詞。2、基本操作、基本操作1）創(chuàng)建）創(chuàng)建2）查找）查找3）插入）插入4）刪除）刪除5）排序排序 LLINKKEYDATARLINK58數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-41、二叉查找樹的查找、二叉查找樹的查找 算法算法 BST (T, K . found) BST1 由根結(jié)點(diǎn)開始由根結(jié)點(diǎn)開始 PT foundfalse BST2 比較比較 WHILE Pnull AND NOT(

50、found) DO CASE DO （KKEY（P）：）：PRLINK（P）. K=KEY（P）：）：foundtrue）59數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4 設(shè)表中元素的關(guān)鍵詞設(shè)表中元素的關(guān)鍵詞K1K2Kn，則查找成功應(yīng)該終止于則查找成功應(yīng)該終止于Ri(內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn))，而查找失敗應(yīng)終止在，而查找失敗應(yīng)終止在n1個(gè)記錄間隔個(gè)記錄間隔(或者稱或者稱外結(jié)點(diǎn)，即外結(jié)點(diǎn)，即KiKKi+1的情形的情形)。60數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-42 2、二叉查找樹的創(chuàng)建、二叉查找樹的創(chuàng)建n如何建立一棵二叉查找樹。如何建立一棵二叉查找樹。 例例 有一數(shù)據(jù)集合有一數(shù)據(jù)集合53,78,65,17,87,09

51、,81,45,2353,78,65,17,87,09,81,45,23n給定各種查找情況發(fā)生的概率給定各種查找情況發(fā)生的概率i i和和i i，如何確定一棵如何確定一棵最優(yōu)最優(yōu)( (最小加權(quán)通路長度最小加權(quán)通路長度) )的二叉查找樹的二叉查找樹 ；( (靜態(tài)樹靜態(tài)樹) ) n近似最優(yōu)樹。近似最優(yōu)樹。61數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-43、二叉查找樹的插入、二叉查找樹的插入(動(dòng)態(tài)樹動(dòng)態(tài)樹) 35612OEAUI436712OEAUI5446712OEAUI3562數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4 設(shè)樹形設(shè)樹形T是一棵二叉查找樹，是一棵二叉查找樹，T中結(jié)點(diǎn)中結(jié)點(diǎn)R1, R2, , Rn相應(yīng)的

52、關(guān)鍵詞滿足相應(yīng)的關(guān)鍵詞滿足K1K2Kn, 且且KiKKi+1, 0in(K0=-, Kn+1=+). 那么插入新結(jié)點(diǎn)那么插入新結(jié)點(diǎn)K的過程的過程就是用就是用 代替第代替第i+1個(gè)外結(jié)點(diǎn)的過程個(gè)外結(jié)點(diǎn)的過程. K63數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4算法算法T ( root, K . p) /* 給定一棵以二叉查找樹形式存儲(chǔ)的記錄表，本算法查找給定一棵以二叉查找樹形式存儲(chǔ)的記錄表，本算法查找一給定變元一給定變元K . 如果如果K不在表中，則在樹的適當(dāng)位置插不在表中，則在樹的適當(dāng)位置插入包含入包含K的一個(gè)新結(jié)點(diǎn)。空子樹以空指針的一個(gè)新結(jié)點(diǎn)?？兆訕湟钥罩羔?表示，變量表示，變量root指向此樹的根

53、。指向此樹的根。*/T1. 初始化初始化 置置p root . / 指針指針p將沿樹下移將沿樹下移T2. 比比 較較 如果如果K key(p)，則轉(zhuǎn)到則轉(zhuǎn)到T4；如果；如果K key (p)，則查找成功結(jié)束，則查找成功結(jié)束.64數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4T3. 左左 移移 如果如果llink (p) ，則置，則置p llink (p)，并轉(zhuǎn)回，并轉(zhuǎn)回T2；否則轉(zhuǎn)到否則轉(zhuǎn)到T5 .T4. 右右 移移 如果如果rlink (p) ，則置，則置p rlink (p)，并轉(zhuǎn)回，并轉(zhuǎn)回T2 .T5. 插入樹形中插入樹形中 置置q AVAIL . / q為新結(jié)點(diǎn)的地址為新結(jié)點(diǎn)的地址 置置key

54、(q) K，llink (q) rlink (q) . 若若K key (p)，則置，則置llink (p) q，否則置，否則置rlink (p) q . 置置p q，本算法成功結(jié)束，本算法成功結(jié)束65數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4顯然，算法顯然，算法T的查找執(zhí)行時(shí)間與算法的查找執(zhí)行時(shí)間與算法B同階（對隨機(jī)輸入），同階（對隨機(jī)輸入），即為即為O (log 2 N)66數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-44、二叉查找樹的刪除、二叉查找樹的刪除 假定指針假定指針q指向二叉查找樹中待刪除的結(jié)點(diǎn)，則刪除指向二叉查找樹中待刪除的結(jié)點(diǎn)，則刪除q后的樹仍為二叉查找樹。后的樹仍為二叉查找樹。 刪除刪除q

55、后，由后，由q的中根后繼或者中根前驅(qū)結(jié)點(diǎn)代替的中根后繼或者中根前驅(qū)結(jié)點(diǎn)代替q，刪除過程分三種情形刪除過程分三種情形: 1) q無右兒子無右兒子； 2) q有右兒子有右兒子r，但但r無左兒子無左兒子； 3) q的右兒子的右兒子r有左兒子有左兒子。67數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4二叉查找樹的刪除二叉查找樹的刪除l分三種情況加以討論分三種情況加以討論(刪除刪除q)：（1）rlink (q) .68數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-43725237512486082689637257512486082689669數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4二叉查找樹的刪除二叉查找樹的刪除l分三種情況加

56、以討論分三種情況加以討論(刪除刪除q)：（2）rlink (q) ，且，且llink (rlink (q) ) 70數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-437252375124860826896二叉查找樹的刪除（情況二）二叉查找樹的刪除（情況二）37252312486082689671數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4二叉查找樹的刪除二叉查找樹的刪除l分三種情況加以討論分三種情況加以討論(刪除刪除q)：（3）rlink(q) ，且，且llink(rlink(q) .72數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-43725237512486082689637237512486082689673數(shù)據(jù)結(jié)構(gòu)國

57、家精品課程2022-6-4算法算法D ( q，a. )/*刪除二叉查找樹中的結(jié)點(diǎn)刪除二叉查找樹中的結(jié)點(diǎn)q,指針指針a指向結(jié)點(diǎn)指向結(jié)點(diǎn)q的父親。的父親。*/D1. rlink (q) t q . 若若rlink (t) ，則則t llink (t) ，并轉(zhuǎn)到步驟并轉(zhuǎn)到步驟D4 . / t指向取代指向取代q位置的結(jié)點(diǎn)位置的結(jié)點(diǎn)D2. llink(rlink(q) r rlink (t) . 若若llink (r) ，則，則llink (r) llink (q)，tr，轉(zhuǎn)，轉(zhuǎn)D4 .D3. llink (rlink (q) s llink (r) . 若若llink (s) ，則則r s并重復(fù)到并重

58、復(fù)到llink (s) 為止為止 . 置置llink (s) llink (t)，llink (r) rlink (s)，rlink (s) rlink (t)，t s .D4. 接樹與釋放結(jié)點(diǎn)接樹與釋放結(jié)點(diǎn)q 若若llink (a) q，則，則llink (a) t；否則；否則rlink (a) t . 然后置然后置AVAIL q . 74數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4二叉查找樹的簡單分析二叉查找樹的簡單分析l由于算法由于算法 D 左右兩邊很不對稱，有理由認(rèn)為一連串的左右兩邊很不對稱，有理由認(rèn)為一連串的隨機(jī)刪除和插入操作將使樹失去平衡，但事實(shí)上，刪隨機(jī)刪除和插入操作將使樹失去平衡，但事

59、實(shí)上，刪除操作不會(huì)使樹退化。除操作不會(huì)使樹退化。l定理定理 8.3 （T. N. Hibbard，1962）通過算法）通過算法 D 從一株從一株隨機(jī)二叉查找樹中刪除一個(gè)隨機(jī)元素之后，得到的樹隨機(jī)二叉查找樹中刪除一個(gè)隨機(jī)元素之后，得到的樹仍是隨機(jī)的。仍是隨機(jī)的。l結(jié)論結(jié)論 : 在隨機(jī)情況下，二叉查找樹操作的平均時(shí)間為在隨機(jī)情況下，二叉查找樹操作的平均時(shí)間為O (log2N) 但在特定情況下，會(huì)產(chǎn)生形同線性鏈表的但在特定情況下，會(huì)產(chǎn)生形同線性鏈表的退化的二叉查找樹形，從而使最壞情況查找時(shí)間達(dá)退化的二叉查找樹形，從而使最壞情況查找時(shí)間達(dá)O(N) .75數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4二、樹形結(jié)構(gòu)

60、的查找二、樹形結(jié)構(gòu)的查找8.3 二叉查找樹二叉查找樹8.4 最優(yōu)二叉查找樹最優(yōu)二叉查找樹8.5 高度平衡樹高度平衡樹8.7 B樹及其變型樹及其變型76數(shù)據(jù)結(jié)構(gòu)國家精品課程2022-6-4靜態(tài)樹靜態(tài)樹給定各種查找情況發(fā)生的概率給定各種查找情況發(fā)生的概率i和和i，如何確定一棵最優(yōu)如何確定一棵最優(yōu)(最最小加權(quán)通路長度小加權(quán)通路長度)的二叉查找樹的二叉查找樹 ；動(dòng)態(tài)樹動(dòng)態(tài)樹建立最優(yōu)二叉查找樹；建立最優(yōu)二叉查找樹；對對樹動(dòng)態(tài)調(diào)整，保證動(dòng)態(tài)插入刪除結(jié)點(diǎn)后，仍為最優(yōu)。樹動(dòng)態(tài)調(diào)整，保證動(dòng)態(tài)插入刪除結(jié)點(diǎn)后，仍為最優(yōu)。 缺點(diǎn)：計(jì)算復(fù)雜度高，有時(shí)結(jié)點(diǎn)出現(xiàn)的頻率無法精確統(tǒng)計(jì)。缺點(diǎn)：計(jì)算復(fù)雜度高，有時(shí)結(jié)點(diǎn)出現(xiàn)的頻率無法精確統(tǒng)計(jì)