《數(shù)據(jù)結(jié)構(gòu)：思想與方法》第8章動(dòng)態(tài)查找表

1第8章動(dòng)態(tài)查找表二叉查找樹AVL樹紅黑樹AA樹伸展樹B樹和B+樹STL中的動(dòng)態(tài)查找表2二叉查找樹二叉查找樹的定義二叉查找樹的操作二叉查找樹的性能二叉查找樹類的實(shí)現(xiàn)3二叉排序樹如果p的左子樹若非空，則左子樹上的所有結(jié)點(diǎn)的關(guān)鍵字值均小于p結(jié)點(diǎn)的關(guān)鍵字值。如果p的右子樹若非空，則右子樹上的所有結(jié)點(diǎn)的關(guān)鍵字值均大于p結(jié)點(diǎn)的關(guān)鍵字值。結(jié)點(diǎn)p的左右子樹同樣是二叉排序樹。二叉排序樹是二叉樹在查找方面的重要應(yīng)用。二叉排序樹或者為空，或者具有如下性質(zhì)：對(duì)任意一個(gè)結(jié)點(diǎn)p而言4e、g：二叉排序樹LNPEMCY122250300110200991052302165二叉查找樹二叉查找樹的定義二叉查找樹的操作二叉查找樹的性能二叉查找樹類的實(shí)現(xiàn)6二叉排序樹的操作特定節(jié)點(diǎn)在樹上是否存在插入一個(gè)節(jié)點(diǎn)刪除一個(gè)節(jié)點(diǎn)由于樹是遞歸定義的，因此這些操作往往也用遞歸實(shí)現(xiàn)。因?yàn)槎鏄涞钠骄叨葹閘ogN，這些操作的時(shí)間復(fù)雜度也是O(logN)7查找過程若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，查其左子樹。若大于根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹。在左右子樹上的操作類似。812225030011020099105230216如：查找122，查找110，查找230，查找2259查找過程的遞歸描述如果樹為空，返回false如果根節(jié)點(diǎn)等于被查結(jié)點(diǎn)，返回true如果被查節(jié)點(diǎn)小于根節(jié)點(diǎn)，遞歸查找左子樹，否則遞歸查找右子樹10插入操作若二叉樹為空。則新插入的結(jié)點(diǎn)成為根結(jié)點(diǎn)。如二叉樹非空首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)11將數(shù)的序列：122、99、250、110、300、280作為二叉查找樹的結(jié)點(diǎn)的關(guān)鍵字值，生成二叉查找樹。122250300110280991221229912225099122250110991222503001109912插入操作的遞歸實(shí)現(xiàn)如果當(dāng)前樹為空，插入值作為樹的根節(jié)點(diǎn)，返回如果插入值小于根節(jié)點(diǎn)，插入到左子樹，否則插入到右子樹。13

執(zhí)行實(shí)例：插入值為280的結(jié)點(diǎn)12225030011099Tf：null12225030011099fTKey=28012225030011099fTKey=280f12225030011099T:nullKey=280p1222503001109928014刪除操作刪除葉結(jié)點(diǎn)刪除有一個(gè)兒子的結(jié)點(diǎn)刪除有兩個(gè)兒子的結(jié)點(diǎn)15刪除葉結(jié)點(diǎn)

直接刪除，更改它的父親結(jié)點(diǎn)的相應(yīng)指針場(chǎng)為空。這不會(huì)改變二叉排序樹的特性。如：刪除數(shù)據(jù)場(chǎng)為15、70的結(jié)點(diǎn)。1560703020506030205016刪除操作刪除葉結(jié)點(diǎn)刪除有一個(gè)兒子的結(jié)點(diǎn)刪除有兩個(gè)兒子的結(jié)點(diǎn)17只有一個(gè)兒子12225030011020099105230216400450500被刪結(jié)點(diǎn)122250300200230216400450500110105刪除991812225030011020099105330316400450500被刪結(jié)點(diǎn)122250330230216400450500刪除3001109910531619若被刪結(jié)點(diǎn)只有一個(gè)唯一的兒子，將此兒子取代被刪結(jié)點(diǎn)的位置。即，如被刪結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子，那么將他的兒子作為父結(jié)點(diǎn)的左孩子；如被刪結(jié)點(diǎn)是其父結(jié)點(diǎn)的有孩子，那么將他的孩子作為父結(jié)點(diǎn)的右孩子。20刪除操作刪除葉結(jié)點(diǎn)刪除有一個(gè)兒子的結(jié)點(diǎn)刪除有兩個(gè)兒子的結(jié)點(diǎn)21被刪結(jié)點(diǎn)有兩個(gè)兒子通常的做法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰哪？替身的要求：維持二叉分類樹的特性不變。因此，只有在中序周游中緊靠著被刪結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”，即，左子樹中最大的結(jié)點(diǎn)或右子樹中最小的結(jié)點(diǎn)。刪除這個(gè)結(jié)點(diǎn)會(huì)使其他結(jié)點(diǎn)從樹上脫離。22

12225030011020099105330316400450500被刪結(jié)點(diǎn)替身替身11025030010520099330316400450500做法：將替身110的數(shù)據(jù)字段復(fù)制到被刪結(jié)點(diǎn)的數(shù)據(jù)字段。將結(jié)點(diǎn)110的左兒子作為99的右兒子。用左子樹中的最大值做替身23

12225030011020099105330316400450500被刪結(jié)點(diǎn)替身替身做法：將替身的數(shù)據(jù)字段復(fù)制到被刪結(jié)點(diǎn)的數(shù)據(jù)字段。將結(jié)點(diǎn)200的右兒子作為200的父結(jié)點(diǎn)的左兒子。20025030011099105400450500330316用右子樹的最小值做替身24

