紅黑樹的增加(插入)和删除

紅黑樹的增加(插入)和删除

☼ 紅黑樹之介紹：

-----------形态上是特殊的二叉搜尋樹【特殊展現在顔色上，同時在邏輯上它是等價于4階B樹的】

❀ 紅黑樹是怎麼等價于4 階B 樹的？ ---------紅黑樹要變成B樹：需要将紅結點和黑結點進行合并（黑色作為根【也是中間元素】）。

✿ 紅黑-->B 樹： 結點有四種情況是：①紅-黑-紅、②紅-黑、③黑-紅、④黑

● 可以插入的位置的所有情況：

◼ 紅黑樹必須滿足以下 5 條性質: 1. 節點是 RED 或者 BLACK 2. 根節點是 BLACK 3. 葉子節點（外部節點，空節點）都是 BLACK 4. RED 節點的子節點都是 BLACK: ✓ RED 節點的 parent 都是 BLACK ✓ 從根節點到葉子節點的所有路徑上不能有 2 個連續的 RED 節點 5. 從任一節點到葉子節點的所有路徑都包含相同數目的 BLACK 節點

一、紅黑樹結點的添加(插入)--添加必是添加到 -B樹葉子子結點的位置：

(1) 4階 B 樹的葉子結點一般有以下四種情況：

①    紅<---黑--->紅    ② 紅<---黑        ③ 黑--->紅      ④ 黑

(2) 分類讨論：

（2-1）當父結點是黑色（有四種情況）時【上圖的 7、8、11、12】，直接插入；【有可能是第一個結點-根(記得染黑根)】;

（2-2）剩下8種情況根據 叔父結點是否為紅色進行劃分：

