數(shù)據(jù)結(jié)構(gòu)與算法第五章查找

1、主講老師：劉斌Email: nj_QQ：12634473395.0 術(shù)語和約定術(shù)語和約定5.1 線性查找線性查找5.2 折半查找折半查找5.3 分塊查找分塊查找5.4 二元查找樹二元查找樹5.5 AVL樹樹5.6 B-樹與樹與B+樹樹5.8 散列法散列法知識點(diǎn)：n 各種查找結(jié)構(gòu)的性質(zhì)n 靜態(tài)環(huán)境下查找算法的設(shè)計思想、實(shí)現(xiàn)方法n 動態(tài)環(huán)境下查找算法的設(shè)計思想、實(shí)現(xiàn)方法n 各種查找方法的時間性能的分析方法重點(diǎn)：n 靜態(tài)和動態(tài)環(huán)境下查找算法的設(shè)計思想、實(shí)現(xiàn)方法難點(diǎn)：n 動態(tài)環(huán)境下查找算法的設(shè)計思想、實(shí)現(xiàn)方法l 查找表：由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。l 關(guān)鍵字：數(shù)據(jù)元素中某個或某些數(shù)據(jù)項(xiàng)的

2、值，用以標(biāo)識一個數(shù)據(jù)元素（或記錄）。l 查找：根據(jù)給定的值，在查找表中確定一個關(guān)鍵字值等于給定值的數(shù)據(jù)元素或記錄。若找到與該值匹配的關(guān)鍵字，則查找成功；否則，查找失敗。l 查找的分類查找的環(huán)境 靜態(tài)查找：查找+提取數(shù)據(jù)元素屬性信息在靜態(tài)環(huán)境下，被查找的數(shù)據(jù)集合經(jīng)查找之后并不改變，就是說，既不插入新的記錄，也不刪除原有記錄。 動態(tài)查找：查找+（插入或刪除元素）在動態(tài)環(huán)境下，被查找的數(shù)據(jù)集合經(jīng)查找之后可以改變，就是說，可以插入新的記錄，也可以刪除原有記錄。定義在查找表上的主要操作l SEARCH(k , F)：在數(shù)據(jù)集合(查找表、文件) F 中查找關(guān)鍵字值等于k 的數(shù)據(jù)元素（記錄）。若查找成功，則

3、返回包含k 的記錄的位置；否則，返回一個特定的值。l INSERT(R, F)：在動態(tài)環(huán)境下的插入操作。在F中查找記錄R，若查找不成功，則插入R；否則不插入R。l DELETE(k, F)：在動態(tài)環(huán)境下的刪除操作。在F 中查找關(guān)鍵字值等于k 的數(shù)據(jù)元素（記錄）。若查找成功，則刪除關(guān)鍵字值等于k 的記錄，否則不刪除任何記錄。定義在查找表上的主要操作l SEARCH(k , F)：在數(shù)據(jù)集合(查找表、文件) F 中查找關(guān)鍵字值等于k 的數(shù)據(jù)元素（記錄）。若查找成功，則返回包含k 的記錄的位置；否則，返回一個特定的值。l INSERT(R, F)：在動態(tài)環(huán)境下的插入操作。在F中查找記錄R，若查找不成

4、功，則插入R；否則不插入R。l DELETE(k, F)：在動態(tài)環(huán)境下的刪除操作。在F 中查找關(guān)鍵字值等于k 的數(shù)據(jù)元素（記錄）。若查找成功，則刪除關(guān)鍵字值等于k 的記錄，否則不刪除任何記錄。查找分類：l 基于關(guān)鍵字的查找1 線性查找2 折半查找3 分塊查找4 二元樹查找l 基于關(guān)鍵字存儲位置的查找 散列法（外查找、內(nèi)查找）l 查找表結(jié)點(diǎn)（數(shù)據(jù)元素、記錄)的類型定義 struct records keytype key; fields other; ;l 查找的性能指標(biāo)平均查找長度 定義: 為確定記錄在查找表中的位置，需要把給定值與關(guān)鍵字進(jìn)行比較的次數(shù)的期望值稱為查找算法在查找成功時的平均查找