12225030011020099105230216400450500被刪結(jié)點(diǎn)替身替身結(jié)論：先將替身的數(shù)據(jù)字段復(fù)制到被刪結(jié)點(diǎn)將原替身的另一兒子作為它的父親結(jié)點(diǎn)的兒子，究竟是作為左兒子還是右兒子依原替身結(jié)點(diǎn)和其父親結(jié)點(diǎn)的關(guān)系而定釋放原替身結(jié)點(diǎn)的空間。25刪除總結(jié)FP被刪結(jié)點(diǎn)PRPLFPRPL、PR皆空，直接刪除。PL或PR為空PL為空，刪除后的情況。26FP被刪結(jié)點(diǎn)CCLPRQQLSSLFSCCLPRQQLSL用左子樹的最大值代替27刪除的遞歸實(shí)現(xiàn)如果是空樹，返回如果被刪節(jié)點(diǎn)小于根節(jié)點(diǎn)，遞歸在左子樹上刪除如果被刪節(jié)點(diǎn)大于根節(jié)點(diǎn)，遞歸在右子樹刪除如果被刪節(jié)點(diǎn)等于根節(jié)點(diǎn)如果根節(jié)點(diǎn)有兩個(gè)兒子，將右子樹的最小值放入根節(jié)點(diǎn)，在右子樹上刪除最小節(jié)點(diǎn)如果有左子樹，左子樹取代根節(jié)點(diǎn)，刪除原來的根節(jié)點(diǎn)如果有右子樹，右子樹取代根節(jié)點(diǎn)，刪除原來的根節(jié)點(diǎn)28二叉查找樹二叉查找樹的定義二叉查找樹的操作二叉查找樹的性能二叉查找樹類的實(shí)現(xiàn)29二叉查找樹性能二叉查找樹的操作（包括insert、find和delete等）的代價(jià)正比于操作過程中要訪問的結(jié)點(diǎn)數(shù)。如果所操作的二叉查找樹是完全平衡的，那么訪問的代價(jià)將是對(duì)數(shù)級(jí)別的在最壞的請(qǐng)況下，二叉查找樹會(huì)退化為一個(gè)單鏈表。時(shí)間復(fù)雜度是O(N)。30平均性能n個(gè)結(jié)點(diǎn)二叉查找樹的可能有n種形態(tài)，如果這些形態(tài)出現(xiàn)的概率是相等的。設(shè)P（n）為查找n個(gè)結(jié)點(diǎn)的二叉查找樹的平均查找時(shí)間，則31二叉查找樹二叉查找樹的定義二叉查找樹的操作二叉查找樹的性能二叉查找樹類的實(shí)現(xiàn)32二叉排序樹類的設(shè)計(jì)采用標(biāo)準(zhǔn)的二叉鏈表存儲(chǔ)一棵二叉查找樹需要一個(gè)指向根節(jié)點(diǎn)的數(shù)據(jù)成員公有的成員函數(shù)：find、insert和remove以及構(gòu)造、析構(gòu)函數(shù)二叉查找樹的插入、刪除和查找都是通過遞歸實(shí)現(xiàn)的，而這三個(gè)公有函數(shù)的參數(shù)表中并不需要包含遞歸參數(shù)。為此，對(duì)于每個(gè)公有的成員函數(shù)都定義了一個(gè)對(duì)應(yīng)的帶有遞歸參數(shù)的私有的成員函數(shù)33二叉排序樹類的定義template<classType>classBinarySearchTree{private:structBinaryNode{Typedata;BinaryNode*left;BinaryNode*right;BinaryNode(constType&thedata,BinaryNode*lt,BinaryNode*rt):data(thedata),left(lt),right(rt){}};BinaryNode*root;34public:BinarySearchTree(BinaryNode*t=NULL){root=t;}~BinarySearchTree();boolfind(constType&x)const;voidinsert(constType&x);voidremove(constType&x);private:voidinsert(constType&x,BinaryNode*&t)const;voidremove(constType&x,BinaryNode*&t)const;boolfind(constType&x,BinaryNode*t)const;voidmakeEmpty(BinaryNode*&t);};

