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

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

關于二叉樹的基本知識，可以參見：Java 實現基本數據結構 2(樹)

以下是算法導論第13章的學習筆記

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

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

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

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

我們把 NIL 視為二叉樹的外結點 (葉子)，而帶關鍵字的結點視為內結點。

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

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

2) 根結點是黑的。

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

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

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

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

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

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

旋轉的目的是讓樹保持紅黑樹的特性。

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

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

        // 左旋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的父節點
            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;
            }
            // 鏈接新的父節點
            x.parent = y;
            y.left = x;
        }
    }

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

關于插入和刪除整理自July大神的blog和youtube的短視頻
youtube

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

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

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

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

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

        //插入
        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){
            // 又分為父結點是祖父結點的左子還是右子，對于對稱性，我們只要解開一個方向就可以了
            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
將紅黑樹內的某一個節點刪除。需要執行的操作依次是：
首先，將紅黑樹當作一顆二叉查找樹，將該節點從二叉查找樹中刪除；
然后，通過 "旋轉和重新著色" 等一系列來修正該樹，使之重新成為一棵紅黑樹。詳細描述如下：

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

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

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

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