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

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

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

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

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

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

紅黑樹(shù)中每個(gè)結(jié)點(diǎn)包含五個(gè)域：color,key,left,right 和p。通過(guò)對(duì)一條從根到葉子的路徑上各個(gè)節(jié)點(diǎn)著色方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)兩倍。

如果某結(jié)點(diǎn)沒(méi)有一個(gè)子結(jié)點(diǎn)或父結(jié)點(diǎn)，則該域指向 NIL。

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

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

1) 每個(gè)結(jié)點(diǎn)或是紅的，或是黑的。

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

3) 每個(gè)葉結(jié)點(diǎn) (NIL) 是黑的。

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

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

采用哨兵來(lái)代表 NIL，它的 color 域?yàn)?BLACK，其它域?yàn)槿我庵怠?/p>

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

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

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

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

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

        // 左旋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é)點(diǎn)
            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é)點(diǎn)
            x.parent = y;
            y.left = x;
        }
    }

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

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

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

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

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

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

case2 和 case3 的區(qū)分是1. 二者二叉樹(shù)的結(jié)構(gòu)不同，菱形和三角 2. 解決方案不同，涂黑or not
最后，把根結(jié)點(diǎn)涂為黑色，整棵紅黑樹(shù)便重新恢復(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é)點(diǎn)是祖父結(jié)點(diǎn)的左子還是右子，對(duì)于對(duì)稱性，我們只要解開(kāi)一個(gè)方向就可以了
            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
將紅黑樹(shù)內(nèi)的某一個(gè)節(jié)點(diǎn)刪除。需要執(zhí)行的操作依次是：
首先，將紅黑樹(shù)當(dāng)作一顆二叉查找樹(shù)，將該節(jié)點(diǎn)從二叉查找樹(shù)中刪除；
然后，通過(guò) "旋轉(zhuǎn)和重新著色" 等一系列來(lái)修正該樹(shù)，使之重新成為一棵紅黑樹(shù)。詳細(xì)描述如下：

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

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

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

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