35二叉排序樹類的設(shè)計(jì)特點(diǎn)一個(gè)內(nèi)嵌的BinaryNode類數(shù)據(jù)成員只有一個(gè)，樹根公有的成員函數(shù)通過調(diào)用私有的遞歸函數(shù)完成相應(yīng)的功能36find函數(shù)的實(shí)現(xiàn)template<classType>boolBinarySearchTree<Type>::find(constType&x)const{returnfind(x,root);}template<classType>boolBinarySearchTree<Type>::find(constType&x,BinaryNode*t)const{if(t==NULL)returnfalse;elseif(x<t->data)returnfind(x,t->left);elseif(t->data<x)returnfind(x,t->right);elsereturntrue;}37insert函數(shù)的實(shí)現(xiàn)template<classType>voidBinarySearchTree<Type>::insert(constType&x){insert(x,root);}template<classType>voidBinarySearchTree<Type>::insert(constType&x,BinaryNode*&t){if(t==NULL)t=newBinaryNode(x,NULL,NULL);elseif(x<t->data)insert(x,t->left);elseif(t->data<x)insert(x,t->right);}38insert函數(shù)私有的insert函數(shù)的第二個(gè)形式參數(shù)，它是一個(gè)指向結(jié)點(diǎn)的指針的引用。這個(gè)引用符號(hào)不能省略。正是這個(gè)引用，使得新插入的結(jié)點(diǎn)和它的父結(jié)點(diǎn)之間關(guān)聯(lián)了起來。39remove函數(shù)的實(shí)現(xiàn)template<classType>voidBinarySearchTree<Type>::remove(constType&x){remove(x,root);}40template<classType>voidBinarySearchTree<Type>::remove(constType&x,BinaryNode*&t){if(t==NULL)return;if(x<t->data)remove(x,t->left);elseif(t->data<x)remove(x,t->right);elseif(t->left!=NULL&&t->right!=NULL){ BinaryNode*tmp=t->right;while(tmp->left!=NULL)tmp=tmp->left;t->data=tmp->data;remove(t->data,t->right);}else{BinaryNode*oldNode=t;t=(t->left!=NULL)?t->left:t->right;

deleteoldNode;}}41remove函數(shù)同樣請(qǐng)注意私有的remove函數(shù)的參數(shù)，它的第二個(gè)參數(shù)也是指向結(jié)點(diǎn)的指針的引用。與插入過程一樣，這個(gè)引用也不能去掉。正是這個(gè)引用使得被刪結(jié)點(diǎn)的父結(jié)點(diǎn)和被刪結(jié)點(diǎn)的兒子連接起來。42二叉查找樹類的使用intmain(){inta[]={10,8,6,21,87,56,4,0,11,3,22,7,5,34,1,2,9};BinarySearchTree<int>tree;for(inti=0;i<17;++i)tree.insert(a[i]);cout<<endl<<"find2is"<<(tree.find(2)?"true":"false")<<endl;tree.remove(2);cout<<"afterdelete2,find2is"<<(tree.find(2)?"true":"false")<<endl;cout<<"find3is"<<(tree.find(3)?"true":"false")<<endl;tree.remove(3);cout<<"afterdelete3,find3is"<<(tree.find(3)?"true":"false")<<endl;cout<<"find21is"<<(tree.find(21)?"true":"false")<<endl;tree.remove(21);cout<<"afterdelete21,find21is"<<(tree.find(21)?"true":"false")<<endl;return0;}43第8章動(dòng)態(tài)查找表二叉查找樹AVL樹紅黑樹AA樹伸展樹B樹和B+樹STL中的動(dòng)態(tài)查找表44AVL樹AVL樹的定義AVL樹的插入操作AVL樹的刪除AVL樹類的實(shí)現(xiàn)45平衡二叉分類樹當(dāng)樹退化為鏈表時(shí)，樹的優(yōu)點(diǎn)蕩然無存。要使查找樹的性能盡可能好，就要使得樹盡可能豐滿。要構(gòu)造一個(gè)豐滿樹很困難，一種替代的方案是平衡樹。DGEDABCFEGBACF46二叉平衡樹二叉平衡樹就是滿足某種平衡條件的二叉查找樹平衡條件：容易維護(hù)保證樹的高度是O(logN)47平衡條件最簡(jiǎn)單的想法是讓左右子樹有同樣的高度。但它并不能保證樹是矮胖的。另一個(gè)想法是要求每個(gè)節(jié)點(diǎn)的左右子樹都有同樣的高度。這個(gè)條件能保證樹是矮胖的，但這個(gè)條件太苛刻，只有滿二叉樹才滿足這個(gè)條件。將上述條件稍微放寬一些就是二叉平衡排序樹。48平衡樹的定義平衡因子（平衡度）：結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹的高度－右子樹的高度?？諛涞母叨榷x為-1。平衡二叉樹：每個(gè)結(jié)點(diǎn)的平衡因子都為＋1、－1、0的二叉樹?；蛘哒f每個(gè)結(jié)點(diǎn)的左右子樹的高度最多差1的二叉樹?？梢宰C明平衡樹的高度至多約為：1.44log(N+2)-1.32849是平衡樹不是豐滿樹不是平衡樹141253928635360501718730+1+1-1-1-100000000145392863536050171830+1+2-1-100000+1-150平衡二叉樹的查找性能定理：具有N個(gè)結(jié)點(diǎn)的平衡樹，高度h滿足：log2(N+1)<=h<=1.44log2(N+1)-0.328;與二叉樹的高度成正比因此，平衡二叉樹的操作都是O(logN)51AVL樹AVL樹的定義AVL樹的插入操作AVL樹的刪除AVL樹類的實(shí)現(xiàn)52插入操作插入過程與二叉查找樹的插入相同，只是插入后可能出現(xiàn)兩種情況：插入后，不破壞平衡性，只是改變了樹根到插入點(diǎn)的路徑上的某些結(jié)點(diǎn)的平衡度，因此需要自底向上修改節(jié)點(diǎn)的平衡度破壞了路徑上的某些結(jié)點(diǎn)的平衡性，需要向上調(diào)整53141253928635360501718730+1+1-1-1-10000000029141253928635360501718730+1+1-1-1-10+1000000只改變了某些結(jié)點(diǎn)的平衡度，需要自底向上的調(diào)整。只要有一個(gè)節(jié)點(diǎn)的平衡度不變，它上面的節(jié)點(diǎn)的平衡度也不變。調(diào)整可以結(jié)束。54141253928635360501718730+1+1-1-1-100000000平衡樹141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)插入2以后，變得不平衡了。如何用最簡(jiǎn)單、最有效的辦法保持平衡分類二叉樹的性質(zhì)不變？55解決方案：希望不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹的高度應(yīng)保持不變（左圖為3）。調(diào)整可以到此結(jié)束。仍應(yīng)保持分類二叉樹的性質(zhì)不變新結(jié)點(diǎn)插入后，找到第一個(gè)平衡度不為0的結(jié)點(diǎn)，該節(jié)點(diǎn)可能平衡失調(diào)。如果需要的話調(diào)整該子樹。新插入的結(jié)點(diǎn)和第一個(gè)平衡度不為0的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為0141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)56可能引起節(jié)點(diǎn)不平衡的情況在節(jié)點(diǎn)的左孩子的左子樹上插入（LL）在節(jié)點(diǎn)左孩子的右子樹上插入（LR）在節(jié)點(diǎn)的右孩子的左子樹上插入（RL）在節(jié)點(diǎn)的右孩子的右子樹上插入（RR）57可能引起不平衡的情況LLRR：LL的鏡像對(duì)稱LRRL：LR的鏡像對(duì)稱AB+1h-10+2+1hh-1h-1BLBRAR危機(jī)結(jié)點(diǎn)AB+1h-10+2-1h-1BLARBRh危機(jī)結(jié)點(diǎn)58LL和RR問題通過單旋轉(zhuǎn)來解決。即危機(jī)結(jié)點(diǎn)和引起危機(jī)的兒子的角色轉(zhuǎn)換。如果是LL問題，將危機(jī)結(jié)點(diǎn)的左兒子作為根，原來的根結(jié)點(diǎn)作為他的右子樹，原先的右兒子作為原先根的左兒子。如果是RR問題，將危機(jī)結(jié)點(diǎn)的右兒子作為根，原來的根結(jié)點(diǎn)作為他的左子樹，原先的左兒子作為原先根的右兒子59LL問題保持了樹的有序性保持了原先的高度AB+1h-10+2+1hh-1h-1BLBRAR危機(jī)結(jié)點(diǎn)ABh-1hh-1h-1BLBRAR60在下列樹中插入4，將會(huì)使得9失去平衡。這是在9的左孩子的左子樹上插入引起失衡，是LL情況141253928635360501718730+1+1-1-1-100000000141253928635360501718730+1+1-1-1-100000000461旋轉(zhuǎn)后的結(jié)果141253928635360501718730+1-1-1-100004保持了樹的有序性保持了原先的高度62LR和RL問題通過雙旋轉(zhuǎn)來解決，即兩次單旋轉(zhuǎn)?，F(xiàn)對(duì)危機(jī)結(jié)點(diǎn)的兒子和孫子進(jìn)行一次單旋轉(zhuǎn)，使孫子變成兒子。然后是危機(jī)結(jié)點(diǎn)和新的兒子進(jìn)行一次單旋轉(zhuǎn)。63LR問題AB+1h-10+2-1h-1BLARBRh危機(jī)結(jié)點(diǎn)有一個(gè)結(jié)點(diǎn)被插入到B的右子樹的事實(shí)保證了B的右子樹不會(huì)是空的，因此我們可以假定B的右子樹為C，它有一個(gè)根和兩棵子樹（當(dāng)然可能是空的）組成AB+1h-10+2-1h-1BLARCL危機(jī)結(jié)點(diǎn)CCR64保持了樹的有序性保持了原先的高度ABh-1h-1BLARCLCCRLR旋轉(zhuǎn)可以看成有兩個(gè)單選轉(zhuǎn)組成：先對(duì)B執(zhí)行RR旋轉(zhuǎn)，再對(duì)A執(zhí)行LL旋轉(zhuǎn)6514923528601814插入4后調(diào)整后1492352860181466AVL插入總結(jié)用遞歸實(shí)現(xiàn)要在AVL樹T中插入一個(gè)鍵值為X的結(jié)點(diǎn)，我們遞歸地將它插入到T的某棵合適的子樹（記做TLR）中，如果插入后TLR的高度沒有改變，就完成了操作。否則，我們就根據(jù)X和T及TLR中的鍵值選擇單旋轉(zhuǎn)或是雙旋轉(zhuǎn)（以T為根），然后操作也結(jié)束了（因?yàn)樵瓉淼母叨群托D(zhuǎn)后的高度是一樣的）