5、長度(Average Search Length)。 設(shè)Pi為查找表中第i 個記錄的概率，Pi=1，Ci為查找第i個記錄所進(jìn)行的比較次數(shù)，則在等概率情況下，即Pi = 1/n 時，一、線性查找 把數(shù)據(jù)集合或文件組織成線性表，從線性表的一端開始，依次比較其中每個數(shù)據(jù)元素或記錄的關(guān)鍵字。二、順序表上的查找適合于靜態(tài)查找1. 數(shù)據(jù)結(jié)構(gòu)定義（類型定義）typedef records LISTmaxsize ;LIST F ;2. SEARCH操作的實(shí)現(xiàn)3. INSERT操作的實(shí)現(xiàn)（不適合）4. DELETE操作的實(shí)現(xiàn)（不適合）int SEARCH (keytype k, int last, LIST

6、F )/* 在F1Flast中查找關(guān)鍵字為k的記錄，若找到，則返回該記錄所在的下標(biāo)，否則返回0*/ int i ; F0.key = k ; /*F0為偽記錄或哨兵*/ i = last ; while ( Fi.key != k ) i = i 1 ; return i ;/* ASL=(n+1)/2, 時間復(fù)雜性O(shè)( n ) */三、單鏈表上的查找既適合于靜態(tài)也適合于動態(tài)查找既適合于靜態(tài)也適合于動態(tài)查找1. 數(shù)據(jù)結(jié)構(gòu)定義（類型定義）數(shù)據(jù)結(jié)構(gòu)定義（類型定義）struct celltype records data ;celltype * next ;typedef celltype * LI

7、ST2. 查找操作的實(shí)現(xiàn)查找操作的實(shí)現(xiàn)3. INSERT操作的實(shí)現(xiàn)操作的實(shí)現(xiàn)4. DELETE操作的實(shí)現(xiàn)操作的實(shí)現(xiàn)一、二叉查找樹（二叉搜索樹、二叉分類（排序）樹） 二叉查找樹或者是空樹，或者是滿足下列性質(zhì)的二叉樹：u 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字的值都小于根結(jié)點(diǎn)關(guān)鍵字的值；u 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字的值都大于根結(jié)點(diǎn)關(guān)鍵字的值；u 它的左、右子樹本身又是一個二叉查找樹。一、二叉查找樹（二叉搜索樹、二叉分類（排序）樹）二叉搜索樹、二叉分類（排序）樹）u 二叉查找中任意一個結(jié)點(diǎn)X 的關(guān)鍵字，都大于(小于)其左(右)子樹中任意結(jié)點(diǎn)Y的關(guān)鍵字，因此各結(jié)點(diǎn)的關(guān)鍵字互不

8、相同；u 按中序遍歷二叉查找樹所得的中序序列是一個遞增的有序序列；u 同一個數(shù)據(jù)集合，可按關(guān)鍵字表示成不同的二叉查找樹，即同一數(shù)據(jù)集合的二叉查找樹不唯一；但中序序列相同。u 每個結(jié)點(diǎn)X的右子樹的最左結(jié)點(diǎn)Y，稱為X的繼承結(jié)點(diǎn)。有如下性質(zhì)： (1)在此右子樹中，其關(guān)鍵字值最小，但大于X的關(guān)鍵字； (2)最多有一個右子樹，即沒有左子樹。二、二叉查找樹的存儲結(jié)構(gòu)typedef struct celltype records data ; struct celltype *lchild,*rchild ; BSTNode；typedef BSTNode * BST ;三、SEARCH查找操作的實(shí)現(xiàn)查找操

