紅黑樹的其實就是加了操作的AVL樹，這一類的樹形結構戒幔，主要區(qū)別就是調整維護吠谢，刪除維護的策略不同。

因為紅黑樹的情況是高度對稱的诗茎，那么所有的情況都能壓縮一半工坊。

插入操作

插入簡單，主要難點在于插入操作的維護敢订，插入操作需要維護的是什么呢王污？
站在插入點的祖父點看，插入點和插入點的父親都是紅色枢析，這個時候就需要盤它玉掸。

插入情況

你插入點在４，５醒叁，６司浪，７泊业。并且他爹是紅色（８種情況）。那就盤（tiao）它（zheng）啊易。
如果他爹是黑色吁伺，黑點下插紅點，滿足條件租谈，不調篮奄。

插入與插入調整操作

RBTNode *insert_maintain(RBTNode *root) {//插入策略
    if (!has_red_child(root)) return root;
    if (root->lchild->color == 0 && root->rchild->color == 0) {
        if (has_red_child(root->lchild) || has_red_child(root->rchild)) {
            root->color = 0;
            root->lchild->color = root->rchild->color = 1;
        }
        return root;
    } else if (root->lchild->color == 0 && has_red_child(root->lchild)) {
        if (root->lchild->rchild->color == 0) {
            root->lchild = left_rotate(root->lchild);
        }
        root = right_rotate(root);
    } else if (root->rchild->color == 0 && has_red_child(root->rchild)) {
        if (root->rchild->lchild->color == 0) {
            root->rchild = right_rotate(root->rchild);
        }
        root = left_rotate(root);
    } else {
        return root;
    }
    root->color = 0;
    root->lchild->color = root->rchild->color = 1;
    return root;
}


RBTNode *__insert(RBTNode *root, int key) {// 插入
    if (root == NIL) return init(key);
    if (root->key == key) return root;
    else if (root->key < key) root->rchild = __insert(root->rchild, key);
    else root->lchild = __insert(root->lchild, key);
    return insert_maintain(root);
}

RBTNode *insert(RBTNode *root, int key) {
    root = __insert(root, key);
    root->color = 1;
    return root;
}

刪除操作：

刪除的策略：為了調整和少操作，在刪除點以后割去，不管這給點是什么顏色窟却，直接把刪除點的顏色疊加到他爹的點上，這樣他爹的顏色就是１呻逆，２夸赫，這兩種，然后需要維護的是顏色出現(xiàn)有２的情況咖城。

刪除的時候分為三種大情況：
１．刪除點的度為２
２．刪除點的度為１
３．刪除點的度為０

刪除度２茬腿，１，０：找前驅或者后繼宜雀，交換值切平，刪掉前驅后繼
因為是一層一層下去的，遞歸回去的時候一層一層的維護辐董。

刪除的維護：

刪除的情況

這個時候的關鍵點是雙重黑點的兄弟點悴品，１和４點愛是什么顏色就是什么顏色，因為不影響所以不確定郎哭。

1.雙重黑的２點的兄弟點是紅色（如圖此時是３點）他匪，那么來一個以雙重黑２點的父親為根節(jié)點（此時是１)開始的右旋，調整后讓３為根節(jié)點夸研，３點改成黑色邦蜜，然后這個時候２點的父親是１點，在１點看亥至，看１點的左兒子（２點的兄弟）是不是黑色悼沈，不是就繼續(xù)調整，直到進入第２步姐扮。

2.雙重黑的２點的兄弟點是黑色（如圖此時是３點）：

• 雙重黑點（根節(jié)點左兒子）的兄弟節(jié)點右兒子（根節(jié)點右兒子的右兒子）的（３點的右兒子）是黑色絮供，那么以３點右旋，４點成為３的父親茶敏，３點變成紅色，雙重黑的父親左旋惊搏，４變成根節(jié)點忧换，４點顏色變成雙重黑父親顏色，雙重黑父親顏色變成黑色亚茬，雙重黑顏色減去一層
• 雙重黑點（根節(jié)點左兒子）的兄弟節(jié)點右兒子（根節(jié)點右兒子的右兒子）的（３點的右兒子）是紅色，那么以３點父親為root刹缝，左旋３點成為根節(jié)點，３點顏色變成雙重黑父親顏色颈将，雙重黑父親顏色變成黑色，雙重黑顏色減去一層