67AVL樹AVL樹的定義AVL樹的插入操作AVL樹的刪除AVL樹類的實(shí)現(xiàn)68平衡二叉樹的刪除首先在AVL樹上刪除結(jié)點(diǎn)x然后調(diào)整平衡69調(diào)整平衡和插入操作一樣，失衡節(jié)點(diǎn)存在于被刪節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上在刪除了一個(gè)結(jié)點(diǎn)后，必須沿著到根結(jié)點(diǎn)的路徑向上回溯，隨時(shí)調(diào)整路徑上的結(jié)點(diǎn)的平衡度。刪除操作沒有插入操作那么幸運(yùn)。插入時(shí)，最多只需要調(diào)整一個(gè)結(jié)點(diǎn)。而刪除時(shí)，我們無法保證子樹在平衡調(diào)整后的高度不變。只有當(dāng)某個(gè)結(jié)點(diǎn)的高度在刪除前后保持不變，才無需繼續(xù)調(diào)整。遞歸的刪除函數(shù)有一個(gè)布爾型的返回值。當(dāng)返回值為true時(shí)，調(diào)整停止。當(dāng)返回值為false時(shí)，繼續(xù)調(diào)整。70刪除可能出現(xiàn)的情況令q是最終被刪除的結(jié)點(diǎn)，p是q到根結(jié)點(diǎn)的路徑上的某個(gè)結(jié)點(diǎn)。q的刪除對(duì)p的影響有以下幾種情況：結(jié)點(diǎn)P的平衡因子原為0從p的較高的子樹上刪去一個(gè)結(jié)點(diǎn)從p較矮的子樹上刪除一個(gè)結(jié)點(diǎn)71結(jié)點(diǎn)P的平衡因子原為0從p的某棵子樹上刪除結(jié)點(diǎn)后，該子樹變矮，但以p為根的子樹高度不會(huì)改變。只需要修改p的平衡因子即可。p的高度不變，意味著它上面的結(jié)點(diǎn)的平衡因子都不變，調(diào)整可以結(jié)束。返回true。72從p的較高的子樹上刪去一個(gè)結(jié)點(diǎn)從p的較高的子樹上刪除結(jié)點(diǎn)后，如果該子樹變矮，以p為根的子樹也變矮。但以結(jié)點(diǎn)P為根的這棵子樹仍然是AVL樹，而且更平衡了。調(diào)整：將p的平衡因子置為0由于以p為根的子樹變矮，可能會(huì)影響p的父結(jié)點(diǎn)的平衡度，返回false7314951072860182刪除2：原來結(jié)點(diǎn)5是左高右低，屬于情況2。刪除2以后，結(jié)點(diǎn)5的平衡因子變?yōu)?，以結(jié)點(diǎn)5為根結(jié)點(diǎn)的子樹也矮了一層，這樣就會(huì)影響結(jié)點(diǎn)7的平衡度，所以繼續(xù)往上調(diào)整。對(duì)結(jié)點(diǎn)7而言，正好屬于情況一。所以修改7的平衡因子，調(diào)整結(jié)束。149510728601874從p較矮的子樹上刪除一個(gè)結(jié)點(diǎn)在p的較矮的子樹上刪除一個(gè)結(jié)點(diǎn)，使較矮的子樹變得更矮，p的平衡度肯定遭到坡壞，此時(shí)要通過旋轉(zhuǎn)來恢復(fù)這棵子樹的平衡。設(shè)q是p的較高的子樹的根。根據(jù)q的平衡因子的值，可以進(jìn)一步細(xì)化為以下三種不同的情況：q的平衡因子為0q的平衡因子和p的平衡因子符號(hào)相同q的平衡因子和p的平衡因子符號(hào)相反75q的平衡因子為0P-1h-1Qh-10h-1P+1h-2Qh-1h-1-1QRQRQLQLPLPL整棵樹高度不變，不需要繼續(xù)調(diào)整76q和p的平衡因子符號(hào)相同P-1h-1Qh-2-1h-1P0h-2Qh-2h-10QRQRQLQLPLPL整棵樹矮了一層，需要繼續(xù)調(diào)整77q和p的平衡因子符號(hào)相反P-1h-1Q+1h-2Rh-2或h-3R0QPh-2h-2RLQRQRRLRRRRPLPLh-2或h-3h-2或h-3h-2或h-3整棵樹矮了一層，需要繼續(xù)調(diào)整78AVL樹AVL樹的定義AVL樹的插入操作AVL樹的刪除AVL樹類的實(shí)現(xiàn)79AVL樹類的實(shí)現(xiàn)template<classType>classAvlTree{structAvlNode {Typedata;AvlNode*left;AvlNode*right;intheight;

AvlNode(constType&element,AvlNode*lt,AvlNode*rt,inth=0)

:data(element),left(lt),right(rt),height(h){}}; AvlNode*root;80 public: AvlTree(AvlNode*t=NULL){root=t;}

~AvlTree(){makeEmpty(root);}boolfind(constType&x)const;voidinsert(constType&x){insert(x,root);}voidremove(constType&x){remove(x,root);} private:voidinsert(constType&x,AvlNode*&t);

boolremove(constType&x,AvlNode*&t);voidmakeEmpty(AvlNode*&t); intheight(AvlNode*t)const{returnt==NULL?-1:t->height;} voidLL(AvlNode*&t); voidLR(AvlNode*&t); voidRL(AvlNode*&t); voidRR(AvlNode*&t); intmax(inta,intb){return(a>b)?a:b;}};81find函數(shù)的非遞歸實(shí)現(xiàn)template<classType>boolAvlTree<Type>::find(constType&x)const{AvlNode*t=root;while(t!=NULL&&t->data!=x) if(t->data>x)t=t->left;elset=t->right;if(t==NULL)returnfalse;elsereturntrue;}82私有的insert函數(shù)的實(shí)現(xiàn)template<classType>voidAvlTree<Type>::insert(constType&x,AvlNode*&t){if(t==NULL)t=newAvlNode(x,NULL,NULL);elseif(x<t->data){insert(x,t->left);

if(height(t->left)-height(t->right)==2)if(x<t->left->data)LL(t);elseLR(t); }elseif(t->data<x){insert(x,t->right);

if(height(t->right)-height(t->left)==2)if(t->right->data<x)RR(t);elseRL(t); }

t->height=max(height(t->left),height(t->right))+1;}83LLtemplate<classType>voidAvlTree<Type>::LL(AvlNode*&t){AvlNode*t1=t->left;t->left=t1->right;t1->right=t;t->height=max(height(t->left),height(t->right))+1;t1->height=max(height(t1->left),height(t))+1;t=t1;}AB+1h-10+2+1hh-1h-1BLBRAR危機(jī)結(jié)點(diǎn)84RRtemplate<classType>voidAvlTree<Type>::RR(AvlNode*&t){AvlNode*t1=t->right;t->right=t1->left;t1->left=t;t->height=max(height(t->left),height(t->right))+1;t1->height=max(height(t1->right),height(t))+1;t=t1;}85LR和RLtemplate<classType>voidAvlTree<Type>::LR(AvlNode*&t){RR(t->left);LL(t);}template<classType>voidAvlTree<Type>::RL(AvlNode*&t){LL(t->right);RR(t);}86私有的remove函數(shù)的實(shí)現(xiàn)template<classType>boolAvlTree<Type>::remove(constType&x,AvlNode*&t){boolstop=false;intsubTree;//1表示刪除發(fā)生在左子樹上，

//2表示刪除發(fā)生在右子樹上

if(t==NULL)returntrue;87if(x<t->data){stop=remove(x,t->left);subTree=1;}elseif(t->data<x){stop=remove(x,t->right);subTree=2;}elseif(t->left!=NULL&&t->right!=NULL){ AvlNode*tmp=t->right; while(tmp->left!=NULL)tmp=tmp->left;t->data=tmp->data;stop=remove(t->data,t->right); subTree=2;}else{AvlNode*oldNode=t;t=(t->left!=NULL)?t->left:t->right;

deleteoldNode; returnfalse; }if(stop)returntrue;intbf;88switch(subTree){ case1:bf=height(t->left)-height(t->right)+1; if(bf==0)returntrue;//情況一

if(bf==1)returnfalse;//情況二

if(bf==-1){//情況三

intbfr=height(t->right->left)-height(t->right->right); switch(bfr){ case0:RR(t);returntrue; case-1:RR(t);returnfalse; default:RL(t);returnfalse; } } break; case2:bf=height(t->left)-height(t->right)-1; if(bf==0)returntrue;//情況一

if(bf==-1)returnfalse;//情況二

if(bf==1){//情況三

intbfl=height(t->right->left)-height(t->right->right); switch(bfl){ case0:LL(t);returntrue; case1:LL(t);returnfalse; default:LR(t);returnfalse;}}}}89第8章動(dòng)態(tài)查找表二叉查找樹AVL樹紅黑樹AA樹伸展樹B樹和B+樹STL中的動(dòng)態(tài)查找表90紅黑樹紅黑樹的定義紅黑樹的插入紅黑樹的刪除紅黑樹類的實(shí)現(xiàn)紅黑樹是平衡樹的一種替換方案。它比平衡樹簡(jiǎn)單。紅黑樹在最壞情況下的操作時(shí)間是O(logN)91紅黑樹的定義每個(gè)節(jié)點(diǎn)都被標(biāo)記為紅色或是黑色的根是黑色的如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的兒子都是黑色的每一條從某個(gè)節(jié)點(diǎn)到一個(gè)空鏈域的路徑必須具有相同數(shù)量的黑色節(jié)點(diǎn)141253928261560502025302392紅黑樹紅黑樹的定義紅黑樹的插入紅黑樹的刪除紅黑樹類的實(shí)現(xiàn)紅黑樹是平衡樹的一種替換方案。它比平衡樹簡(jiǎn)單。紅黑樹在最壞情況下的操作時(shí)間是O(logN)93紅黑樹的插入插入過程同普通的二叉排序樹，只是插入后被插入的節(jié)點(diǎn)要被著色著成黑色是不可能的，會(huì)違反定義4，必須著成紅色如果父節(jié)點(diǎn)是黑色的，插入結(jié)束。如果父節(jié)點(diǎn)是紅色的，則違反定義3。必須調(diào)整節(jié)點(diǎn)的顏色把新插入的節(jié)點(diǎn)稱作X，P是它的父親節(jié)點(diǎn)，S是它父親的兄弟節(jié)點(diǎn)（空節(jié)點(diǎn)認(rèn)為是黑色的），G是X祖父。94顏色調(diào)整總結(jié)父結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)S是黑色的X是G的外側(cè)結(jié)點(diǎn)：LLb，RRbX是G的內(nèi)側(cè)結(jié)點(diǎn)：LRb，RLb父結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)S是紅色的95LLb，RRbBDECAGSBXPDECAPGXSLLb旋轉(zhuǎn)DECAGPBXSRRb旋轉(zhuǎn)DECAPXBSG調(diào)整后，樹根為黑色。不需要繼續(xù)調(diào)整96LRb，RLbLRb旋轉(zhuǎn)BDECAGSBPDECAXGSXPBDECAGSBPDECAXGSRLb旋轉(zhuǎn)XP調(diào)整后，樹根為黑色。不需要繼續(xù)調(diào)整9714125392826156050202530231在樹中插入1，屬LLb的情況1412539282615605020253023198父結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)S是紅色的DECAGSBXPDECAGSBXP通過重新著色，消除連續(xù)紅節(jié)點(diǎn)99DECAGSBPXDECAGSBPX通過重新著色，連續(xù)的紅結(jié)點(diǎn)就不存在了，而且路徑上的黑結(jié)點(diǎn)數(shù)也沒有變化。經(jīng)過重新著色以后，根結(jié)點(diǎn)變成了紅色。如果原來X的曾祖父就是紅色的，那么又出現(xiàn)了連續(xù)紅結(jié)點(diǎn)問題。于是，需要繼續(xù)往上調(diào)整。最壞的情況下可能要調(diào)整到根。

