第八章+查找5.9課件

1、查找查找1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)8查找查找查找查找2主要內(nèi)容主要內(nèi)容 查找的概念查找的概念 靜態(tài)查找表靜態(tài)查找表 線性查找線性查找 折半查找折半查找 動態(tài)查找表動態(tài)查找表 二叉查找樹、平衡二叉樹、二叉查找樹、平衡二叉樹、B-、B+樹樹 哈希查找哈希查找查找查找3n 1靜態(tài)查找表中各種方法及其運算。靜態(tài)查找表中各種方法及其運算。n 2二叉排序樹的建立、查找，插入和刪除算法。二叉排序樹的建立、查找，插入和刪除算法。n 3最佳二叉排序樹，平衡二叉樹的性質(zhì)和手工繪制。最佳二叉排序樹，平衡二叉樹的性質(zhì)和手工繪制。n 4B-樹是多路平衡外查找樹，手工模擬樹是多路平衡外查找樹，手工模擬B-樹插入和刪除。樹插入和刪

2、除。n 5散列表的建立、查找。散列表的建立、查找。n 6. 平均查找長度平均查找長度(ASL)的計算的計算重點難點重點難點查找查找4 查找表查找表: n個性質(zhì)相同的數(shù)據(jù)元素構(gòu)成的有限集合，元素間除同屬個性質(zhì)相同的數(shù)據(jù)元素構(gòu)成的有限集合，元素間除同屬一個集合外，別無聯(lián)系。一個集合外，別無聯(lián)系。 基本操作：按關(guān)鍵字查找、插入、刪除?；静僮鳎喊搓P(guān)鍵字查找、插入、刪除。 查找結(jié)果：查找結(jié)果： 查找成功查找成功(表中存在特定元素，輸出該記錄表中存在特定元素，輸出該記錄) 查找不成功查找不成功(表中不存在特定元素，表中不存在特定元素，也應(yīng)輸出失敗標志或也應(yīng)輸出失敗標志或失敗位置失敗位置)查找的概念查找的

3、概念查找查找5 靜態(tài)查找表靜態(tài)查找表 數(shù)據(jù)集合數(shù)據(jù)集合“只讀只讀”，即只能對該數(shù)據(jù)集合進行查詢操作，即只能對該數(shù)據(jù)集合進行查詢操作 動態(tài)查找表動態(tài)查找表 數(shù)據(jù)集合數(shù)據(jù)集合“可寫可寫”，即可對集合元素做插入、刪除等操，即可對集合元素做插入、刪除等操作作 注：注： 查找算法和數(shù)據(jù)存儲的結(jié)構(gòu)有關(guān)查找算法和數(shù)據(jù)存儲的結(jié)構(gòu)有關(guān)查找的概念查找的概念查找查找6 關(guān)鍵字關(guān)鍵字 數(shù)據(jù)元素中某個數(shù)據(jù)項或組合項的值數(shù)據(jù)元素中某個數(shù)據(jù)項或組合項的值 可以標識一個數(shù)據(jù)元素可以標識一個數(shù)據(jù)元素 關(guān)鍵字可以相同，即不一定唯一標識這個元素關(guān)鍵字可以相同，即不一定唯一標識這個元素 主關(guān)鍵字主關(guān)鍵字 可以可以唯一唯一標識一個記錄

4、的關(guān)鍵字標識一個記錄的關(guān)鍵字 次關(guān)鍵字次關(guān)鍵字 識別若干記錄的關(guān)鍵字識別若干記錄的關(guān)鍵字例如例如“學號學號”例如例如“女女”查找的概念查找的概念查找查找7 平均查找長度平均查找長度(Average Search Length) 查找就是不斷將數(shù)據(jù)元素的關(guān)鍵字與待查找關(guān)鍵字進行查找就是不斷將數(shù)據(jù)元素的關(guān)鍵字與待查找關(guān)鍵字進行比較，查找算法在比較，查找算法在查找成功時查找成功時平均比較的次數(shù)平均比較的次數(shù)稱作稱作平均平均查找長度查找長度 Pi：查找第：查找第i個數(shù)據(jù)元素的概率個數(shù)據(jù)元素的概率 Ci：查找該元素的過程中比較的次數(shù)：查找該元素的過程中比較的次數(shù)1niiiASLP C顯然，顯然，ASL值

5、越小，時間效率越高。值越小，時間效率越高。 查找的概念查找的概念查找查找8靜態(tài)查找表上的查找靜態(tài)查找表上的查找 集合（查找表）中的元素是無序的，由于元素間不存在邏集合（查找表）中的元素是無序的，由于元素間不存在邏輯關(guān)系，為了查找的方便，可以把元素按某種方法組織成輯關(guān)系，為了查找的方便，可以把元素按某種方法組織成順序順序表，從而可以采用表，從而可以采用順序順序表的方法來實現(xiàn)查找。表的方法來實現(xiàn)查找。 靜態(tài)查找表靜態(tài)查找表主要有三種結(jié)構(gòu)：主要有三種結(jié)構(gòu)：順序表順序表有序表有序表索引順序表索引順序表順序查找順序查找(線性查找線性查找)折半查找折半查找(二分查找二分查找)分塊查找分塊查找(索引順序查找

6、索引順序查找)查找查找9 將待查關(guān)鍵字值與查找表中各數(shù)據(jù)元素的關(guān)鍵字值一一將待查關(guān)鍵字值與查找表中各數(shù)據(jù)元素的關(guān)鍵字值一一進行比較，直至找到或確定找不到。進行比較，直至找到或確定找不到。572315645761447238查找表：查找表：舉例舉例線性查找（又稱順序查找）線性查找（又稱順序查找）60查找查找10順序表的機內(nèi)存儲結(jié)構(gòu)順序表的機內(nèi)存儲結(jié)構(gòu)typedef struct keytype key; /*關(guān)鍵字域關(guān)鍵字域*/ datatype other; /*其它域其它域*/table; 查找查找11 int seqsearch_1(table R,keytype K) 在順序表在順序表R