刪除與刪除調整操作:

RBTNode *erase_maintain(RBTNode *root) { // 刪除策略
    if (root->lchild->color != 2 && root->rchild->color != 2) return root;
    #define UNFINE(a, b) (root->a->color == 2 && root->b->color == 1 && !has_red_child(root->b)) 
    if (UNFINE(lchild, rchild) || UNFINE(rchild, lchild)) {
        root->color += 1;
        root->lchild->color -= 1;
        root->rchild->color -= 1;
        return root;
    }
    #undef  UNFINE
    if (root->lchild->color == 2) {
        if (root->rchild->color == 0) {
            root = left_rotate(root);
            root->color = 1;
            root->lchild->color = 0;
            root->lchild = erase_maintain(root->lchild);
            return root;
        }
        root->lchild->color = 1;
        if (root->rchild->rchild->color != 0) {
            root->rchild = right_rotate(root->rchild);
            root->rchild->color = 1;
            root->rchild->rchild->color = 0;
        }
        root = left_rotate(root);
        root->color = root->lchild->color;
    } else {
        if (root->lchild->color == 0) {
            root = right_rotate(root);
            root->color = 1;
            root->rchild->color = 0;
            root->rchild = erase_maintain(root->rchild);
            return root;
        }
        root->rchild->color = 1;
        if (root->lchild->lchild->color != 0) {
            root->lchild = left_rotate(root->lchild);
            root->lchild->color = 1;
            root->lchild->lchild->color = 0;
        }
        root = right_rotate(root);
        root->color = root->rchild->color;
    }
    root->lchild->color = root->rchild->color = 1;
    return root;
}

RBTNode *__erase(RBTNode *root, int key) { // 刪除
    if (root == NIL) return NIL;
    if (root->key < key) root->rchild = __erase(root->rchild, key);
    else if (root->key > key) root->lchild = __erase(root->lchild, key);
    else {
        if (root->lchild != NIL && root->rchild != NIL) {
            RBTNode *temp = preacessor(root);
            root->key = temp->key;
            root->lchild = __erase(root->lchild, temp->key);
        } else {
            RBTNode *temp = (root->lchild == NIL ? root->rchild : root->lchild);
            temp->color += root->color;
            free(root);
            return temp;
        }
    }
    return erase_maintain(root);
}

RBTNode *erase(RBTNode *root, int key) {
    root = __erase(root, key);
    root->color = 1;
    return root;
} 

其他結構操作：

typedef struct RBTNode {
    int key;
    int color;
    struct RBTNode *lchild, *rchild;
} RBTNode;


RBTNode *NIL;
__attribute__((constructor))
void init_NIL() {
    NIL = (RBTNode *)malloc(sizeof(RBTNode));
    NIL->key = 0;
    NIL->color = 1;
    NIL->lchild = NIL->rchild = NIL;
}

RBTNode *init(int key) {
    RBTNode *q = (RBTNode *)malloc(sizeof(RBTNode));
    q->key = key;
    q->color = 0;
    q->lchild = q->rchild = NIL;
    return q;
}

RBTNode *left_rotate(RBTNode *root) {
    RBTNode *temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    return temp;
}

RBTNode *right_rotate(RBTNode *root) {
    RBTNode *temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    return temp;
}

int has_red_child(RBTNode *root) {
    return root->lchild->color == 0 || root->rchild->color == 0;
}

RBTNode *preacessor(RBTNode *root) {
    RBTNode *temp = root->lchild;
    while (temp->rchild != NIL) temp = temp->rchild;
    return temp;
}

void  clear(RBTNode *root) {
    if (root == NIL) return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}