摘要：需要執(zhí)行的操作依次是首先，將紅黑樹當(dāng)作一顆二叉查找樹，將該節(jié)點從二叉查找樹中刪除然后，通過旋轉(zhuǎn)和重新著色等一系列來修正該樹，使之重新成為一棵紅黑樹。

雖是讀書筆記，但是如轉(zhuǎn)載請注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復(fù)制黨

關(guān)于二叉樹的基本知識，可以參見：Java 實現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 2(樹)

以下是算法導(dǎo)論第13章的學(xué)習(xí)筆記

BST的各種操作的時間復(fù)雜度是依賴于樹的高度，通過使得BST成為紅黑樹，確保每次對BST進(jìn)行插入和刪除之后，樹的高度上限依然是logn.

紅黑樹，本質(zhì)上來說就是一棵二叉查找樹，而且是平衡的查找二叉樹 -- 讓BST效率更優(yōu)

紅黑樹中每個結(jié)點包含五個域：color,key,left,right 和p。通過對一條從根到葉子的路徑上各個節(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長兩倍。

如果某結(jié)點沒有一個子結(jié)點或父結(jié)點，則該域指向 NIL。

我們把 NIL 視為二叉樹的外結(jié)點 (葉子)，而帶關(guān)鍵字的結(jié)點視為內(nèi)結(jié)點。

一棵二叉樹如果滿足下面的紅黑性質(zhì)，則為一棵紅黑樹：

1) 每個結(jié)點或是紅的，或是黑的。

2) 根結(jié)點是黑的。

3) 每個葉結(jié)點 (NIL) 是黑的。

4) 如果一個結(jié)點是紅的，則它的兩個兒子都是黑的。