7、1.n中順序查找關(guān)鍵字為中順序查找關(guān)鍵字為k的結(jié)點，成功返回結(jié)的結(jié)點，成功返回結(jié)點位置，失敗返回點位置，失敗返回0。0號單元用作監(jiān)視哨號單元用作監(jiān)視哨 int i=1; R0.key=K; 設(shè)置監(jiān)視哨設(shè)置監(jiān)視哨 從表頭向后查找從表頭向后查找 while( Ri.key != K & ( i = n ) ) i+; 找不到為找不到為-1，找到則返回元素在順序表中的位置，找到則返回元素在順序表中的位置 if( i = n+1 ) return(-1); else return i; 查找查找12 int seqsearch_2(table R,keytype K) 在順序表在順序表R1.n中順序查

8、找關(guān)鍵字為中順序查找關(guān)鍵字為k的結(jié)點，成功返回結(jié)的結(jié)點，成功返回結(jié)點位置，失敗返回點位置，失敗返回0。0號單元用作監(jiān)視哨號單元用作監(jiān)視哨 int i=n; R0.key=K; 設(shè)置監(jiān)視哨設(shè)置監(jiān)視哨 從表尾向前查找從表尾向前查找 while( Ri.key != K ) i-; 找不到為找不到為-1，找到則返回元素在順序表中的位置，找到則返回元素在順序表中的位置 if( i = 0 ) return(-1); else return i; 查找查找13 監(jiān)視哨技術(shù)使順序查找在監(jiān)視哨技術(shù)使順序查找在n1000時，進行一次查找所需時，進行一次查找所需的平均時間幾乎減少一半。的平均時間幾乎減少一半。實

9、驗數(shù)據(jù)實驗數(shù)據(jù):n=1000上述算法約為上述算法約為:1.89ms 普通算法約為普通算法約為:3.70ms摘自參考書摘自參考書:E.Horowits and S.Sahni,Fundamentals of Data Structures. 監(jiān)視哨的作用監(jiān)視哨的作用查找查找14線性查找線性查找分析：分析： 查找第查找第1個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為1；查找第；查找第2個元素所需個元素所需的比較次數(shù)為的比較次數(shù)為2； ；查找第；查找第n個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為n?？傆嬋勘容^次數(shù)為總計全部比較次數(shù)為: 1+2+n = (1+n)n/2 時間復(fù)雜度時間復(fù)雜度 最好

10、情況：最好情況：O(1)第一個就是欲查找值第一個就是欲查找值 最差情況：最差情況：O(n)欲查找值在第一個單元欲查找值在第一個單元或搜索了所有的數(shù)據(jù)才得知找不到或搜索了所有的數(shù)據(jù)才得知找不到查找查找15線性查找線性查找 時間復(fù)雜度時間復(fù)雜度 平均情況：平均情況：O(n)等概率時，順序查找算法在查找成功時的平均查找等概率時，順序查找算法在查找成功時的平均查找長度：長度：查找查找不成功不成功時的比較次數(shù)為時的比較次數(shù)為 次。次。212) 1(1).21 (11nnnnnnCPASLniiin注意：若表中各數(shù)據(jù)元素被查找的概率不同，則可在存儲時注意：若表中各數(shù)據(jù)元素被查找的概率不同，則可在存儲時按查

11、找概率遞減有序，以便提高查找效率。按查找概率遞減有序，以便提高查找效率。查找查找16線性查找線性查找 順序查找的特點順序查找的特點 優(yōu)點優(yōu)點算法簡單，算法簡單，無論記錄是否按關(guān)鍵字有序均可應(yīng)用，無論記錄是否按關(guān)鍵字有序均可應(yīng)用，且對且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用 缺點缺點ASL太大，太大，特別是當特別是當n很大時，很大時，時間效率太低時間效率太低思考題：思考題：1 1、問：對、問：對單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何線性查找？如何線性查找？ 答：從頭指針開始答：從頭指針開始 “ “順藤摸瓜順藤摸瓜”2 2、問：對、問：對非線性（樹結(jié)構(gòu)）非線性（樹結(jié)構(gòu)）如何順序查找如何順序查找? ?

12、 答：答：借助各種二叉樹遍歷操作！借助各種二叉樹遍歷操作！查找查找171.將表中各數(shù)據(jù)元素按關(guān)鍵字值將表中各數(shù)據(jù)元素按關(guān)鍵字值有序排列有序排列；2.將待查關(guān)鍵字值與將待查關(guān)鍵字值與最中間最中間的數(shù)據(jù)元素的關(guān)鍵字值比較，的數(shù)據(jù)元素的關(guān)鍵字值比較，若兩者相等，則找到；若兩者相等，則找到；若待查關(guān)鍵字值較小，則在表的若待查關(guān)鍵字值較小，則在表的前半部分前半部分找；找；若待查關(guān)鍵字值較大，則在表的若待查關(guān)鍵字值較大，則在表的后半部分后半部分找。找。3.重復(fù)重復(fù)2，直至找到或確定找不到。，直至找到或確定找不到。有序表的查找有序表的查找查找查找18舉例舉例571523384457616472查找表：查找表

13、：lhm折半查找折半查找60lhm12345678查找查找19折半查找：非遞歸算法折半查找：非遞歸算法int Search_Bin1(table R, keytype k) int low = 1, high = n, mid; while(low = high) mid = (low + high)/2; /找到待查元素找到待查元素 if( k = Rmid.key ) return mid; /繼續(xù)在前或后半?yún)^(qū)間查找繼續(xù)在前或后半?yún)^(qū)間查找 if( k right，說明找不到，說明找不到查找查找20int Search_Bin2(table R,keytype k,int low,int h

14、igh) /遞歸出口遞歸出口 if(lowhigh) return 0; mid=(low+high)/2; if( k=Rmid.key ) return mid; /找到待查元素找到待查元素 else if( k Rmid.key ) /繼續(xù)在后半?yún)^(qū)間查找繼續(xù)在后半?yún)^(qū)間查找 return Search_Bin2(R,k,mid+1,high); else /繼續(xù)在前半?yún)^(qū)間查找繼續(xù)在前半?yún)^(qū)間查找 return Search_Bin2(R,k,low,mid-1);SearchBin2 折半查找：遞歸算法折半查找：遞歸算法查找查找21算法分析算法分析1523384457616472查找表：查找