（2-2-1）叔父是紅色時【上圖的 1、2、3、4】，舉個栗子：   紅(新插入的)<---紅<---黑【根】--->紅 （對于4階B樹而言，發生了上溢了，需要，進行分裂處理，根（染紅）上去，然後父結點、叔父結點染黑）；即 ：

 （2-2-2）叔父不是紅色時【上圖的 5、6、9、10】，舉個栗子：   紅(新插入的)<---紅<---黑【根】：為了滿足紅黑樹定義的性質四：

   紅(新插入的)<---紅(變黑)<---黑【根】(變紅，因為B樹的結點組合中是紅黑紅（隻有一個黑作為中間元素的根））

  ●  現在需要修改：中間的黑色為根，需要修改那個<---的方向：改為：

  紅(新插入的)<---紅(變黑) 【根】--->黑【根】(變紅)

[觀察此刻情況，修改這種修改，符合右旋，再觀察其實就是跟AVL 的LL型原理一緻啦]

❀ 紅黑樹整個添加之後的處理的代碼如下：

@Override
    protected void afterAdd(Node<E> node) {
        // 判斷父結點
        Node<E> parent = node.parent;
        // 添加的是根【當添加第一個結點時】/ 或者上溢到了根結點時
        if (parent == null) {
            black(node);
            return;
        }
        // 若父結點是黑色時，不用處理，直接傳回
        if (isBlack(parent))
            return;

        // 若叔父結點是紅色的[B 樹的上溢]
        Node<E> uncle = parent.sibling();
        Node<E> grand = red(parent.parent);
        if (isRed(uncle)) {
            // 染黑爸爸、叔叔，把祖父染成紅色，相當于新插入的結點
            black(uncle);
            black(parent);
//            red(grand);
//            afterAdd(grand);
            // ① 上溢時，也要染紅祖父結點
//            afterAdd(red(grand));
            afterAdd(grand);
            return;
        }
        //觀察一下，對代碼進行優化，共同擁有的抽到外部之類的
        // 來到這裡叔父不是紅色
        if (parent.isLeftChild()) { // L
            // ② 旋轉時，也要 染紅結點
//            red(grand);
            
            if (node.isLeftChild()) { // LL
                //染黑父結點，染紅祖父結點
                black(parent);
//                red(grand);
                //右旋
//                rotateRight(grand);
            } else { // LR
                //染紅自己、染黑祖父結點
                black(node);
//                red(grand);
                //左旋後右旋
                rotateLeft(parent);
//                rotateRight(grand);
            }
            
            rotateRight(grand);
        } else { // R
            // ② 旋轉時，也要 染紅結點
//            red(grand);
            
            if (node.isLeftChild()) { // RL
                //染紅自己、染黑祖父結點
                black(node);
//                red(grand);
                //左旋後右旋
                rotateRight(parent);
//                rotateLeft(grand);
            } else { // RR
                //染黑父結點，染紅祖父結點
                black(parent);
//                red(grand);
                //左旋
//                rotateLeft(grand);
            }
            
            rotateLeft(grand);
        }
    }      

二、紅黑樹結點的删除--删除必是 -B樹葉子子結點的位置：

● 可以删除的位置的所有情況：

(2-1) 删除的直接是紅色結點時【上圖的 1、3、5、6】【2也一樣（因為它是度為2，最終删除的要麼是前驅的1或者後驅的3）】，就直接删除，不用處理。

(2-2) 删除的是黑色的結點：

（2-2-1）用來替代的結點是紅色時【上圖的 4、7】，處理：将替代的結點【5、6】染成黑色（因為替代成為了B樹的葉子結點了，根是黑色的）。

 （2-2-2）用來替代的結點是黑色時【上圖的 8】，處理：

 ❀ 紅黑樹整個删除結點之後的處理的代碼如下：

@Override
    protected void afterRemove(Node<E> node) {
        //要删除結點是紅色，直接删除，不用處理
//        if(isRed(node))    return;
        //要删除的結點是黑色 ，然後用于替換删除結點的子結點是紅色，然後替換結點即可
        if(isRed(node)) {    //這裡的處理是包含了上面if(isRed(node))的情況
            black(node);
            return;
        }
        Node<E> parent = node.parent;
        //删除的是根結點，也是直接删除不用處理
        if(parent == null)    return;

        // 要删除結點是黑色，而且是葉子結點，沒有可以替換的結點時，
        // 判斷被删除的node 是左還是右，直接通過sibling 去拿就已經不準了，因為葉子結點已經删除了，拿不到哦 了
        // 需重新判斷一下
        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;
        if (left) { // 被删除的是左邊的，兄弟結點在右邊
            if (isRed(sibling)) { // 兄弟結點是紅色，相當于以前删除時，先考慮删除度為2，将度為2的進行第一步處理後，它就變成了與删除度為1、0 的情況一緻了
                black(sibling); // 等下變成根
                red(parent);
                rotateLeft(parent);// 通過左邊旋轉，侄子變成了我的兄弟了
                // 更換兄弟
                sibling = parent.right;
            }
            // 現在來到這裡的兄弟都是黑色的啦
            if (isBlack(sibling.left) && isBlack(sibling.right)) { // 黑兄弟的孩子是黑色的，不能借【沒有紅色結點可以外借】
                // 借不了，隻能讓父結點下來進行跟兄弟合并【将父結點染黑（變成根），兄弟染紅】
                // 染色之前還需要考慮父結點原先是不是黑色【黑色會導緻下溢】
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    // 下溢，遞歸處理，相當于父結點被删除
                    afterRemove(parent);
                }

            } else { // 兄弟結點至少有一個紅色子結點【可以外借時】
                // 即接下來的情況： 黑【根】->紅 紅<-黑【根】 紅<-黑【根】->紅
                // 兄弟結點的右邊是黑色，兄弟要先旋轉【即先處理情況： 黑->紅，處理完後，接下來變成了 RR的情況，與後邊兩者是一樣隻需要左旋轉】
                if (isBlack(sibling.right)) {
                    rotateRight(sibling);
                    sibling = parent.right; // 修改兄弟結點位置
                }

                // 染色處理【上去的兄弟，要保證顔色與原來的相同，結構不變 】
                color(sibling, colorOf(parent));

                // 兄弟的兒子【可以借的結點】要上去作為根
                black(sibling.right);
                // 父結點要旋轉下來作為根
                black(parent);

                rotateLeft(parent);
            }

        } else { // 删除結點是在右邊的，兄弟結點在左邊的
            if (isRed(sibling)) { // 兄弟結點是紅色，相當于以前删除時，先考慮删除度為2，将度為2的進行第一步處理後，它就變成了與删除度為1、0 的情況一緻了
                black(sibling); // 等下變成根
                red(parent);
                rotateRight(parent);// 通過右邊旋轉，侄子變成了我的兄弟了
                // 更換兄弟
                sibling = parent.left;
            }
            // 現在來到這裡的兄弟都是黑色的啦
            if (isBlack(sibling.left) && isBlack(sibling.right)) { // 黑兄弟的兄弟是黑色的，不能借【沒有紅色結點可以外借】
                // 借不了，隻能讓父結點下來進行跟兄弟合并【将父結點染黑（變成根），兄弟染紅】
                // 染色之前還需要考慮父結點原先是不是黑色【黑色會導緻下溢】
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    // 下溢，遞歸處理，相當于父結點被删除
                    afterRemove(parent);
                }

            } else { // 兄弟結點至少有一個紅色子結點【可以外借時】
                // 即接下來的情況： 黑【根】->紅 紅<-黑【根】 紅<-黑【根】->紅
                // 兄弟結點的左邊是黑色，兄弟要先旋轉【即先處理情況： 黑->紅，處理完後，接下來變成了 LL的情況，與後邊兩者是一樣隻需要右旋轉】
                if (isBlack(sibling.left)) {
                    rotateLeft(sibling);
                    sibling = parent.left; // 修改兄弟結點位置
                }

                // 染色處理【上去的兄弟，要保證顔色與原來的相同，結構不變 】
                color(sibling, colorOf(parent));

                // 兄弟的兒子【可以借的結點】要上去作為根
                black(sibling.left);
                // 父結點要旋轉下來作為根
                black(parent);

                rotateRight(parent);

            }
        }
    }