紅黑樹深入剖析及Java實現(xiàn)

1、紅黑樹深入剖析及Java實現(xiàn)在理想的情況下，二叉查找樹增刪查改的時間復(fù)雜度為O(logN)（其中N為節(jié)點數(shù)），最壞的情況下為O(N)。當它的高度為logN+1時，我們就說二叉查找樹是平衡的。作者：振興來源：振興|2016-12-08 11:01 收藏   分享  紅黑樹是平衡二叉查找樹的一種。為了深入理解紅黑樹，我們需要從二叉查找樹開始講起。BST二叉查找樹（Binary Search Tree，簡稱BST）是一棵二叉樹，它的左子節(jié)點的值比父節(jié)點的值要小，右節(jié)點的值要比父節(jié)點的值大。它的高度決定了它的查找效率。在理想的情況下，二叉查找樹增刪查改的時間復(fù)雜

2、度為O(logN)（其中N為節(jié)點數(shù)），最壞的情況下為O(N)。當它的高度為logN+1時，我們就說二叉查找樹是平衡的。BST的查找操作1. T  key = a search key 2. Node root = point to the root of a BST 3.  4. while(true) 5.     if(root=null) 6.

3、60;       break; 7.      8.     if(root.value.equals(key) 9.         return root; 10.      11.     else if(par

4、eTo(root.value)<0) 12.         root = root.left; 13.      14.     else 15.         root = root.right; 16.     &#

5、160;17.  18. return null; 從程序中可以看出，當BST查找的時候，先與當前節(jié)點進行比較：· 如果相等的話就返回當前節(jié)點；· 如果少于當前節(jié)點則繼續(xù)查找當前節(jié)點的左節(jié)點；· 如果大于當前節(jié)點則繼續(xù)查找當前節(jié)點的右節(jié)點。直到當前節(jié)點指針為空或者查找到對應(yīng)的節(jié)點，程序查找結(jié)束。BST的插入操作1. Node node = create a new node with specify value 2. Node 

6、;root = point the root node of a BST 3. Node parent = null; 4.  5. /find the parent node to append the new node 6. while(true) 7.    if(root=null)break; 8. 

7、0;  parent = root; 9.    if(pareTo(root.value)<=0) 10.       root = root.left;   11.    else 12.       root = root.right; 13.  

8、    14.  15. if(parent!=null) 16.    if(pareTo(parent.value)<=0)/append to left 17.       parent.left = node; 18.    else/append to right 19.    &#

9、160;  parent.right = node; 20.     21.  插入操作先通過循環(huán)查找到待插入的節(jié)點的父節(jié)點，和查找父節(jié)點的邏輯一樣，都是比大小，小的往左，大的往右。找到父節(jié)點后，對比父節(jié)點，小的就插入到父節(jié)點的左節(jié)點，大就插入到父節(jié)點的右節(jié)點上。BST的刪除操作刪除操作的步驟如下：1. 查找到要刪除的節(jié)點。2. 如果待刪除的節(jié)點是葉子節(jié)點，則直接刪除。3. 如果待刪除的節(jié)點不是葉子節(jié)點，則先找到待刪除節(jié)點的中序遍歷的后繼節(jié)點，用該后繼節(jié)點的值替換待刪除的節(jié)點的值，然后刪除后繼節(jié)

10、點。BST存在的問題BST存在的主要問題是，數(shù)在插入的時候會導(dǎo)致樹傾斜，不同的插入順序會導(dǎo)致樹的高度不一樣，而樹的高度直接的影響了樹的查找效率。理想的高度是logN，最壞的情況是所有的節(jié)點都在一條斜線上，這樣的樹的高度為N。RBTree基于BST存在的問題，一種新的樹平衡二叉查找樹(Balanced BST)產(chǎn)生了。平衡樹在插入和刪除的時候，會通過旋轉(zhuǎn)操作將高度保持在logN。其中兩款具有代表性的平衡樹分別為AVL樹和紅黑樹。AVL樹由于實現(xiàn)比較復(fù)雜，而且插入和刪除性能差，在實際環(huán)境下的應(yīng)用不如紅黑樹。紅黑樹（Red-Black Tree，以下簡稱RBTree）的實際應(yīng)用非常廣泛，比如Linu

11、x內(nèi)核中的完全公平調(diào)度器、高精度計時器、ext3文件系統(tǒng)等等，各種語言的函數(shù)庫如Java的TreeMap和TreeSet，C+ STL的map、multimap、multiset等。RBTree也是函數(shù)式語言中最常用的持久數(shù)據(jù)結(jié)構(gòu)之一，在計算幾何中也有重要作用。值得一提的是，Java 8中HashMap的實現(xiàn)也因為用RBTree取代鏈表，性能有所提升。RBTree的定義RBTree的定義如下:1. 任何一個節(jié)點都有顏色，黑色或者紅色2. 根節(jié)點是黑色的3. 父子節(jié)點之間不能出現(xiàn)兩個連續(xù)的紅節(jié)點4. 任何一個節(jié)點向下遍歷到其子孫的葉子節(jié)點，所經(jīng)過的黑節(jié)點個數(shù)必須相等5. 空節(jié)點被認為是黑色的數(shù)據(jù)

12、結(jié)構(gòu)表示如下：1. class  Node<T> 2.    public  T value; 3.    public   Node<T> parent; 4.    public   boolean isRed; 5.    public   Node

13、<T> left; 6.    public   Node<T> right; 7.  RBTree在理論上還是一棵BST樹，但是它在對BST的插入和刪除操作時會維持樹的平衡，即保證樹的高度在logN,logN+1（理論上，極端的情況下可以出現(xiàn)RBTree的高度達到2*logN，但實際上很難遇到）。這樣RBTree的查找時間復(fù)雜度始終保持在O(logN)從而接近于理想的BST。RBTree的刪除和插入操作的時間復(fù)雜度也是O(logN)。RBTree的查找操作就是

14、BST的查找操作。RBTree的旋轉(zhuǎn)操作旋轉(zhuǎn)操作(Rotate)的目的是使節(jié)點顏色符合定義，讓RBTree的高度達到平衡。Rotate分為left-rotate（左旋）和right-rotate（右旋），區(qū)分左旋和右旋的方法是：待旋轉(zhuǎn)的節(jié)點從左邊上升到父節(jié)點就是右旋，待旋轉(zhuǎn)的節(jié)點從右邊上升到父節(jié)點就是左旋。RBTree的查找操作RBTree的查找操作和BST的查找操作是一樣的。請參考BST的查找操作代碼。RBTree的插入操作RBTree的插入與BST的插入方式是一致的，只不過是在插入過后，可能會導(dǎo)致樹的不平衡，這時就需要對樹進行旋轉(zhuǎn)操作和顏色修復(fù)（在這里簡稱插入修復(fù)），使得它符合RBTree

15、的定義。新插入的節(jié)點是紅色的，插入修復(fù)操作如果遇到父節(jié)點的顏色為黑則修復(fù)操作結(jié)束。也就是說，只有在父節(jié)點為紅色節(jié)點的時候是需要插入修復(fù)操作的。插入修復(fù)操作分為以下的三種情況，而且新插入的節(jié)點的父節(jié)點都是紅色的：1. 叔叔節(jié)點也為紅色。2. 叔叔節(jié)點為空，且祖父節(jié)點、父節(jié)點和新節(jié)點處于一條斜線上。3. 叔叔節(jié)點為空，且祖父節(jié)點、父節(jié)點和新節(jié)點不處于一條斜線上。插入操作-case 1case 1的操作是將父節(jié)點和叔叔節(jié)點與祖父節(jié)點的顏色互換，這樣就符合了RBTRee的定義。即維持了高度的平衡，修復(fù)后顏色也符合RBTree定義的第三條和第四條。下圖中，操作完成后A節(jié)點變成了新的節(jié)點。如果A節(jié)點的父節(jié)

16、點不是黑色的話，則繼續(xù)做修復(fù)操作。插入操作-case 2case 2的操作是將B節(jié)點進行右旋操作，并且和父節(jié)點A互換顏色。通過該修復(fù)操作RBTRee的高度和顏色都符合紅黑樹的定義。如果B和C節(jié)點都是右節(jié)點的話，只要將操作變成左旋就可以了。插入操作-case 3case 3的操作是將C節(jié)點進行左旋，這樣就從case 3轉(zhuǎn)換成case 2了，然后針對case 2進行操作處理就行了。case 2操作做了一個右旋操作和顏色互換來達到目的。如果樹的結(jié)構(gòu)是下圖的鏡像結(jié)構(gòu)，則只需要將對應(yīng)的左旋變成右旋，右旋變成左旋即可。插入操作的總結(jié)插入后的修復(fù)操作是一個向root節(jié)點回溯的操作，一旦牽涉的節(jié)點都符合了紅黑

17、樹的定義，修復(fù)操作結(jié)束。之所以會向上回溯是由于case 1操作會將父節(jié)點，叔叔節(jié)點和祖父節(jié)點進行換顏色，有可能會導(dǎo)致祖父節(jié)點不平衡(紅黑樹定義3)。這個時候需要對祖父節(jié)點為起點進行調(diào)節(jié)（向上回溯）。祖父節(jié)點調(diào)節(jié)后如果還是遇到它的祖父顏色問題，操作就會繼續(xù)向上回溯，直到root節(jié)點為止，根據(jù)定義root節(jié)點永遠是黑色的。在向上的追溯的過程中，針對插入的3中情況進行調(diào)節(jié)。直到符合紅黑樹的定義為止。直到牽涉的節(jié)點都符合了紅黑樹的定義，修復(fù)操作結(jié)束。如果上面的3中情況如果對應(yīng)的操作是在右子樹上，做對應(yīng)的鏡像操作就是了。RBTree的刪除操作刪除操作首先需要做的也是BST的刪除操作，刪除操作會刪除對應(yīng)的

18、節(jié)點，如果是葉子節(jié)點就直接刪除，如果是非葉子節(jié)點，會用對應(yīng)的中序遍歷的后繼節(jié)點來頂替要刪除節(jié)點的位置。刪除后就需要做刪除修復(fù)操作，使的樹符合紅黑樹的定義，符合定義的紅黑樹高度是平衡的。刪除修復(fù)操作在遇到被刪除的節(jié)點是紅色節(jié)點或者到達root節(jié)點時，修復(fù)操作完畢。刪除修復(fù)操作是針對刪除黑色節(jié)點才有的，當黑色節(jié)點被刪除后會讓整個樹不符合RBTree的定義的第四條。需要做的處理是從兄弟節(jié)點上借調(diào)黑色的節(jié)點過來，如果兄弟節(jié)點沒有黑節(jié)點可以借調(diào)的話，就只能往上追溯，將每一級的黑節(jié)點數(shù)減去一個，使得整棵樹符合紅黑樹的定義。刪除操作的總體思想是從兄弟節(jié)點借調(diào)黑色節(jié)點使樹保持局部的平衡，如果局部的平衡達到了，

19、就看整體的樹是否是平衡的，如果不平衡就接著向上追溯調(diào)整。刪除修復(fù)操作分為四種情況(刪除黑節(jié)點后)：1. 待刪除的節(jié)點的兄弟節(jié)點是紅色的節(jié)點。2. 待刪除的節(jié)點的兄弟節(jié)點是黑色的節(jié)點，且兄弟節(jié)點的子節(jié)點都是黑色的。3. 待調(diào)整的節(jié)點的兄弟節(jié)點是黑色的節(jié)點，且兄弟節(jié)點的左子節(jié)點是紅色的，右節(jié)點是黑色的(兄弟節(jié)點在右邊)，如果兄弟節(jié)點在左邊的話，就是兄弟節(jié)點的右子節(jié)點是紅色的，左節(jié)點是黑色的。4. 待調(diào)整的節(jié)點的兄弟節(jié)點是黑色的節(jié)點，且右子節(jié)點是是紅色的(兄弟節(jié)點在右邊)，如果兄弟節(jié)點在左邊，則就是對應(yīng)的就是左節(jié)點是紅色的。刪除操作-case 1由于兄弟節(jié)點是紅色節(jié)點的時候，無法借調(diào)黑節(jié)點，所以需要

20、將兄弟節(jié)點提升到父節(jié)點，由于兄弟節(jié)點是紅色的，根據(jù)RBTree的定義，兄弟節(jié)點的子節(jié)點是黑色的，就可以從它的子節(jié)點借調(diào)了。case 1這樣轉(zhuǎn)換之后就會變成后面的case 2，case 3，或者case 4進行處理了。上升操作需要對C做一個左旋操作，如果是鏡像結(jié)構(gòu)的樹只需要做對應(yīng)的右旋操作即可。之所以要做case 1操作是因為兄弟節(jié)點是紅色的，無法借到一個黑節(jié)點來填補刪除的黑節(jié)點。刪除操作-case 2case 2的刪除操作是由于兄弟節(jié)點可以消除一個黑色節(jié)點，因為兄弟節(jié)點和兄弟節(jié)點的子節(jié)點都是黑色的，所以可以將兄弟節(jié)點變紅，這樣就可以保證樹的局部的顏色符合定義了。這個時候需要將父節(jié)點A變成新的節(jié)

21、點，繼續(xù)向上調(diào)整，直到整顆樹的顏色符合RBTree的定義為止。case 2這種情況下之所以要將兄弟節(jié)點變紅，是因為如果把兄弟節(jié)點借調(diào)過來，會導(dǎo)致兄弟的結(jié)構(gòu)不符合RBTree的定義，這樣的情況下只能是將兄弟節(jié)點也變成紅色來達到顏色的平衡。當將兄弟節(jié)點也變紅之后，達到了局部的平衡了，但是對于祖父節(jié)點來說是不符合定義4的。這樣就需要回溯到父節(jié)點，接著進行修復(fù)操作。刪除操作-case 3case 3的刪除操作是一個中間步驟，它的目的是將左邊的紅色節(jié)點借調(diào)過來，這樣就可以轉(zhuǎn)換成case 4狀態(tài)了，在case 4狀態(tài)下可以將D，E節(jié)點都階段過來，通過將兩個節(jié)點變成黑色來保證紅黑樹的整體平衡。之所以說cas

22、e-3是一個中間狀態(tài)，是因為根據(jù)紅黑樹的定義來說，下圖并不是平衡的，他是通過case 2操作完后向上回溯出現(xiàn)的狀態(tài)。之所以會出現(xiàn)case 3和后面的case 4的情況，是因為可以通過借用侄子節(jié)點的紅色，變成黑色來符合紅黑樹定義4.刪除操作-case 4Case 4的操作是真正的節(jié)點借調(diào)操作，通過將兄弟節(jié)點以及兄弟節(jié)點的右節(jié)點借調(diào)過來，并將兄弟節(jié)點的右子節(jié)點變成紅色來達到借調(diào)兩個黑節(jié)點的目的，這樣的話，整棵樹還是符合RBTree的定義的。Case 4這種情況的發(fā)生只有在待刪除的節(jié)點的兄弟節(jié)點為黑，且子節(jié)點不全部為黑，才有可能借調(diào)到兩個節(jié)點來做黑節(jié)點使用，從而保持整棵樹都符合紅黑樹的定義。刪除操作

23、的總結(jié)紅黑樹的刪除操作是最復(fù)雜的操作，復(fù)雜的地方就在于當刪除了黑色節(jié)點的時候，如何從兄弟節(jié)點去借調(diào)節(jié)點，以保證樹的顏色符合定義。由于紅色的兄弟節(jié)點是沒法借調(diào)出黑節(jié)點的，這樣只能通過選擇操作讓他上升到父節(jié)點，而由于它是紅節(jié)點，所以它的子節(jié)點就是黑的，可以借調(diào)。對于兄弟節(jié)點是黑色節(jié)點的可以分成3種情況來處理，當所以的兄弟節(jié)點的子節(jié)點都是黑色節(jié)點時，可以直接將兄弟節(jié)點變紅，這樣局部的紅黑樹顏色是符合定義的。但是整顆樹不一定是符合紅黑樹定義的，需要往上追溯繼續(xù)調(diào)整。對于兄弟節(jié)點的子節(jié)點為左紅右黑或者 (全部為紅，右紅左黑)這兩種情況，可以先將前面的情況通過選擇轉(zhuǎn)換為后一種情況，在后一種情況下，因為兄弟

24、節(jié)點為黑，兄弟節(jié)點的右節(jié)點為紅，可以借調(diào)出兩個節(jié)點出來做黑節(jié)點，這樣就可以保證刪除了黑節(jié)點，整棵樹還是符合紅黑樹的定義的，因為黑色節(jié)點的個數(shù)沒有改變。紅黑樹的刪除操作是遇到刪除的節(jié)點為紅色，或者追溯調(diào)整到了root節(jié)點，這時刪除的修復(fù)操作完畢。RBTree的Java實現(xiàn)1. public class RBTreeNode<T extends Comparable<T>>  2.     private T value;/node value&

25、#160;3.     private RBTreeNode<T> left;/left child pointer 4.     private RBTreeNode<T> right;/right child pointer 5.     private RBTreeNode<T> parent;/parent

26、0;pointer 6.     private boolean red;/color is red or not red 7.  8.     public RBTreeNode() 9.     public RBTreeNode(T value)this.value=value; 10.    

27、; public RBTreeNode(T value,boolean isRed)this.value=value;this.red = isRed; 11.  12.     public T getValue()  13.         return value; 14.      

28、;15.     void setValue(T value)  16.         this.value = value; 17.      18.     RBTreeNode<T> getLeft()  19.     

29、0;   return left; 20.      21.     void setLeft(RBTreeNode<T> left)  22.         this.left = left; 23.      24.   

30、  RBTreeNode<T> getRight()  25.         return right; 26.      27.     void setRight(RBTreeNode<T> right)  28.       &

31、#160; this.right = right; 29.      30.     RBTreeNode<T> getParent()  31.         return parent; 32.      33.     void&

32、#160;setParent(RBTreeNode<T> parent)  34.         this.parent = parent; 35.      36.     boolean isRed()  37.         return

33、 red; 38.      39.     boolean isBlack() 40.         return !red; 41.      42.     /* 43.     * is leaf&#

34、160;node 44.     */ 45.     boolean isLeaf() 46.         return left=null && right=null; 47.      48.  49.     void s

35、etRed(boolean red)  50.         this.red = red; 51.      52.  53.     void makeRed() 54.         red=true; 55.   &#

36、160;  56.     void makeBlack() 57.         red=false; 58.      59.     Override 60.     public String toString() 61.   &

37、#160;     return value.toString(); 62.      63.  64.  65. public class RBTree<T extends Comparable<T>>  66.     private final RBTreeNode<T> root;&#

38、160;67.     /node number 68.     private java.util.concurrent.atomic.AtomicLong size =  69.                     new java

39、.util.concurrent.atomic.AtomicLong(0); 70.  71.     /in overwrite mode,all node's value can not  has same    value 72.     /in non-overwrite mode,node can h

40、ave same value, suggest don't use non-overwrite mode. 73.     private volatile boolean overrideMode=true; 74.  75.     public RBTree() 76.        

41、 this.root = new RBTreeNode<T>(); 77.      78.  79.     public RBTree(boolean overrideMode) 80.         this(); 81.        &

42、#160;this.overrideMode=overrideMode; 82.      83.  84.     public boolean isOverrideMode()  85.         return overrideMode; 86.      87.  88. &#

43、160;   public void setOverrideMode(boolean overrideMode)  89.         this.overrideMode = overrideMode; 90.      91.  92.     /* 93.    

44、;  * number of tree number 94.      * return 95.      */ 96.     public long getSize()  97.         return size.get

45、(); 98.      99.     /* 100.      * get the root node 101.      * return 102.      */ 103.     private RB

46、TreeNode<T> getRoot() 104.         return root.getLeft(); 105.      106.  107.     /* 108.      * add value to a new node,if

47、 this value exist in this tree, 109.      * if value exist,it will return the exist value.otherwise return null 110.      * if override mode 

48、;is true,if value exist in the tree, 111.      * it will override the old value in the tree 112.      *  113.      * param

49、60;value 114.      * return 115.      */ 116.     public T addNode(T value) 117.         RBTreeNode<T> t = new RBTreeNode<

50、;T>(value); 118.         return addNode(t); 119.      120.     /* 121.      * find the value by give value(include key,key used

51、 for search, 122.      * other field is not used,see compare method).if this value not exist return null 123.      * param value 124.   

52、0;  * return 125.      */ 126.     public T find(T value) 127.         RBTreeNode<T> dataRoot = getRoot(); 128.      &#

53、160;  while(dataRoot!=null) 129.             int cmp = dataRoot.getValue().compareTo(value); 130.             if(cmp<0) 131.   

54、              dataRoot = dataRoot.getRight(); 132.             else if(cmp>0) 133.           

55、;      dataRoot = dataRoot.getLeft(); 134.             else 135.                 return dataRoot.getValue

56、(); 136.              137.          138.         return null; 139.      140.     /* 1

57、41.      * remove the node by give value,if this value not exists in tree return null 142.      * param value include search key 143.   

58、;   * return the value contain in the removed node 144.      */ 145.     public T remove(T value) 146.         RBTreeNode<T>

59、 dataRoot = getRoot(); 147.         RBTreeNode<T> parent = root; 148.  149.         while(dataRoot!=null) 150.          

60、;   int cmp = dataRoot.getValue().compareTo(value); 151.             if(cmp<0) 152.                 parent =

61、0;dataRoot; 153.                 dataRoot = dataRoot.getRight(); 154.             else if(cmp>0) 155.     &

62、#160;           parent = dataRoot; 156.                 dataRoot = dataRoot.getLeft(); 157.        &

63、#160;    else 158.                 if(dataRoot.getRight()!=null) 159.                     

64、RBTreeNode<T> min = removeMin(dataRoot.getRight(); 160.                     /x used for fix color balance 161.      

65、60;              RBTreeNode<T> x = min.getRight()=null ? min.getParent() : min.getRight(); 162.               

66、0;     boolean isParent = min.getRight()=null; 163.  164.                     min.setLeft(dataRoot.getLeft(); 165.      

67、               setParent(dataRoot.getLeft(),min); 166.                     if(parent.getLeft()=dataRoot) 167.  

68、;                       parent.setLeft(min); 168.                     else 

69、169.                         parent.setRight(min); 170.                     

70、; 171.                     setParent(min,parent); 172.  173.                     bool

71、ean curMinIsBlack = min.isBlack(); 174.                     /inherit dataRoot's color 175.            

72、0;        min.setRed(dataRoot.isRed(); 176.  177.                     if(min!=dataRoot.getRight() 178.        

73、                 min.setRight(dataRoot.getRight(); 179.                         setParent(

74、dataRoot.getRight(),min); 180.                      181.                     /remove 

75、a black node,need fix color 182.                     if(curMinIsBlack) 183.                

76、0;        if(min!=dataRoot.getRight() 184.                             fixRemove(x,isParent); 185.   

77、;                      else if(min.getRight()!=null) 186.                     &#

78、160;       fixRemove(min.getRight(),false); 187.                         else 188.         

79、0;                   fixRemove(min,true); 189.                          190

80、.                      191.                 else 192.          &#

81、160;          setParent(dataRoot.getLeft(),parent); 193.                     if(parent.getLeft()=dataRoot) 194.     

82、0;                   parent.setLeft(dataRoot.getLeft(); 195.                     else 196. 

83、0;                       parent.setRight(dataRoot.getLeft(); 197.                    

84、  198.                     /current node is black and tree is not empty 199.            &#

85、160;        if(dataRoot.isBlack() && !(root.getLeft()=null) 200.                         RBTreeNode<T> x&#

86、160;= dataRoot.getLeft()=null  201.                                          

87、60;  ? parent :dataRoot.getLeft(); 202.                         boolean isParent = dataRoot.getLeft()=null; 203.    

88、0;                    fixRemove(x,isParent); 204.                      205.   &#

89、160;              206.                 setParent(dataRoot,null); 207.             

90、60;   dataRoot.setLeft(null); 208.                 dataRoot.setRight(null); 209.                 if(getRoot()!=null

91、) 210.                     getRoot().setRed(false); 211.                     getRoot().set

92、Parent(null); 212.                  213.                 size.decrementAndGet(); 214.       

93、60;         return dataRoot.getValue(); 215.              216.          217.         return

94、0;null; 218.      219.     /* 220.      * fix remove action 221.      * param node 222.      * param isParent 223.  

95、;    */ 224.     private void fixRemove(RBTreeNode<T> node,boolean isParent) 225.         RBTreeNode<T> cur = isParent ? null : node; 226.

96、         boolean isRed = isParent ? false : node.isRed(); 227.         RBTreeNode<T> parent = isParent ? node : node.getParent(); 228.

97、  229.         while(!isRed && !isRoot(cur) 230.             RBTreeNode<T> sibling = getSibling(cur,parent); 231.      &#

98、160;      /sibling is not null,due to before remove tree color is balance 232.  233.             /if cur is a left node 

99、234.             boolean isLeft = parent.getRight()=sibling; 235.             if(sibling.isRed() && !isLeft)/case 1 236.   

100、;              /cur in right 237.                 parent.makeRed(); 238.          

101、60;      sibling.makeBlack(); 239.                 rotateRight(parent); 240.             else if(sibling.isRed()

102、60;&& isLeft) 241.                 /cur in left 242.                 parent.makeRed(); 243.  

103、0;              sibling.makeBlack(); 244.                 rotateLeft(parent); 245.          

104、60;  else if(isBlack(sibling.getLeft() && isBlack(sibling.getRight()/case 2 246.                 sibling.makeRed(); 247.         

105、60;       cur = parent; 248.                 isRed = cur.isRed(); 249.               

106、  parent=parent.getParent(); 250.             else if(isLeft && !isBlack(sibling.getLeft()  251.                 

107、;                    && isBlack(sibling.getRight()/case 3 252.                 sibling.makeRed();

108、 253.                 sibling.getLeft().makeBlack(); 254.                 rotateRight(sibling); 255.     

109、        else if(!isLeft && !isBlack(sibling.getRight()  256.                            

110、0;                && isBlack(sibling.getLeft() ) 257.                 sibling.makeRed(); 258.    

111、             sibling.getRight().makeBlack(); 259.                 rotateLeft(sibling); 260.          

112、;   else if(isLeft && !isBlack(sibling.getRight()/case 4 261.                 sibling.setRed(parent.isRed(); 262.          

113、;       parent.makeBlack(); 263.                 sibling.getRight().makeBlack(); 264.                

114、; rotateLeft(parent); 265.                 cur=getRoot(); 266.             else if(!isLeft && !isBlack(sibling.getLeft()&#

115、160;267.                 sibling.setRed(parent.isRed(); 268.                 parent.makeBlack(); 269.     

116、0;           sibling.getLeft().makeBlack(); 270.                 rotateRight(parent); 271.           

117、0;     cur=getRoot(); 272.              273.          274.         if(isRed) 275.      

118、60;      cur.makeBlack(); 276.          277.         if(getRoot()!=null) 278.             getRoot().setRed(false);&

119、#160;279.             getRoot().setParent(null); 280.          281.  282.      283.     /get sibling node 284.   &#

120、160; private RBTreeNode<T> getSibling(RBTreeNode<T> node,RBTreeNode<T> parent) 285.         parent = node=null ? parent : node.getParent(); 286.      &#

121、160;  if(node=null) 287.             return parent.getLeft()=null ? parent.getRight() : parent.getLeft(); 288.          289.     &

122、#160;   if(node=parent.getLeft() 290.             return parent.getRight(); 291.         else 292.            

123、 return parent.getLeft(); 293.          294.      295.  296.     private boolean isBlack(RBTreeNode<T> node) 297.         re

124、turn node=null | node.isBlack(); 298.      299.     private boolean isRoot(RBTreeNode<T> node) 300.         return root.getLeft() = node &&&#

125、160;node.getParent()=null; 301.      302.     /* 303.      * find the successor node 304.      * param node current node's right node

126、60;305.      * return 306.      */ 307.     private RBTreeNode<T> removeMin(RBTreeNode<T> node) 308.         /find the min node&

127、#160;309.         RBTreeNode<T> parent = node; 310.         while(node!=null && node.getLeft()!=null) 311.             parent = node; 312.             node = node.getLeft(); 313.          314.         /remove min no