15、表：lhm折半查找折半查找12345678查找查找22折半查找折半查找1523384457616472判定樹：判定樹：v判定樹每一結(jié)點對應(yīng)表中一個元素，但結(jié)點的值不是關(guān)鍵判定樹每一結(jié)點對應(yīng)表中一個元素，但結(jié)點的值不是關(guān)鍵字值，而是元素在表中的字值，而是元素在表中的位置位置。前半子表前半子表后半子表后半子表當前區(qū)間的當前區(qū)間的中間記錄中間記錄查找查找23查找查找表中表中任一元素任一元素的過程，即是判定樹中的過程，即是判定樹中從根到該元素結(jié)從根到該元素結(jié)點點的過程，比較次數(shù)為該元素的過程，比較次數(shù)為該元素結(jié)點在樹中的層次數(shù)結(jié)點在樹中的層次數(shù)。對于對于n個結(jié)點的判定樹，樹高為個結(jié)點的判定樹，樹高為k

16、 = 。折半查找在查找成功時，所進行的關(guān)鍵字比較次數(shù)至多折半查找在查找成功時，所進行的關(guān)鍵字比較次數(shù)至多為為 。) 1(log2n) 1(log2n折半查找的過程折半查找的過程查找查找24折半查找的性能折半查找的性能 平均查找長度平均查找長度 第第h層的元素有層的元素有2h-1個，找到它需要比較個，找到它需要比較h次次 等概率條件下等概率條件下 ASL ASL=(1+2+2+3+3+3+3+4)/8=21/8 查找查找不成功不成功時的比較次數(shù)：時的比較次數(shù)：1122121log (1)1log (1)1hjjjnnnnn3次或次或4次次查找查找25折半查找折半查找 總結(jié)總結(jié) 順序查找和折半查找

17、都針對靜態(tài)查找表順序查找和折半查找都針對靜態(tài)查找表 折半查找效率較高折半查找效率較高 但是但是折半查找要求數(shù)據(jù)有序折半查找要求數(shù)據(jù)有序且存儲結(jié)構(gòu)必須是順序存儲且存儲結(jié)構(gòu)必須是順序存儲(鏈表怎么折半？鏈表怎么折半？)思考題：思考題：1 1、問：能否使用、問：能否使用單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)進行折半查找？進行折半查找？ 無法實現(xiàn)！因全部元素的定位只能從頭指針無法實現(xiàn)！因全部元素的定位只能從頭指針headhead開始。開始。2 2、問：對、問：對非線性（樹結(jié)構(gòu)）非線性（樹結(jié)構(gòu)）如何折半查找如何折半查找? ? 可借助二叉排序樹來查找（屬動態(tài)查找表形式）?？山柚媾判驑鋪聿檎遥▽賱討B(tài)查找表形式）。 查找查

18、找261. 將表中各數(shù)據(jù)元素按關(guān)鍵字值分塊有序排列；將表中各數(shù)據(jù)元素按關(guān)鍵字值分塊有序排列；615 12826 18 24 21 43 28 32 47 50 83 72 6612345678910 11 12 13 14 15 16查找表：查找表：v查找方法查找方法分塊查找（索引順序查找）分塊查找（索引順序查找）查找查找27v查找方法查找方法2. 創(chuàng)建索引表，并為每個分塊創(chuàng)建一個索引項，其中記錄該塊創(chuàng)建索引表，并為每個分塊創(chuàng)建一個索引項，其中記錄該塊最大的關(guān)鍵字值及其首地址，各索引項按關(guān)鍵字值有序排列。最大的關(guān)鍵字值及其首地址，各索引項按關(guān)鍵字值有序排列。15 26 47 83615 128

19、26 18 24 21 43 28 32 47 50 83 72 6612345678910 11 12 13 14 15 16查找表：查找表：159 13最大關(guān)鍵字最大關(guān)鍵字塊起始記錄下標塊起始記錄下標索引表：索引表：分塊查找（索引順序查找）分塊查找（索引順序查找）查找查找28v查找方法查找方法3. 查找時先根據(jù)索引表確定待查元素可能位于的塊（可折半可查找時先根據(jù)索引表確定待查元素可能位于的塊（可折半可順序），再在塊內(nèi)順序查找。順序），再在塊內(nèi)順序查找。15 26 47 83615 12826 18 24 21 43 28 32 47 50 83 72 6612345678910 11 12

20、 13 14 15 16查找表：查找表：159 13最大關(guān)鍵字最大關(guān)鍵字塊起始記錄下標塊起始記錄下標索引表索引表：分塊查找（索引順序查找）分塊查找（索引順序查找）查找查找29v舉例舉例15 26 47 83615 12826 18 24 21 43 28 32 47 50 83 72 6612345678910 11 12 13 14 15 16查找表：查找表：159 13最大關(guān)鍵字最大關(guān)鍵字塊起始記錄下標塊起始記錄下標索引表：索引表：1833分塊查找（索引順序查找）分塊查找（索引順序查找）查找查找30索引表結(jié)點的數(shù)據(jù)類型定義如下：索引表結(jié)點的數(shù)據(jù)類型定義如下：#define MaxIndex

21、 typedef struct keytype key; int addr; IDtable; 在這種結(jié)構(gòu)下，查找過程要分為在這種結(jié)構(gòu)下，查找過程要分為兩步兩步：首先：首先查找索引查找索引表表。因為索引表是有序表，所以可采用二分查找或順序查。因為索引表是有序表，所以可采用二分查找或順序查找，以確定給定值所在的塊。因為塊中的記錄可以是任意找，以確定給定值所在的塊。因為塊中的記錄可以是任意排列的，所以在上一步已確定的排列的，所以在上一步已確定的塊塊中進行中進行順序查找順序查找。 查找查找31建立索引表建立索引表void CREAT_ID(int R,Idtable ID) /利用順序表建立索引表利