100141235928261560502025302315524插入24141235928261560502025302315524重新著色調(diào)整20、25的連續(xù)紅節(jié)點(diǎn)，又是情況二。重新著色141235928261560502025302315524101紅黑樹紅黑樹的定義紅黑樹的插入紅黑樹的刪除紅黑樹類的實(shí)現(xiàn)紅黑樹是平衡樹的一種替換方案。它比平衡樹簡(jiǎn)單。紅黑樹在最壞情況下的操作時(shí)間是O(logN)102紅黑樹的刪除刪除操作首先使用普通的二叉查找樹的刪除算法刪除結(jié)點(diǎn)，然后進(jìn)行旋轉(zhuǎn)及顏色的調(diào)整。在二叉查找樹的刪除中，最終可以歸結(jié)到兩種情況：刪除葉結(jié)點(diǎn)和刪除只有一個(gè)兒子的結(jié)點(diǎn)。只要解決了這兩種情況下的著色問題，就解決了紅黑樹的刪除103紅黑樹刪除時(shí)的情況刪除的是紅色葉結(jié)點(diǎn)：直接刪除刪除只有一個(gè)兒子的結(jié)點(diǎn)：將兒子的顏色改為黑色刪除一個(gè)黑色的葉結(jié)點(diǎn)104刪除一個(gè)黑色的葉結(jié)點(diǎn)被調(diào)整的結(jié)點(diǎn)的兄弟是黑色的（如果兄弟是空結(jié)點(diǎn)，則認(rèn)為是黑色結(jié)點(diǎn)）被調(diào)整的結(jié)點(diǎn)的兄弟是紅色的刪除這個(gè)結(jié)點(diǎn)將會(huì)使得這個(gè)位置變成了一個(gè)空結(jié)點(diǎn)。因此，這條路徑上少了一個(gè)黑結(jié)點(diǎn)。我們將這個(gè)空結(jié)點(diǎn)稱為被調(diào)整結(jié)點(diǎn)。105被調(diào)整的結(jié)點(diǎn)的兄弟是黑色的L0和R0：兄弟結(jié)點(diǎn)有0個(gè)紅孩子L1L和R1R：兄弟有一個(gè)紅孩子，且為它的外側(cè)的孩子L1R和R1L：兄弟有一個(gè)紅孩子，且為它的內(nèi)側(cè)的孩子L2和R2：兄弟有兩個(gè)紅孩子106L0和R0pszpsz父節(jié)點(diǎn)原來可以為任意顏色。如果父結(jié)點(diǎn)原來是紅色的，現(xiàn)在變成了黑色，調(diào)整可以結(jié)束了。但如果父結(jié)點(diǎn)原來就是黑色的，現(xiàn)在經(jīng)過父結(jié)點(diǎn)的所有路徑都少了一個(gè)黑結(jié)點(diǎn)。于是繼續(xù)調(diào)整。107L1L和R1Rpsrslszpsrslsz新的根結(jié)點(diǎn)的顏色和老的根結(jié)點(diǎn)的顏色是相同的，因此也不會(huì)出現(xiàn)連續(xù)的紅結(jié)點(diǎn)的問題。調(diào)整可以結(jié)束了108L1R和R1Lpsrslszsrlsrrpsrslszsrlsrr由于新的根結(jié)點(diǎn)的顏色和老的根結(jié)點(diǎn)的顏色是相同的，因此也不會(huì)出現(xiàn)連續(xù)的紅結(jié)點(diǎn)的問題。調(diào)整可以結(jié)束了109L2和R2psrslszsrlsrrpsrslszsrlsrrL2的調(diào)整方法和L1R是一樣的，R2的調(diào)整方法和R1L是一樣的110刪除一個(gè)黑色的葉結(jié)點(diǎn)被調(diào)整的結(jié)點(diǎn)的兄弟是黑色的（如果兄弟是空結(jié)點(diǎn)，則認(rèn)為是黑色結(jié)點(diǎn)）被調(diào)整的結(jié)點(diǎn)的兄弟是紅色的刪除這個(gè)結(jié)點(diǎn)將會(huì)使得這個(gè)位置變成了一個(gè)空結(jié)點(diǎn)。因此，這條路徑上少了一個(gè)黑結(jié)點(diǎn)。我們將這個(gè)空結(jié)點(diǎn)稱為被調(diào)整結(jié)點(diǎn)。111兄弟結(jié)點(diǎn)是紅色的如果被調(diào)整結(jié)點(diǎn)的兄弟結(jié)點(diǎn)是紅色的，那么父結(jié)點(diǎn)一定是黑色的，兄弟結(jié)點(diǎn)的兒子也一定是黑色的。旋轉(zhuǎn)后，紅黑樹的特性得以保持，但被調(diào)整結(jié)點(diǎn)的兄弟結(jié)點(diǎn)變成了黑色。第2種情況轉(zhuǎn)換成了第1種情況，pszslsrpszslsr112141235928261560502025302315524在下列紅黑樹中刪除26，違反了紅黑樹的性質(zhì)，25的右路徑少了一個(gè)黑結(jié)點(diǎn)，是屬于第二種情況1412359281560502025302315524113旋轉(zhuǎn)后，結(jié)果如下，被調(diào)整節(jié)點(diǎn)（25的右孩子）的兄弟變成了黑色而且有一個(gè)紅孩子，屬于L1R的情況。調(diào)整后如右圖14123592815605020253023155241412359281560502025302315524調(diào)整后，這棵樹恢復(fù)了平衡114紅黑樹紅黑樹的定義紅黑樹的插入紅黑樹的刪除紅黑樹類的實(shí)現(xiàn)紅黑樹是平衡樹的一種替換方案。它比平衡樹簡(jiǎn)單。紅黑樹在最壞情況下的操作時(shí)間是O(logN)115紅黑樹類的實(shí)現(xiàn)紅黑樹的節(jié)點(diǎn)類需要一個(gè)保存顏色的數(shù)據(jù)成員插入、刪除時(shí)的調(diào)整需要用到父節(jié)點(diǎn)可祖父節(jié)點(diǎn)，所以用迭代的方式實(shí)現(xiàn)116紅黑樹類的定義template<classType>classRedBlackTree{structRedBlackNode {Typedata;RedBlackNode*left;RedBlackNode*right;intcolour;//0--Red,1--Black

RedBlackNode(constType&element,RedBlackNode*lt,RedBlackNode*rt,inth=0):data(element),left(lt),right(rt),colour(h){}};RedBlackNode*root; 117public: RedBlackTree(RedBlackNode*t=NULL){root=t;}~RedBlackTree(){makeEmpty(root);}boolfind(constType&x)const;voidinsert(constType&x);voidremove(constType&x);private:voidmakeEmpty(RedBlackNode*&t); voidLL(RedBlackNode*&t); voidLR(RedBlackNode*&t); voidRL(RedBlackNode*&t); voidRR(RedBlackNode*&t); voidreLink(RedBlackNode*oldp,RedBlackNode*newp,linkStack<RedBlackNode*>&path);voidinsertReBalance(RedBlackNode*t,linkStack<RedBlackNode*>&path);voidremoveReBalance(RedBlackNode*t,linkStack<RedBlackNode*>&path);};118reLink函數(shù)的實(shí)現(xiàn)當(dāng)子樹被旋轉(zhuǎn)后，子樹的根會(huì)發(fā)生變化。對(duì)子樹的父結(jié)點(diǎn)來講，必須將新的子樹根作為兒子。reLink就是完成這個(gè)功能ReLink函數(shù)有三個(gè)參數(shù)。第一個(gè)參數(shù)是子樹原來的根，第二個(gè)參數(shù)是子樹的新根，第三個(gè)參數(shù)是一個(gè)鏈接棧類對(duì)象，保存從根結(jié)點(diǎn)到這棵子樹的路徑上的結(jié)點(diǎn)。這里的linkStack就是第三章中實(shí)現(xiàn)的鏈接棧類