5) 對每個結(jié)點，從該結(jié)點到其子孫結(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點。

采用哨兵來代表 NIL，它的 color 域為 BLACK，其它域為任意值。

從某個結(jié)點 x 出發(fā) (不包括該結(jié)點) 到達(dá)一個葉結(jié)點的任意一條路徑上，黑色結(jié)點的個數(shù)稱為該結(jié)點x 的黑高度，用bh(x) 表示。

引理：一顆有 n 個內(nèi)結(jié)點的紅黑樹的高度至多為 2lg(n+1)。

旋轉(zhuǎn)的目的是讓樹保持紅黑樹的特性。

對 x 進(jìn)行左旋，意味著，將 “x 的右孩子” 設(shè)為 “x 的父親節(jié)點”；即，將 x 變成了一個左節(jié)點 (x 成了為 z 的左孩子)！。 因此，左旋中的 “左”，意味著 “被旋轉(zhuǎn)的節(jié)點將變成一個左節(jié)點”。

對 x 進(jìn)行右旋，意味著，將 “x 的左孩子” 設(shè)為 “x 的父親節(jié)點”；即，將 x 變成了一個右節(jié)點 (x 成了為 y 的右孩子)！ 因此，右旋中的 “右”，意味著 “被旋轉(zhuǎn)的節(jié)點將變成一個右節(jié)點”

        // 左旋x
    public void rotate(TreeNode root, TreeNode x){
        if(x.right != null){
            //處理x的右孩子
            TreeNode y = x.right;
            x.right = y.left;
            if(y.left != null)
                y.left.parent = x;
            // 處理x的父節(jié)點
            y.parent = x.parent ;
            if(x.parent != null){
                // 判斷y鏈接的位置
                if(x.parent.left == x){
                    x.parent.left = y;
                }
                if(x.parent.right == x){
                    x.parent.right = y;
                }
            }else{
                root = y;
            }
            // 鏈接新的父節(jié)點
            x.parent = y;
            y.left = x;
        }
    }

Note: 右旋轉(zhuǎn)的時候可以把代碼中的left換成right就好了。

關(guān)于插入和刪除整理自July大神的blog和youtube的短視頻
youtube

重溫下RedBlack tree的五條性質(zhì)：
1 節(jié)點 r or b
2 根 b
3 葉子 b
4 紅色節(jié)點孩子必為黑
5 任意節(jié)點其葉子節(jié)點的路徑包含相同個數(shù)黑節(jié)點

紅黑樹插入過程的思想是：利用BST的插入方法，尋找待插入元素的位置并插入[所以這一部分可以把BST的直接挪過來]。然后（sth different:） 將待插入元素涂紅色。為了保證紅黑樹的五條性質(zhì)，需要調(diào)用輔助程序rbInsertFixup來調(diào)整，對節(jié)點重新著色并旋轉(zhuǎn)。

插入情況（插入的節(jié)點p設(shè)置為紅）有三：
1. 原tree為空樹，所以p設(shè)置為根節(jié)點 -- 解決方案：Just 設(shè)置p為黑就可以
2. 插入節(jié)點的父節(jié)點為黑 -- 無需解決方法，插入后無影響。
3. ** 插入節(jié)點的父節(jié)點為紅 -- 需要rbInsertFixup
case 1: p 的父節(jié)點和叔叔節(jié)點都為紅 -- 解決方案：父+叔 都涂黑；祖父涂紅，p = 祖父從新的當(dāng)前結(jié)點重新開始算法
case 2: p 的父節(jié)點為紅，叔為黑，且p是父節(jié)點的右子 -- 解決方案：p = 父， 左旋p
(case2 實際上有兩種，看youtube 視頻時候才發(fā)現(xiàn))
（這兩種情況可以想象成一個菱形的兩半。只要右子就左旋，左子就右旋）
case 3: p 的父節(jié)點為紅，叔為黑,且p是父節(jié)點的左子 -- 解決方案：父+叔 都涂黑, 父節(jié)點涂黑,祖父涂紅，祖父右旋。
（case3 實際上也有兩種，這兩種情況可以想象成兩條直線，三角形除了底的兩條邊）

上面三種情況 (Case) 處理問題的核心思路都是：將紅色的節(jié)點移到根節(jié)點；然后，將根節(jié)點設(shè)為黑色。

case2 和 case3 的區(qū)分是1. 二者二叉樹的結(jié)構(gòu)不同，菱形和三角 2. 解決方案不同，涂黑or not
最后，把根結(jié)點涂為黑色，整棵紅黑樹便重新恢復(fù)了平衡。

        //插入
        public RBNode insert(RBNode root, RBNode x){
        RBNode y = this.Nil; // Nil
        RBNode p = root;
        // if the node inserted is null
        if(x == null){
            return root;
        }
        // seek the place where x to be inserted
        while(p!=null){         
            if(x.val > p.val){
                y = p;
                p = p.right;
            }
            if(x.val < p.val){
                y = p;
                p = p.left;
            }
        }
        // insert
        if(y == Nil){
            root = x;
        }
        else
        {
            x.parent = y;
            if(x.val > y.val){
                y.right = x;
            }
            else{
                y.left = x;
            }
        }
        // something different from BST insert 
        x.left = Nil;
        x.right = Nil;
        x.color = 0; // set it red;
        // fixup
        rbInsertFixup(root, x);
        return root;
    }

        public void rbInsertFixup(RBNode root, RBNode x){
        // the fixup occurs when x.partent is red
        while(x.parent.color == 0){
            // 又分為父結(jié)點是祖父結(jié)點的左子還是右子，對于對稱性，我們只要解開一個方向就可以了
            if(x.parent == x.parent.parent.left){
                RBNode uncle = x.parent.parent.right;
                // case 1 
                if(uncle.color == 0){
                    x.parent.color = 1;
                    uncle.color = 1; 
                    x.parent.parent.color = 0;
                    x = x.parent.parent;
                }

                else
                {
                    // case 2
                    if(x == x.parent.right){
                    {   
                        x = x.parent;
                        this.rotateLeft(root, x);
                    }
                    // case 3
                    {
                        x.parent.color = 1;
                        x.parent.parent.color = 0;
                        this.rotateRight(root, x.parent.parent);
                    }
                }
            else
            {
                    // same as the clause with right and left child
            }
                    }
                }
            root.color = 1;
            }
    }

摘錄整理自blog
將紅黑樹內(nèi)的某一個節(jié)點刪除。需要執(zhí)行的操作依次是：
首先，將紅黑樹當(dāng)作一顆二叉查找樹，將該節(jié)點從二叉查找樹中刪除；
然后，通過 "旋轉(zhuǎn)和重新著色" 等一系列來修正該樹，使之重新成為一棵紅黑樹。詳細(xì)描述如下：

第一步：將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點刪除。
這和 "刪除常規(guī)二叉查找樹中刪除節(jié)點的方法是一樣的"。分 3 種情況：
① 被刪除節(jié)點沒有兒子，即為葉節(jié)點。那么，直接將該節(jié)點刪除就 OK 了。
② 被刪除節(jié)點只有一個兒子。那么，直接刪除該節(jié)點，并用該節(jié)點的唯一子節(jié)點頂替它的位置。
③ 被刪除節(jié)點有兩個兒子。那么，先找出它的后繼節(jié)點；然后把 “它的后繼節(jié)點的內(nèi)容” 復(fù)制給 “該節(jié)點的內(nèi)容”；之后，刪除 “它的后繼節(jié)點”。在這里，后繼節(jié)點相當(dāng)于替身，在將后繼節(jié)點的內(nèi)容復(fù)制給 "被刪除節(jié)點" 之后，再將后繼節(jié)點刪除。這樣就巧妙的將問題轉(zhuǎn)換為 "刪除后繼節(jié)點" 的情況了，下面就考慮后繼節(jié)點。 在 "被刪除節(jié)點" 有兩個非空子節(jié)點的情況下，它的后繼節(jié)點不可能是雙子非空。既然 "的后繼節(jié)點" 不可能雙子都非空，就意味著 "該節(jié)點的后繼節(jié)點" 要么沒有兒子，要么只有一個兒子。若沒有兒子，則按 "情況①" 進(jìn)行處理；若只有一個兒子，則按 "情況②" 進(jìn)行處理。

第二步：通過 "旋轉(zhuǎn)和重新著色" 等一系列來修正該樹，使之重新成為一棵紅黑樹。
因為 "第一步" 中刪除節(jié)點之后，可能會違背紅黑樹的特性。所以需要通過 "旋轉(zhuǎn)和重新著色" 來修正該樹，使之重新成為一棵紅黑樹。

紅黑樹的應(yīng)用比較廣泛，主要是用它來存儲有序的數(shù)據(jù)，它的時間復(fù)雜度是 O(lgn)，效率非常之高。
例如，Java 集合中的 TreeSet 和 TreeMap，C++ STL 中的 set、map，以及 Linux 虛擬內(nèi)存的管理，都是通過紅黑樹去實現(xiàn)的。

AVL比RBtree更加平衡，但是AVL的插入和刪除會帶來大量的旋轉(zhuǎn)。
所以如果插入和刪除比較多的情況，應(yīng)該使用RBtree, 如果查詢操作比較多，應(yīng)該使用AVL.