22、用順序表建立索引表 int i,j,k,m,s; /m為索引表下標為索引表下標 m=0; s=(n+b-1)/b; /b為塊數(shù)為塊數(shù),s為塊內(nèi)記錄數(shù)為塊內(nèi)記錄數(shù) for( i=0; in; i+=s ) /尋找每塊中的最大值尋找每塊中的最大值Rk k=i; for(j=i+1; ji+s & jRk) k=j; /將將Rk放入索引表中放入索引表中 IDm.key=Rk; IDm.addr=i; m+; 查找查找32int IdxSerch(SeqList A, IDtable index, int b,keytype k,int n) /分塊查找關(guān)鍵字為分塊查找關(guān)鍵字為k的記錄，索引表為的記錄

23、，索引表為index0.b-1 int low=0,high=b-1,mid,i; int s=(n+b-1)/b; /每塊記錄個數(shù)每塊記錄個數(shù) while(low=high) /在索引表中進行二分查找，找到的位置放在在索引表中進行二分查找，找到的位置放在low中中 mid=(low+high)/2; if(indexmid.keyk) low=mid+1; else high=mid-1; 分塊查找算法分塊查找算法查找查找33分塊查找算法（接上頁）分塊查找算法（接上頁）if(lowb) /在順序表中順序查找在順序表中順序查找 for( i=indexlow.addr; i=indexlow.

24、addr+s-1; i+) if(Ai.key=k) return i; return -1;查找查找34對索引表查找的對索引表查找的ASL對塊內(nèi)查找的對塊內(nèi)查找的ASLASL = Lb + Lw 若用若用順序查找順序查找確定所在塊，則分塊查找成功時的平均確定所在塊，則分塊查找成功時的平均查找長度為：查找長度為：1)(212121111ssnsbisjbiASLsibj 若用若用二分查找二分查找確定所在塊，則分塊查找成功時的平均確定所在塊，則分塊查找成功時的平均查找長度為：查找長度為： 2) 1(log2ssnASL查找效率查找效率ASL分析：分析：查找查找35分塊查找性能分析分塊查找性能分析

25、122ssn0222snsdsdASLbs令令ns 得得nnASLbs1此時此時 塊長度以塊長度以 為最佳為最佳n 若用若用順序查找順序查找確定所在塊，則分塊查找成功時的平均查確定所在塊，則分塊查找成功時的平均查找長度為：找長度為：1)(212121111ssnsbisjbiASLsibj查找查找36)21(log2) 1(log22nASLnssnASLbsbsS為每塊內(nèi)部的記錄個數(shù)，為每塊內(nèi)部的記錄個數(shù)，n/s即塊的數(shù)目即塊的數(shù)目例如例如:當當n=9，s=3時，時，分塊法的分塊法的 ASLbs =3.5而折半法的而折半法的 ASLlog2n=3.1順序法的順序法的 ASL =(1+n)/2

26、=5但折半法要預(yù)先全排但折半法要預(yù)先全排序，仍需時間。序，仍需時間。 若用若用二分查找二分查找確定所在塊，則分塊查找成功時的平均查確定所在塊，則分塊查找成功時的平均查找長度為：找長度為：查找效率查找效率ASL分析：分析：查找查找37算法分析算法分析15 26 47 83615 12826 18 24 21 43 28 32 47 50 83 72 6612345678910 11 12 13 14 15 16查找表：查找表：159 13最大關(guān)鍵字最大關(guān)鍵字塊起始記錄下標塊起始記錄下標索引表：索引表：ASL=查找不成功時的比較次數(shù)：查找不成功時的比較次數(shù)：最少最少4次，最多次，最多8次。次。(2

27、+3+4+5)+(3+4+5+6)+(4+5+6+7)+(5+6+7+8)/16查找效率查找效率ASL分析：分析：查找查找38 折半查找適用于一經(jīng)建立就很少變動折半查找適用于一經(jīng)建立就很少變動( (當插入或刪除操作頻當插入或刪除操作頻繁時，為維護表的有序性，勢必要移動表中很多記錄，這種由移繁時，為維護表的有序性，勢必要移動表中很多記錄，這種由移動記錄引起的額外時間開銷，就會抵消折半查找的優(yōu)點動記錄引起的額外時間開銷，就會抵消折半查找的優(yōu)點) )而查找而查找操作卻很頻繁的查找表。操作卻很頻繁的查找表。 順序查找適用于查找操作不很頻繁而經(jīng)常需要變動的查找表。順序查找適用于查找操作不很頻繁而經(jīng)常需要

28、變動的查找表。 如果要處理的查找表既希望有較高的查找效率，又需要作動如果要處理的查找表既希望有較高的查找效率，又需要作動態(tài)變化，則可以采用分塊查找的方法，這是一種折衷方案。態(tài)變化，則可以采用分塊查找的方法，這是一種折衷方案。 當表中記錄數(shù)當表中記錄數(shù)n較大，且查找、插入和刪除操作的效率均需較大，且查找、插入和刪除操作的效率均需要考慮時，采用分塊查找才有意義。要考慮時，采用分塊查找才有意義。分塊查找方法的存在有何意義？分塊查找方法的存在有何意義？查找查找39討論：討論：當有序表中各記錄的當有序表中各記錄的查找概率不相等查找概率不相等時，該如何查找？時，該如何查找？提提 醒：醒：此時用此時用折半查

29、找法未必最優(yōu)折半查找法未必最優(yōu)！改改 進：進： 若將各記錄的概率看作是二叉樹之權(quán)值，則轉(zhuǎn)為研究帶若將各記錄的概率看作是二叉樹之權(quán)值，則轉(zhuǎn)為研究帶權(quán)路徑長度最小的二叉樹（類似最優(yōu)二叉樹）。權(quán)路徑長度最小的二叉樹（類似最優(yōu)二叉樹）。查找查找40順序查找順序查找折半查找折半查找分塊查找分塊查找ASL表結(jié)構(gòu)表結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)優(yōu)優(yōu) 點點缺缺 點點最小最小log2n有序表有序表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)查找速度快查找速度快只能在順序存儲只能在順序存儲的有序表上進行的有序表上進行最大最大(n+1)/2 有序表、無序表有序表、無序表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表線性鏈表算法簡單，適應(yīng)算法簡單，適應(yīng)面廣，實