9、作的實(shí)現(xiàn)算法要點(diǎn)：設(shè)F 為二叉查找數(shù)的根結(jié)點(diǎn)的指針，k 為已知的關(guān)鍵字。在F 中查找關(guān)鍵字為k 的記錄如下： 1. 若F = NULL，則查找失?。环駝t， 2. k =F-data.key，則查找成功；否則， 3. k data.key，則查找F 所指結(jié)點(diǎn)的左子樹；否則， 4. k F-data.key，則查找F 所指結(jié)點(diǎn)的右子樹。BSTNode * SearchBST( keytype k, BST F ) BSTNode * p = F ; if ( p = NULL | k = p-data.key ) /* 遞歸終止條件*/ return p; if ( k data.key ) re

10、turn ( SearchBST ( k, p-lchild ) ) ; /* 查找左子樹*/ else return ( SearchBST ( k, p-rchild ) ) ; /* 查找右子樹*/四、INSERT操作的實(shí)現(xiàn)操作的實(shí)現(xiàn)/*二叉查找樹二叉查找樹F 的類型定義的類型定義*/void InsertBST ( records R , BST F ) / 在二叉查找樹F 中插入新記錄R if ( F =NULL ) F = new BSTNode ; F-data = R ; F-lchild = NULL ; F-rchild = NULL ; else if ( R.key d

11、ata.key ) InsertBST( R , F-lchild )； else if ( R.key F-data.key ) InsertBST( R , F-rchild )； /* 若若R.key=F-data.key，則返回，則返回*/五、二叉查找樹的建立的建立BST CreateBST ( void ) BST F = NULL; /*初始時初始時F為空為空*/ keytype key; cinkey其他字段其他字段;/*讀入一個記錄讀入一個記錄*/ while( key )/*假設(shè)假設(shè)key=0是輸入結(jié)束標(biāo)志是輸入結(jié)束標(biāo)志 */ InsertBST( R , F )；/* 插入

12、記錄插入記錄R */ cinkey其他字段其他字段/*讀入下個記錄讀入下個記錄*/ return F;/*返回建立的二叉查找樹的根返回建立的二叉查找樹的根*/ 注意：在建立二叉查找樹時，若按關(guān)鍵字有序順序輸入各記錄，則產(chǎn)生退化的二叉查找樹單鏈表。如何防止？u 隨機(jī)輸入各結(jié)點(diǎn)u 在建立、插入和刪除各結(jié)點(diǎn)過程中平衡相關(guān)結(jié)點(diǎn)的左、右子樹。六、DELETE操作的實(shí)現(xiàn)操作的實(shí)現(xiàn) 在二叉查找樹中刪除結(jié)點(diǎn)，不能破壞二叉查找樹的結(jié)構(gòu)性質(zhì)，可按如下三種情況分別處理： 1) 如果刪除的是葉結(jié)點(diǎn)，則直接刪除，不會破壞二叉查找樹的結(jié)構(gòu)性質(zhì)； 2) 如果刪除的結(jié)點(diǎn)只有一棵左子樹或右子樹，則直接繼承：將該子樹移到被刪結(jié)點(diǎn)

