節(jié)點標識

待刪除節(jié)點D
兄弟節(jié)點B
侄子節(jié)點C
父親節(jié)點P
雙黑節(jié)點N

刪除步驟

首先分為三類：

• D有2個非空子節(jié)點
  • 找到D的后續(xù)節(jié)點back较沪，將back的值傳遞給D侨核，此時待刪除節(jié)點變?yōu)? back，而此時的back一定只有一個外部子節(jié)點乙帮，因此轉(zhuǎn)為第三類

// 待刪除節(jié)點有2個外部子節(jié)點
    if (n.left != null && n.right != null) {
        // 后繼節(jié)點
        RBNode<T> back = successor(n);
        n.data = back.data;
        delete(back);
        return;
    }

• D沒有非空子節(jié)點
  • 判斷當前節(jié)點是否為根節(jié)點root，若是，則直接root = null捧搞。否則，直接刪除該節(jié)點狮荔，判斷該節(jié)點為黑胎撇，則出現(xiàn)雙黑節(jié)點N，需要進行雙黑節(jié)點處理fixAfterDelete()

// 待刪除節(jié)點沒有外部子節(jié)點
    else if (n.left == null && n.right == null) {
        if (isLeft(n))
            p.left = null;
        else if (isRight(n))
            p.right = null;
        else {// 說明待刪除的節(jié)點子節(jié)點為null殖氏，且父節(jié)點為null晚树，此時樹中僅剩根節(jié)點
            root = null;
            return;
        }
    }
       ...
       if (!isRed(n))
        fixAfterDelete(n,p);

• D只有1個非空子節(jié)點
  • 若D為根節(jié)點root，直接將非空子節(jié)點稱為根節(jié)點root受葛，并將節(jié)點顏色修正為黑色题涨，算法結(jié)束

// n為根節(jié)點
    else {
        root = n.left == null?n.right:n.left;
        root.parent = null;
        root.color = BLACK;
        return;
    }

• 若D為紅色，直接刪除总滩，算法結(jié)束纲堵。若D為黑色，且有一個紅色子節(jié)點闰渔，則將子節(jié)點取代D的位置席函，并將顏色修正為黑色，結(jié)束算法
• 出現(xiàn)雙黑節(jié)點冈涧，需要進行雙黑節(jié)點處理fixAfterDelete()

雙黑節(jié)點處理

分為三類：

• 雙黑節(jié)點N的兄弟節(jié)點B為紅色
  • 交換N.parent和B的顏色茂附。B為右，則B左旋督弓；B為左营曼，則B右旋。該變換后愚隧，轉(zhuǎn)為第二類情況

// 兄弟節(jié)點為紅色蒂阱，先做顏色變換和旋轉(zhuǎn)操作
    if (isRed(brother)) {
        // 父節(jié)點與兄弟交換顏色
        boolean temp = p.color;
        p.color = brother.color;
        brother.color = temp;
        // 兄弟在右，則左旋狂塘；反之
        if (isRight(brother))
            left_rotate(p);
        else
            right_rotate(p);
        // 得到新的兄弟節(jié)點
        brother = p.left == null?p.right:p.left;
    }

• 雙黑節(jié)點N的兄弟節(jié)點B為黑色
  • B存在紅色子節(jié)點C
    (1). B和C都是左子節(jié)點/右子節(jié)點（遠侄子）：B.color = N.parent.color录煤、C.color = BLACK、N.parent.color = BLACK荞胡，對N.parent作左旋/右旋
    (2). B為右/左妈踊、C為左/右（近侄子）：B先作右旋/左旋，轉(zhuǎn)為情況1

// 兄弟節(jié)點存在紅色子節(jié)點
        if (isRed(brother.left) || isRed(brother.right)) {
            // 紅色子節(jié)點
            RBNode<T> redC = isRed(brother.left)?brother.left:brother.right;
            fixWhenBrotherHasRed(p,brother,redC);
        }
// 當兄弟節(jié)點存在紅色子節(jié)點的情況下進行調(diào)整
    // 輸入?yún)?shù)：父節(jié)點泪漂、兄弟節(jié)點廊营、紅色子節(jié)點
    private void fixWhenBrotherHasRed(RBNode<T> p, RBNode<T> b, RBNode<T> c) {
        if (isRight(b) && isLeft(c)) {
            right_rotate(b);
            // 近侄子和兄弟互換歪泳，變?yōu)檫h侄子情況
            RBNode<T> temp;
            temp = c;
            c = b;
            b = temp;
        }
        if (isLeft(b) && isRight(c)) {
            left_rotate(b);
            // 近侄子和兄弟互換，變?yōu)檫h侄子情況
            RBNode<T> temp;
            temp = c;
            c = b;
            b = temp;
        }
        b.color = p.color;
        p.color = BLACK;
        c.color = BLACK;
        if (isRight(b))
            left_rotate(p);
        else
            right_rotate(p);
    }

* B有兩個黑色子節(jié)點(包括`NIL節(jié)點`)

作以下調(diào)整：B.color = RED赘风，N.parent.color = BLACK夹囚。若N.parent.color原來為紅色，則算法結(jié)束邀窃。否則荸哟，將N.parent作為新的雙黑節(jié)點，繼續(xù)fixAfterDelete()

//兄弟節(jié)點存在2個黑色子節(jié)點瞬捕，包含NIL節(jié)點
    else {
        brother.color = RED;
        if (isRed(p)) {
            p.color = BLACK;
        }else {
            // 若父節(jié)點原來為black鞍历，則父節(jié)點作為新的雙黑節(jié)點繼續(xù)調(diào)整，直到根節(jié)點
            if (p.parent != null)
                fixAfterDelete(p,p.parent);
        }
    }

后續(xù)傳圖