30、現(xiàn)容易面廣，實現(xiàn)容易查找速度慢查找速度慢最小最小分塊有序表分塊有序表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表線性鏈表查找速度比順序查找速度比順序查找有較大提高查找有較大提高實現(xiàn)工作量大，實現(xiàn)工作量大，且有一定難度且有一定難度靜態(tài)查找?guī)追N查找方法的比較靜態(tài)查找?guī)追N查找方法的比較查找查找41特點：特點：表結(jié)構(gòu)在查找過程中動態(tài)生成表結(jié)構(gòu)在查找過程中動態(tài)生成要求：要求： 對于給定值對于給定值key，若表中存在其關(guān)鍵字等于，若表中存在其關(guān)鍵字等于key的記錄，的記錄，則查找成功返回；則查找成功返回；否則插入關(guān)鍵字等于否則插入關(guān)鍵字等于key的記錄。的記錄。動態(tài)查找表主要有二叉樹結(jié)構(gòu)和樹結(jié)構(gòu)兩種類型。動態(tài)查找表主

31、要有二叉樹結(jié)構(gòu)和樹結(jié)構(gòu)兩種類型。二叉樹結(jié)構(gòu)有二叉排序樹、平衡二叉樹等。二叉樹結(jié)構(gòu)有二叉排序樹、平衡二叉樹等。樹結(jié)構(gòu)有樹結(jié)構(gòu)有B-樹、樹、B+樹等。樹等。動態(tài)查找表動態(tài)查找表查找查找42 二叉排序樹二叉排序樹(又稱二叉查找樹又稱二叉查找樹) 或為空樹，或為如下性質(zhì)的二叉樹：或為空樹，或為如下性質(zhì)的二叉樹： 若左子樹與右子樹不空，則若左子樹與右子樹不空，則 左子樹上所有結(jié)點的值左子樹上所有結(jié)點的值根結(jié)點的值根結(jié)點的值key) return T; else if( key key ) /左子樹左子樹 return SearchBST(T-lchild,key); else /右子樹右子樹 retur

32、n SearchBST(T-rchild,key);查找查找53二叉排序樹結(jié)點的查找二叉排序樹結(jié)點的查找算法分析算法分析ASL=(1+2+2+3+3+3+4+4)/8查找不成功時的比較次數(shù)：查找不成功時的比較次數(shù)：最少最少2次，最多次，最多4次。次。94213015361218查找查找54設(shè)已有二叉排序樹設(shè)已有二叉排序樹T，若要在其中插入結(jié)點，若要在其中插入結(jié)點e，則應(yīng)先在，則應(yīng)先在T中查找中查找e，若找到，則不必插入，若找不到，則插入位置為，若找到，則不必插入，若找不到，則插入位置為查找路徑上訪問的最后一個結(jié)點的左右孩子位置。查找路徑上訪問的最后一個結(jié)點的左右孩子位置。舉例舉例9421301

33、536121832二叉排序樹結(jié)點的二叉排序樹結(jié)點的插入插入算法算法查找查找55思路思路若二叉查找樹為若二叉查找樹為空空，則新結(jié)點插入為根，并返回，則新結(jié)點插入為根，并返回true； 若二叉查找樹若二叉查找樹非空非空，則從根結(jié)點開始進行查找。，則從根結(jié)點開始進行查找。若待查關(guān)鍵字值與根結(jié)點的關(guān)鍵字值相等，則查找成功，返若待查關(guān)鍵字值與根結(jié)點的關(guān)鍵字值相等，則查找成功，返回回false; 若待查關(guān)鍵字值較大若待查關(guān)鍵字值較大，則：，則： 若右子樹為空則新結(jié)點插入為右子樹根，返回若右子樹為空則新結(jié)點插入為右子樹根，返回true； 若右子樹非空，則從右子樹的根結(jié)點起繼續(xù)查找；若右子樹非空，則從右子樹的

34、根結(jié)點起繼續(xù)查找； 若待查關(guān)鍵字值較小若待查關(guān)鍵字值較小，則：，則： 若左子樹為空則新結(jié)點插入為左子樹根，返回若左子樹為空則新結(jié)點插入為左子樹根，返回true； 若左子樹非空，則從左子樹的根結(jié)點起繼續(xù)查找。若左子樹非空，則從左子樹的根結(jié)點起繼續(xù)查找。二叉排序樹結(jié)點的二叉排序樹結(jié)點的插入插入查找查找56二叉排序樹結(jié)點的二叉排序樹結(jié)點的插入插入int SearchBST(BiTree T,KeyType key,BiTree &p) /若在若在T中查找到值為中查找到值為key的結(jié)點，則返回的結(jié)點，則返回1，p指向該結(jié)點；指向該結(jié)點； 否則返回否則返回0，p指向查找路徑上的最后一個結(jié)點指向查找路徑上