13、位置； 3) 如果刪除的結(jié)點(diǎn)有兩棵子樹，則用繼承結(jié)點(diǎn)代替被刪結(jié)點(diǎn)，這相當(dāng)于刪除繼承結(jié)點(diǎn)按1) 或2) 處理繼承結(jié)點(diǎn)。在二叉查找樹中刪除結(jié)點(diǎn)records deletemin(BST &F ) records tmp ; BST p ; if ( F-lchild = NULL ) p = F ; tmp = F-data ; F = F-rchild ; delete p ; return tmp ; else return(deletemin( F-lchild) ;DeleteB( keytype k, BST &F ) if ( F != NULL ) if ( k data.key )

14、 DeleteB( k, f-lchild ) ; else if ( k F-data.key ) DeleteB( k, f-rchild ); else if ( F-rchild = NULL ) F = F-lchild ; else if( F-lchild = NULL ) F = F-rchild ; else F-data =deletemin(F-rchild);在二叉查找樹的性能評價u 二叉查找樹上進(jìn)行查找的平均長度和二叉樹的形態(tài)有關(guān)。u 在最壞情況下，二叉查找樹是通過把有序表的n 個結(jié)點(diǎn)依次插入而生成的，此時所得到的二叉查找樹退化為一株高度為n 的單支樹，它的平均查找長

15、度和單鏈表上的順序查找相同，(n+1)/2。u 在最好情況下，二叉查找樹的形態(tài)比較均勻，最終得到一株形態(tài)與折半查找的判定樹相似，此時的平均查找長度約為log 2 n。u 二叉查找樹的平均高度為O(log 2 n)。因此平均情況下，三種操作的平均時間復(fù)雜性為O(log 2 n)u 就平均性能而言，二叉查找樹上的查找和二分查找差不多。u 就維護(hù)表的有序性而言，二叉查找樹更有效。 二叉搜索樹上實(shí)現(xiàn)查找的時間復(fù)雜度與從根節(jié)點(diǎn)到所查對象節(jié)點(diǎn)的路徑成正比，最壞情況下等于樹的高度。 在構(gòu)造二叉搜索樹時，如果輸入對象的序列恰好是按其關(guān)鍵碼大小有序，則結(jié)果將產(chǎn)生一棵單支樹。 在這樣的樹上查找所需要的時間是O(n

16、)（與節(jié)點(diǎn)個數(shù)成正比）。u 例如：輸入序列為11,39,46,38,751139466875平衡樹平衡樹（Balanced Tree）：高度為O(logn)的樹。平衡二叉樹平衡二叉樹（Balanced Binary Tree）：由阿德爾森一維爾斯和蘭迪斯（Adelson-Velskii and Landis）于1962年首先提出的，所以又稱為AVL樹。一、平衡二叉樹的定義 空二叉樹是AVL樹； 如果T是一棵非空的二叉搜索樹，TL和TR分別是其左子樹和右子樹，那么當(dāng)T滿足以下條件時，T是一棵AVL樹： 1）TL和TR 是AVL樹； 2）|hL-hR|1，hL和hR分別是左子樹和右子樹的高度391

17、168823467571681175846713923二、平衡二叉樹的特點(diǎn) n個元素的AVL樹的高度是O(logn)； 一棵n元素的AVL搜索樹能在O(高度)=O(logn) 的時間內(nèi)完成搜索； 將一個新元素插入到一棵n元素的AVL搜索樹中，可得到一棵n+1元素的AVL樹，這種插入過程可以在O(logn)時間內(nèi)完成； 從一棵n元素的AVL搜索樹中刪除一個元素，可得到一棵n-1元素的AVL樹，這種刪除過程可以在O(logn)時間內(nèi)完成。三、平衡二叉樹的平衡因子 為每個節(jié)點(diǎn)增加一個平衡因子bf。節(jié)點(diǎn)x 的平衡因子bf (x)定義為：bf (x)= hL-hR 。即：x的左子樹的高度-x 的右子樹的

18、高度。 從AVL樹的定義可以知道，平衡因子的可能取值為-1、0、1。 如果樹中任意一個結(jié)點(diǎn)的平衡因子的絕對值大于 1，則這棵二叉樹就失去平衡。四、AVL樹的搜索 如果一棵AVL樹有n個節(jié)點(diǎn)，其高度可以保持在O(logn)，因此平均搜索長度也可以保持在O(logn)。 二叉搜索樹的算法完全適用于AVL樹。五、AVL樹的插入 若一棵二叉搜索樹是平衡二叉樹，插入某個節(jié)點(diǎn)后，可能會變成非平衡二叉樹； 【解決辦法】對該二叉樹進(jìn)行平衡處理，使其變成一棵平衡二叉樹。非非AVLAVL樹的平衡化處理樹的平衡化處理 每插入一個新節(jié)點(diǎn)時，AVL樹中相關(guān)節(jié)點(diǎn)的平衡狀態(tài)會發(fā)生改變。 因此，在插入一個新節(jié)點(diǎn)后，需要從插入

19、位置沿通向根的路徑回溯，檢查各節(jié)點(diǎn)的平衡因子（左、右子樹的高度差）； 如果在某一節(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯； 從發(fā)生不平衡的節(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的節(jié)點(diǎn)，做平衡化旋轉(zhuǎn)。平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)有兩類： 單旋轉(zhuǎn)（LL旋轉(zhuǎn)和LR旋轉(zhuǎn)） 雙旋轉(zhuǎn)（LR旋轉(zhuǎn)和RL旋轉(zhuǎn)）如果這三個節(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。如果這三個節(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。LL旋轉(zhuǎn)RR旋轉(zhuǎn)LR雙旋轉(zhuǎn)RL雙旋轉(zhuǎn)432234201518607065平衡化旋轉(zhuǎn)若在若在 C 的的左子樹的左子樹上插入左子樹的左子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 C 的平衡因子從的平衡因子從 1 增加增加 至至 2， 需要

20、進(jìn)行一次需要進(jìn)行一次順時針旋轉(zhuǎn)。順時針旋轉(zhuǎn)。 (以以 B 為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 若在若在 A 的的右子樹的右子樹上插入右子樹的右子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 A 的平衡因子從的平衡因子從 -1 改變改變?yōu)闉?-2，需要進(jìn)行一次，需要進(jìn)行一次逆時針旋轉(zhuǎn)。逆時針旋轉(zhuǎn)。(以以 B 為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）2) RR 平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： 1) LL 平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： 31ACCBCABA平衡化旋轉(zhuǎn)若在若在 A 的的右子樹的左子樹上插入右子樹的左子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 A 的平衡因子從的平衡因子從 -1 改變改變 為為 -2，需要，需要先進(jìn)行順時針旋轉(zhuǎn)，再先進(jìn)行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。逆時針旋

21、轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn) B 為為旋轉(zhuǎn)軸）旋轉(zhuǎn)軸） 4) RL 平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： 若在若在 C 的的左子樹的右子樹上插入左子樹的右子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 C 的平衡因子從的平衡因子從 1 增加增加 至至 2， 需要需要先進(jìn)行逆時針旋轉(zhuǎn)，先進(jìn)行逆時針旋轉(zhuǎn)， 再順時針旋轉(zhuǎn)。再順時針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn) B 為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 3) LR 平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： BBCAABCCABACBACCBA平衡化旋轉(zhuǎn)lLL旋轉(zhuǎn)：新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)的左子樹的左子樹中；l RR旋轉(zhuǎn)：新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)的右子樹的右子樹中；l LR旋轉(zhuǎn)：新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)的左子樹的右子樹中；