119template<classType>voidRedBlackTree<Type>::reLink(RedBlackNode*oldp,RedBlackNode*newp,linkStack<RedBlackNode*>&path){if(path.isEmpty())root=newp;else{ RedBlackNode*grandParent=path.pop(); if(grandParent->left==oldp)grandParent->left=newp; elsegrandParent->right=newp; path.push(grandParent);}}120Find、makeEmpty和旋轉(zhuǎn)函數(shù)與AVL樹完全相同121insert函數(shù)的實(shí)現(xiàn)用非遞歸實(shí)現(xiàn)插入函數(shù)只需要一個(gè)參數(shù)：被插入的節(jié)點(diǎn)需要維護(hù)一個(gè)棧，保存從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑可以用第三章中的棧類122template<classType>voidRedBlackTree<Type>::insert(constType&x){linkStack<RedBlackNode*>path;RedBlackNode*t,*parent;if(root==NULL){root=newRedBlackNode(x,NULL,NULL,1); return;}t=root;while(t!=NULL&&t->data!=x){ path.push(t); if(t->data<x)t=t->right;elset=t->left;}123if(t!=NULL)return;t=newRedBlackNode(x,NULL,NULL);parent=path.pop();if(x<parent->data)parent->left=t;elseparent->right=t;if(parent->colour==1)return;path.push(parent);insertReBalance(t,path);}124insertReBalance(t,path)template<classType>voidRedBlackTree<Type>::insertReBalance(RedBlackNode*t,linkStack<RedBlackNode*>&path){RedBlackNode*parent,*grandParent,*uncle,*rootOfSubTree;parent=path.pop();125while(parent->colour==0){if(parent==root){parent->colour=1;return;} grandParent=rootOfSubTree=path.pop(); if(grandParent->data>parent->data) uncle=grandParent->right;elseuncle=grandParent->left;

if(uncle==NULL||uncle->colour==1){//情況一的處理｝

else{//情況二

grandParent->colour=0; parent->colour=1; uncle->colour=1; if(root==grandParent){root->colour=1;return;} t=grandParent; parent=path.pop(); }}}126//情況一的處理If(grandParent->left==parent) if(t==parent->left){//LLbparent->colour=1;grandParent->colour=0;LL(grandParent);} else{//LRb grandParent->colour=0;t->colour=1;LR(grandParent);}elseif(t==parent->right){//RRbparent->colour=1;grandParent->colour=0;RR(grandParent); } else{//RLb grandParent->colour=0;t->colour=1;RL(grandParent);}reLink(rootOfSubTree,grandParent,path);return;}127Remove函數(shù)使用迭代的方式實(shí)現(xiàn)刪除操作。remove函數(shù)中也設(shè)置了一個(gè)棧path，保存從根結(jié)點(diǎn)到被刪結(jié)點(diǎn)的路徑。刪除函數(shù)首先執(zhí)行結(jié)點(diǎn)刪除，然后判斷紅黑樹是否失衡。如果失衡，則調(diào)用removeReBalance重新調(diào)整平衡。128remove函數(shù)的實(shí)現(xiàn)template<classType>voidRedBlackTree<Type>::remove(constType&x){linkStack<RedBlackNode*>path;RedBlackNode*t=root,*old,*parent=NULL;while(t!=NULL&&t->data!=x){ path.push(t); if(t->data>x)t=t->left;elset=t->right;}if(t==NULL)return;//找替代結(jié)點(diǎn)并替代

if(t->left!=NULL&&t->right!=NULL){ path.push(t);old=t;t=t->right; while(t->left!=NULL){path.push(t);t=t->left;} old->data=t->data;}129//執(zhí)行刪除

if(t==root){//刪除根結(jié)點(diǎn)

root=(t->left?t->left:t->right); if(root!=NULL)root->colour=1; return;}parent=path.pop();old=t;t=(t->left?t->left:t->right);

if(parent->left==old)parent->left=t;elseparent->right=t;if(old->colour==0){deleteold;return;}//刪除紅葉結(jié)點(diǎn)

deleteold;if(t!=NULL){//有一個(gè)紅兒子

t->colour=1;return;}path.push(parent);removeReBalance(t,path);}130removeReBalance函數(shù)的實(shí)現(xiàn)template<classType>voidRedBlackTree<Type>::removeReBalance(RedBlackNode*t,linkStack<RedBlackNode*>&path){RedBlackNode*parent,*sibling,*rootOfSubTree;

parent=rootOfSubTree=path.pop();131while(parent!=NULL){ if(parent->left==t)sibling=parent->right;elsesibling=parent->left; if(sibling->colour==0){//情況二

sibling->colour=1; parent->colour=0; if(parent->left==t)RR(parent);elseLL(parent);reLink(rootOfSubTree,parent,path); path.push(parent); parent=rootOfSubTree;} else{//兄弟是黑結(jié)點(diǎn)

if((sibling->left==NULL||sibling->left->colour==1)&&(sibling->right==NULL||sibling->right->colour==1)){//L0orR0 sibling->colour=0; if(parent->colour==0){parent->colour=1;return;} else{t=parent; if(t==root)return; elseparent=rootOfSubTree=path.pop();} } elsebreak; }}//endofwhile132//情況一的處理if(parent->left==t){//兄弟是右孩子

if(sibling->left!=NULL&&sibling->left->colour==0){//R1LorR2sibling->left->colour=parent->colour;parent->colour=1; RL(parent);reLink(rootOfSubTree,parent,path);} else{//R1Rsibling->colour=parent->colour;sibling->right->colour=1; parent->colour=1;RR(parent); reLink(rootOfSubTree,parent,path);}}else{//兄弟是左孩子

if(sibling->right!=NULL&&sibling->right->colour==0){//L1RorL2sibling->right->colour=parent->colour;parent->colour=1; LR(parent); reLink(rootOfSubTree,parent,path);} else{//L1Lsibling->colour=parent->colour; sibling->left->colour=1;parent->colour=1; LL(parent);reLink(rootOfSubTree,parent,path);}}}133第8章動(dòng)態(tài)查找表二叉查找樹AVL樹紅黑樹AA樹伸展樹B樹和B+樹STL中的動(dòng)態(tài)查找表134AA樹AA樹的定義AA樹的插入操作AA樹的刪除操作AA樹類的實(shí)現(xiàn)135AA樹定義：左孩子不能為紅色的紅黑樹優(yōu)點(diǎn)：它省去了一半的需要重構(gòu)的情況；簡(jiǎn)化了重新平衡的過程136141235928156050202530232470一棵AA樹137AA樹的水平鏈表示法將指向紅結(jié)點(diǎn)的鏈畫成水平的，可以看出所有葉子的高度都是相同的141235928156050202530232470138用水平鏈表示的AA樹的特征：水平鏈?zhǔn)怯覂鹤渔湥ㄒ驗(yàn)橹挥杏覂鹤硬趴赡苁羌t色的）不可能有左水平鏈（因?yàn)樽鰞鹤硬豢赡転榧t色）不可能有兩條連續(xù)的水平鏈（因?yàn)椴粫?huì)有連續(xù)的紅色結(jié)點(diǎn)）如果一個(gè)結(jié)點(diǎn)沒有右水平鏈的話，它的兩個(gè)兒子就在同一層139節(jié)點(diǎn)的層次如果結(jié)點(diǎn)是一個(gè)葉子的話，層次為1如果結(jié)點(diǎn)是紅色的，就是它父親的層次如果結(jié)點(diǎn)是黑色的，比它父親的層次少1在AA樹中，我們用節(jié)點(diǎn)的層次表示平衡信息140AA樹AA樹的定義AA樹的插入操作AA樹的刪除操作AA樹類的實(shí)現(xiàn)141AA樹的插入如普通的紅黑樹，新節(jié)點(diǎn)總是插入為葉子且為紅節(jié)點(diǎn)。但可能引起不平衡：插入為左子樹，則出現(xiàn)水平左鏈。這是不允許的插入為一個(gè)紅節(jié)點(diǎn)的右子樹，則出現(xiàn)連續(xù)的水平右鏈，也是不允許的不管是哪一種情況，進(jìn)行一次單旋轉(zhuǎn)就可以解決問題了142水平左鏈的解決（LL旋轉(zhuǎn)）節(jié)點(diǎn)和左孩子進(jìn)行一個(gè)單旋PXPLPRXRPXPLPRXR可能出現(xiàn)連續(xù)的水平右鏈，需要繼續(xù)調(diào)整143連續(xù)的水平右鏈問題(RR)對(duì)前兩個(gè)節(jié)點(diǎn)進(jìn)行一次旋轉(zhuǎn)中間的結(jié)點(diǎn)層次增長(zhǎng)了1，這樣又會(huì)給X原來的父親帶來了問題：出現(xiàn)水平左鏈或是連續(xù)的水平右鏈，但不管是什么問題，都可以通過在向根回溯的過程中反復(fù)應(yīng)用skew/split策略來解決XRPL