35、的最后一個結(jié)點 /SearchBST if (T-key = key) p=T; return 1; /根結(jié)點的值等于根結(jié)點的值等于e else if(T-key key) /待查關(guān)鍵字值較小待查關(guān)鍵字值較小 if(T-lchild) return SearchBST(T-lchild, key, p); else return 0; else /待查關(guān)鍵字值較大待查關(guān)鍵字值較大 if(T-rchild) return SearchBST(T-rchild, key, p); else return 0;查找查找57 插入算法插入算法int INSERTBST(BiTree &T,KeyTyp

36、e e) /在二叉排序樹在二叉排序樹T中插入數(shù)據(jù)元素中插入數(shù)據(jù)元素e，若成功則返回，若成功則返回1，否則返回，否則返回0 /INSERTBST if (!T) /若若T為空，則新元素為空，則新元素e插入為根結(jié)點插入為根結(jié)點 T=(BiTNode *)malloc(sizeof(BiTNode); T-key=e; T-lchild=NULL; T-rchild=NULL; return 1; flag=SearchBST(T, e, p); if (!flag) /找不到找不到 s=(BiTNode *)malloc(sizeof(BiTNode); s-key=e; s-lchild=NUL

37、L; s-rchild=NULL;/生成新結(jié)點生成新結(jié)點 if (e key) p-lchild=s; /新元素新元素e插入到插入到p的左孩子的左孩子 else p-rchild=s; /新元素新元素e插入到插入到p的右孩子的右孩子 /ifreturn !flag; /找不到則成功插入，找到則無法插入找不到則成功插入，找到則無法插入查找查找58刪除刪除 設(shè)已有二叉查找樹設(shè)已有二叉查找樹T，待刪結(jié)點為，待刪結(jié)點為e，則應(yīng)先在，則應(yīng)先在T中查找中查找e，若找到，則刪除結(jié)點若找到，則刪除結(jié)點e，并對，并對T進行調(diào)整，使其仍為一棵二叉查進行調(diào)整，使其仍為一棵二叉查找樹。找樹。 由于中序遍歷二叉查找樹可

38、得到結(jié)點的有序序列，因此，由于中序遍歷二叉查找樹可得到結(jié)點的有序序列，因此，刪除結(jié)點后仍要保持是二叉查找樹；刪除結(jié)點后仍要保持是二叉查找樹； 由于用結(jié)點的前驅(qū)和后繼均可代替被刪結(jié)點的位置，刪除由于用結(jié)點的前驅(qū)和后繼均可代替被刪結(jié)點的位置，刪除算法不唯一，下面介紹算法不唯一，下面介紹2種方案（其中第種方案（其中第2種方案的算法更簡便，種方案的算法更簡便，且不增加平均查找長度）。且不增加平均查找長度）。二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除查找查找59舉例舉例待刪結(jié)點為葉子結(jié)點待刪結(jié)點為葉子結(jié)點9421301536121812二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除查找查找60舉例舉例待

39、刪結(jié)點無左子樹待刪結(jié)點無左子樹3694213015121830二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除查找查找61舉例舉例待刪結(jié)點無右子樹待刪結(jié)點無右子樹15369421301215二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除查找查找62舉例舉例待刪結(jié)點既有左子樹，又有右子樹待刪結(jié)點既有左子樹，又有右子樹21303691512189427 方案一方案一二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除查找查找63舉例舉例待刪結(jié)點既有左子樹，又有右子樹待刪結(jié)點既有左子樹，又有右子樹21303691512189427二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除 方案一方案一查找查找64舉例舉例待刪結(jié)

40、點既有左子樹，又有右子樹待刪結(jié)點既有左子樹，又有右子樹94213015361218972714二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除 方案二方案二查找查找65942130153612189122714二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除舉例舉例待刪結(jié)點既有左子樹，又有右子樹待刪結(jié)點既有左子樹，又有右子樹 方案二方案二查找查找66int DeleteBST(BiTree &T, KeyType key) /找到待刪除的結(jié)點找到待刪除的結(jié)點 if (!T) return 0; else if (key = T-key) Delete(T); return 1; else if (ke

41、y key) return DeleteBST(T-lchild, key); else return DeleteBST(T-rchild, key);DeleteBST 二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除查找查找67void Delete(BiTree &p) /p指向待刪結(jié)點，實參為待刪結(jié)點的雙親結(jié)點的指向待刪結(jié)點，實參為待刪結(jié)點的雙親結(jié)點的lchild指針或指針或rchild指指針，當待刪結(jié)點為二叉排序樹的根結(jié)點時，即為根指針針，當待刪結(jié)點為二叉排序樹的根結(jié)點時，即為根指針 if (!p-rchild) /待刪結(jié)點無右子樹待刪結(jié)點無右子樹 q = p; p = p-lchil

42、d; free(q); else if (!p-lchild) /待刪結(jié)點有右子樹，但無左子樹待刪結(jié)點有右子樹，但無左子樹 q = p; p = p-rchild; free(q); else /被刪除結(jié)點的左、右子樹均不空，用左子樹最右下結(jié)點替換被刪除結(jié)點的左、右子樹均不空，用左子樹最右下結(jié)點替換 q = p; s = p-lchild; while (s-rchild) q = s; s = s-rchild; /使使s指向最右下結(jié)點，指向最右下結(jié)點，q指向指向s的雙親的雙親 p-key = s-key; /以以s的值替換的值替換p的值的值 /s必無右子樹，重接必無右子樹，重接s的左子樹的

43、左子樹 if (q != p) q-rchild = s-lchild; else q-lchild = s-lchild;/p的左子樹最右下結(jié)點就是其的左子樹最右下結(jié)點就是其 左子樹的根左子樹的根 free(s); 查找查找68ABCDif (!p-rchild) /待刪結(jié)點無右子樹待刪結(jié)點無右子樹 q = p; p = p-lchild; free(q);二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除pq查找查找69/被刪除結(jié)點的左、右子樹均不空，被刪除結(jié)點的左、右子樹均不空，用左子樹最右下結(jié)點替換用左子樹最右下結(jié)點替換 q = p;s = p-lchild;while (s-rchild)

44、 q = s; s = s-rchild;p-data = s-data;二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除BCDFEAGpqsF查找查找70pqsABGB/被刪除結(jié)點的左、右子樹均不空，被刪除結(jié)點的左、右子樹均不空，用左子樹最右下結(jié)點替換用左子樹最右下結(jié)點替換 q = p;s = p-lchild;while (s-rchild) q = s; s = s-rchild;p-data = s-data;二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除查找查找71if (q != p) q-rchild = s-lchild;else q-lchild = s-lchild;free(s

45、);二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除FFBCDEGHpsq查找查找72if (q != p) q-rchild = s-lchild;else q-lchild = s-lchild;free(s);二叉排序樹上結(jié)點的刪除二叉排序樹上結(jié)點的刪除ABpqsGBC查找查找735845439832405570639010自測題自測題:二叉排序樹上刪除二叉排序樹上刪除10或或40或或45或或55查找查找74二叉排序樹的查找分析二叉排序樹的查找分析 查找算法的效率查找算法的效率 查找的次數(shù)查找的次數(shù) = 樹的高度樹的高度 因此復(fù)雜度因此復(fù)雜度=O(h)，問題是，問題是h=？查找查找75二叉排

46、序樹的查找分析二叉排序樹的查找分析分析平均查找長度，假設(shè)分析平均查找長度，假設(shè)7個記錄的查找概率相等，即為個記錄的查找概率相等，即為1/7。71773333221)(aASL72877654321)(bASL(a)(b)圖圖(b)樹的平均查找長度為：樹的平均查找長度為：圖圖(a)樹的平均查找長度為：樹的平均查找長度為：h = log2n +1h = n所以二叉排序樹需要平衡，使得查找復(fù)雜度可以達到所以二叉排序樹需要平衡，使得查找復(fù)雜度可以達到O(log2n)查找查找76最壞情況：最壞情況： 插入的插入的n個元素從一開始就有序（單調(diào)增或減），個元素從一開始就有序（單調(diào)增或減），變成變成了單支樹的

47、形態(tài)！了單支樹的形態(tài)！ 此時樹的深度為此時樹的深度為n; ASL= (n+1)/2 與線性查找的與線性查找的ASL相同！相同！二叉排序樹的查找分析二叉排序樹的查找分析查找查找77二叉排序樹的查找分析二叉排序樹的查找分析最好情況：最好情況： 與折半查找中的判定樹相同（即形態(tài)比較均衡）與折半查找中的判定樹相同（即形態(tài)比較均衡）樹的深度為：樹的深度為： log2n +1；ASLlog2(n+1)1最佳二叉排序樹最佳二叉排序樹定義定義：平均查找長度最小的二叉排序樹。：平均查找長度最小的二叉排序樹。舉例：舉例：形如滿二叉樹或完全二叉樹的形如滿二叉樹或完全二叉樹的二叉排序樹。二叉排序樹。非常難于構(gòu)造。非常

48、難于構(gòu)造。折中：平衡二叉樹。折中：平衡二叉樹。查找查找78平衡二叉樹平衡二叉樹 平衡二叉樹平衡二叉樹(AVL樹樹) Adelson-Velskii 和和 Landis 發(fā)明發(fā)明 或者是空樹或者是空樹 或者：或者：左右子樹都是左右子樹都是AVL樹樹且左右子樹的深度之差不超過且左右子樹的深度之差不超過1查找查找79一棵平衡二叉樹一棵平衡二叉樹134726521567384一棵非平衡二叉樹一棵非平衡二叉樹目標調(diào)整：目標調(diào)整：對任意給定的關(guān)鍵字序列，從空二叉樹起構(gòu)造一對任意給定的關(guān)鍵字序列，從空二叉樹起構(gòu)造一棵平衡的二叉查找樹?？闷胶獾亩娌檎覙?。平衡二叉樹平衡二叉樹查找查找80typedef str

49、uct AVLNode int key; int bf; /結(jié)點的平衡因子結(jié)點的平衡因子 struct AVLNode *lchild,*rchild; /左、右孩子指針左、右孩子指針 AVLNode,*AVLTree; 平衡二叉樹的類型定義平衡二叉樹的類型定義查找查找81思路：思路： 1.空樹顯然平衡；空樹顯然平衡； 2.向一棵平衡的二叉查找樹中插入一個結(jié)點，若插入后造向一棵平衡的二叉查找樹中插入一個結(jié)點，若插入后造成不平衡，則進行平衡處理；成不平衡，則進行平衡處理； 3.重復(fù)重復(fù)2直至所有結(jié)點插入完畢。直至所有結(jié)點插入完畢。問題：問題： 1.如何知道插入結(jié)點后的二叉樹是否平衡？如何知道插入

50、結(jié)點后的二叉樹是否平衡？2.結(jié)點的插入是怎樣造成二叉樹不平衡的？如何處理？結(jié)點的插入是怎樣造成二叉樹不平衡的？如何處理？平衡二叉樹平衡二叉樹查找查找82思路細化思路細化1： 為能判定當前二叉查找樹是否平衡，即當前二叉查找樹為能判定當前二叉查找樹是否平衡，即當前二叉查找樹中各結(jié)點的左、右子樹深度之差的絕對值是否均不超過中各結(jié)點的左、右子樹深度之差的絕對值是否均不超過1，特定義特定義 若二叉查找樹中各結(jié)點的平衡因子均為若二叉查找樹中各結(jié)點的平衡因子均為-1、0或或1，則二，則二叉查找樹平衡，否則失衡。叉查找樹平衡，否則失衡。如何知道插入結(jié)點后的二叉樹是否平衡？如何知道插入結(jié)點后的二叉樹是否平衡？

51、結(jié)點的平衡因子結(jié)點的平衡因子=該結(jié)點該結(jié)點左左子樹的深度子樹的深度-該結(jié)點該結(jié)點右右子樹的深度。子樹的深度。平衡二叉樹平衡二叉樹查找查找83舉例：舉例：平衡二叉樹平衡二叉樹2412455393-10100查找查找84思路細化思路細化2：結(jié)點插入前，二叉查找樹平衡，各結(jié)點的平衡因子均為結(jié)點插入前，二叉查找樹平衡，各結(jié)點的平衡因子均為-1、0或或1；插入的新結(jié)點必為葉子結(jié)點，平衡因子為；插入的新結(jié)點必為葉子結(jié)點，平衡因子為0，而，而其雙親結(jié)點由于左其雙親結(jié)點由于左/右子樹長高，平衡因子將發(fā)生變化。右子樹長高，平衡因子將發(fā)生變化。結(jié)點的插入是怎樣造成二叉樹不平衡的？結(jié)點的插入是怎樣造成二叉樹不平衡的

52、？371 12412455393-1-10 00 00 00 00 0舉例：舉例：平衡二叉樹平衡二叉樹查找查找85如果新結(jié)點的插入導(dǎo)致其雙親結(jié)點為根的子樹長高，則如果新結(jié)點的插入導(dǎo)致其雙親結(jié)點為根的子樹長高，則其祖父母結(jié)點的平衡因子也將發(fā)生變化。其祖父母結(jié)點的平衡因子也將發(fā)生變化。舉例：舉例：3702412455393-10000400-11-1思路細化思路細化2：結(jié)點的插入是怎樣造成二叉樹不平衡的？結(jié)點的插入是怎樣造成二叉樹不平衡的？平衡二叉樹平衡二叉樹查找查找86 若某結(jié)點的平衡因子從若某結(jié)點的平衡因子從1變到變到2，或從，或從-1變到變到-2，則需對，則需對以該結(jié)點為根的子樹進行平衡處理

53、。以該結(jié)點為根的子樹進行平衡處理。舉例：舉例：12412455393-10008021待平衡處理待平衡處理思路細化思路細化2：結(jié)點的插入是怎樣造成二叉樹不平衡的？結(jié)點的插入是怎樣造成二叉樹不平衡的？平衡二叉樹平衡二叉樹查找查找87思路細化思路細化3： 失衡后如何處理？失衡后如何處理？ 不平衡的狀態(tài)可以分為不平衡的狀態(tài)可以分為LL、RR、LR和和RL四種類型。四種類型。 四種不平衡狀態(tài)的判斷：四種不平衡狀態(tài)的判斷： 根據(jù)插入結(jié)點根據(jù)插入結(jié)點B與它最接近的平衡因子絕對值大于與它最接近的平衡因子絕對值大于1（|BF|1）的結(jié)點）的結(jié)點A的位置來判斷，的位置來判斷， - 若若B在在A的左邊的左邊，則為

54、的左邊的左邊，則為LL型；型； - 若若B在在A的右邊的右邊，則為的右邊的右邊，則為RR型；型； - 若若B在在A的左邊的右邊，則為的左邊的右邊，則為LR型；型； - 若若B在在A的右邊的左邊，則為的右邊的左邊，則為RL型。型。 平衡二叉樹平衡二叉樹查找查找880B1Ah-112h-1 分情況討論分情況討論 以以A為子樹根的子樹就這為子樹根的子樹就這4種情況：種情況：平衡二叉樹平衡二叉樹(1)LL型型查找查找890B1Ah-1-1-2h-1(2)RR型型平衡二叉樹平衡二叉樹查找查找900B1Ah-1-12h-10Ch-21(3)LR型型平衡二叉樹平衡二叉樹查找查找910B-1Ah-11-2h-

55、10Ch-21(4)RL型型平衡二叉樹平衡二叉樹查找查找92一一. 左單旋轉(zhuǎn)（左單旋轉(zhuǎn)（LL型的處理）型的處理） 二二. 右單旋轉(zhuǎn)（右單旋轉(zhuǎn)（RR型的處理）型的處理） 三三. 先左后右雙向旋轉(zhuǎn)（先左后右雙向旋轉(zhuǎn)（LR型的處理）型的處理）四四. 先右后左雙向旋轉(zhuǎn)（先右后左雙向旋轉(zhuǎn)（RL型的處理）型的處理）調(diào)節(jié)最小不平衡子樹調(diào)節(jié)最小不平衡子樹非平衡二叉樹的調(diào)整非平衡二叉樹的調(diào)整查找查找93 各個擊破各個擊破右旋右旋1B2Ah-1BLh-1BRAR0B0ABLBRAR非平衡二叉樹的調(diào)整非平衡二叉樹的調(diào)整 (1)LR型型查找查找94插入插入F1A0B0C0D0E0F1C1B2A0A0B1C0D0E0F

56、調(diào)整后調(diào)整后調(diào)整方法：調(diào)整方法： 將將A順時針旋轉(zhuǎn)順時針旋轉(zhuǎn)，成為其左子樹根，成為其左子樹根B的的右子樹右子樹，而原來，而原來B的的右子樹右子樹則變成則變成A的的左子樹左子樹。查找查找95LL型調(diào)整的兩個例子型調(diào)整的兩個例子13125016012025160310(a)BL、BR、AR 都是空樹都是空樹 (b)BL、BR、AR 都是非空樹都是非空樹 0312504701628009011202516131092800470查找查找96左旋左旋1B2Ah-1BRh-1BLAL0B0ABRBLAL非平衡二叉樹的調(diào)整非平衡二叉樹的調(diào)整 (2)RR型型查找查找97-1A0B0D0E0C插入插入F0F-

57、1E-1C-2A調(diào)整方法：調(diào)整方法： 將將A逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)，成為其右子樹根，成為其右子樹根C的的左子樹左子樹，而原來，而原來C的的左左子樹子樹則變成則變成A的的右子樹右子樹。0B0D調(diào)整后調(diào)整后0F-1E0C0A查找查找98RR型調(diào)整的兩個例子型調(diào)整的兩個例子(a)BL、BR、AR 都是空樹都是空樹 69-1314700-1-2047310690(b)BL、BR、AR 都是非空樹都是非空樹 -131250470406900760-1-1-204731069-1407600250查找查找99先左旋后右旋先左旋后右旋0B0C-1ABLCLCRAR-1B2ABLh-11Ch-2CLCRARh-

58、1非平衡二叉樹的調(diào)整非平衡二叉樹的調(diào)整 (3)LR型型查找查找1000C0D插入插入F0F0E1A0B-1D-1B2A調(diào)整方法：調(diào)整方法： 將將A的的左孩子左孩子B的右子樹的根的右子樹的根D變變A與與B之間，之間，使之成為使之成為LL型，再型，再按按LL型處理（即型處理（即再把再把A順時針旋轉(zhuǎn)順時針旋轉(zhuǎn)，成為其左子樹根，成為其左子樹根D的的右子樹右子樹，而原來而原來D的的右子樹右子樹則變成則變成A的的左子樹左子樹）。）。0C調(diào)整后調(diào)整后0F0E0D1B0A查找查找101LR型調(diào)整的兩個例子型調(diào)整的兩個例子(a)LR(L)型調(diào)整型調(diào)整1312504702826001601-1202825031-

59、1264700160(b)LR(R)型調(diào)整型調(diào)整131250470280160300-1-12028251310300160470查找查找102先右旋后左旋先右旋后左旋-1B0C0ABRCRCLAL1B-2ABRh-11Ch-2CRCLALh-1非平衡二叉樹的調(diào)整非平衡二叉樹的調(diào)整 (4)RL型型查找查找1030D插入插入F0F0E-1A0B0C1D1C-2A調(diào)整方法：調(diào)整方法： 需進行兩次旋轉(zhuǎn)操作需進行兩次旋轉(zhuǎn)操作(先順時針，后逆時針先順時針，后逆時針)，即先將，即先將A的的右孩右孩子子C的左子樹的根的左子樹的根D變到變到A與與C之間，使之成為之間，使之成為RR型，再按型，再按RR型處理型處理（即將（即將A逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)，成為其右子樹根，成為其右子樹根D的的左