22、l RL旋轉(zhuǎn)：新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)的右子樹的左子樹中。LL（1）LL旋轉(zhuǎn)：順時針在左子樹D上插入新節(jié)點(diǎn)使其高度增1，導(dǎo)致節(jié)點(diǎn)A的平衡因子增到 2，造成了不平衡。 為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個節(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做LL旋轉(zhuǎn)。 以節(jié)點(diǎn)B為旋轉(zhuǎn)軸，將節(jié)點(diǎn)A順時針旋轉(zhuǎn)成為B的右孩子，B代替原來A的位置，原來B的右孩子E轉(zhuǎn)為A的左孩子。(a)(b)(c)LL旋轉(zhuǎn)的算法template void AVLTree:RotateRight ( AVLNode *Tree, AVLNode * &NewTree) NewTree = Treeleft; Treel

23、eft = NewTreeright; NewTreeright = Tree; 注：Tree為子樹的根節(jié)點(diǎn) NewTree為子樹的新的根節(jié)點(diǎn)（2）RR旋轉(zhuǎn)：逆時針(a)(b)(c)在右子樹E中插入一個新節(jié)點(diǎn)，該子樹高度增1導(dǎo)致節(jié)點(diǎn)A的平衡因子變成-2，出現(xiàn)不平衡。 沿插入路徑檢查三個節(jié)點(diǎn)A、C和E。它們處于一條方向?yàn)椤啊钡闹本€上，需要做RR旋轉(zhuǎn)。 以節(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓節(jié)點(diǎn)A反時針旋轉(zhuǎn)成為C的左孩子，C代替原來A的位置，原來C的左孩子D轉(zhuǎn)為A的右孩子。RR旋轉(zhuǎn)的算法template void AVLTree :RotateLeft ( AVLNode *Tree, AVLNode * &New

24、Tree ) NewTree = Treeright; Treeright = NewTreeleft; NewTreeleft = Tree; （3）LR旋轉(zhuǎn)：先左后右雙旋轉(zhuǎn)先逆時針先逆時針后順時針后順時針在子樹F或G中插入新節(jié)點(diǎn)，該子樹的高度增1。節(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡。 從節(jié)點(diǎn)A起沿插入路徑選取3個節(jié)點(diǎn)A、B和E，它們位于一條形如“”的折線上，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)。 首先以節(jié)點(diǎn)E為旋轉(zhuǎn)軸，將節(jié)點(diǎn)B逆時針旋轉(zhuǎn)，以E代替原來B的位置，做RR旋轉(zhuǎn)。 再以節(jié)點(diǎn)E為旋轉(zhuǎn)軸，將節(jié)點(diǎn)A順時針旋轉(zhuǎn)，做LL旋轉(zhuǎn)，使之平衡化。LR旋轉(zhuǎn)演示LR旋轉(zhuǎn)算法template void AVL

25、Tree:LeftBalance ( AVLNode * &Tree, int & taller ) /左平衡化的算法 AVLNode *leftsub = Treeleft, *rightsub; switch ( leftsubbalance ) case -1 : /LL旋轉(zhuǎn)，此處是hR-hL=-1 Treebalance = leftsubbalance = 0; RotateRight ( Tree, Tree ); taller = 0; break; case 0 : cout “樹已經(jīng)平衡化.n; break; LR旋轉(zhuǎn)算法case 1 : rightsub = leftsub

26、right; switch ( rightsubbalance ) case -1: Treebalance = 1; leftsubbalance = 0; break; case 0 : Treebalance = leftsubbalance = 0; break; case 1 : Treebalance = 0; leftsubbalance = -1; break; rightsubbalance = 0; RotateLeft ( leftsub, Treeleft ); 先RR旋轉(zhuǎn) RotateRight ( Tree, Tree ); 后LL旋轉(zhuǎn) taller = 0; （4

27、）RL旋轉(zhuǎn)：先右后左雙旋轉(zhuǎn)先順時針先順時針后逆時針后逆時針右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。 在子樹F或G中插入新節(jié)點(diǎn)，該子樹高度增1。節(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡。 從節(jié)點(diǎn)A起沿插入路徑選取3個節(jié)點(diǎn)A、C和D，它們位于一條形如“”的折線上，需要進(jìn)行先右后左的雙旋轉(zhuǎn)。 首先做LL旋轉(zhuǎn)：以節(jié)點(diǎn)D為旋轉(zhuǎn)軸，將節(jié)點(diǎn)C順時針旋轉(zhuǎn)，以D代替原來C的位置。 再做RR旋轉(zhuǎn)：以節(jié)點(diǎn)D為旋轉(zhuǎn)軸，將節(jié)點(diǎn)A反時針旋轉(zhuǎn)，恢復(fù)樹的平衡。LR旋轉(zhuǎn)的算法template void AVLTree:RightBalance ( AVLNode * &Tree, int & taller ) /右平衡化的算法 AVLNo

28、de *rightsub = Treeright, *leftsub; switch ( rightsubbalance ) case 1 : /RR旋轉(zhuǎn)，此處是hR-hL=1 Treebalance = rightsubbalance = 0; RotateLeft ( Tree, Tree ); taller = 0; break; case 0 : cout “樹已經(jīng)平衡化.n; break; case -1 : leftsub = rightsubleft; switch ( leftsubbalance ) case 1 : Treebalance = -1; rightsubbalance = 0; break; case 0 : Treebalance = rightsubbalance = 0; break; case -1 : Treebalance = 0; rightsubbalance = 1; break; leftsubbalance = 0; RotateRight ( rightsub, Treeleft ); LL旋轉(zhuǎn) RotateLeft ( Tree, Tree ); taller = 0; RR旋轉(zhuǎn)