整理笔记[红黑树]

红黑树的其实就是加了操作的AVL树，这一类的树形结构，主要区别就是调整维护，删除维护的策略不同。

因为红黑树的情况是高度对称的，那么所有的情况都能压缩一半。

插入操作

插入简单，主要难点在于插入操作的维护，插入操作需要维护的是什么呢？
站在插入点的祖父点看，插入点和插入点的父亲都是红色，这个时候就需要盘它。

插入情况

你插入点在４，５，６，７。并且他爹是红色（８种情况）。那就盘（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;
}

删除操作：

删除的策略：为了调整和少操作，在删除点以后，不管这给点是什么颜色，直接把删除点的颜色叠加到他爹的点上，这样他爹的颜色就是１，２，这两种，然后需要维护的是颜色出现有２的情况。

删除的时候分为三种大情况：
１．删除点的度为２
２．删除点的度为１
３．删除点的度为０

删除度２，１，０：找前驱或者后继，交换值，删掉前驱后继
因为是一层一层下去的，递归回去的时候一层一层的维护。

删除的维护：

删除的情况

这个时候的关键点是双重黑点的兄弟点，１和４点爱是什么颜色就是什么颜色，因为不影响所以不确定。

1.双重黑的２点的兄弟点是红色（如图此时是３点），那么来一个以双重黑２点的父亲为根节点（此时是１)开始的右旋，调整后让３为根节点，３点改成黑色，然后这个时候２点的父亲是１点，在１点看，看１点的左儿子（２点的兄弟）是不是黑色，不是就继续调整，直到进入第２步。

2.双重黑的２点的兄弟点是黑色（如图此时是３点）：

• 双重黑点（根节点左儿子）的兄弟节点右儿子（根节点右儿子的右儿子）的（３点的右儿子）是黑色，那么以３点右旋，４点成为３的父亲，３点变成红色，双重黑的父亲左旋，４变成根节点，４点颜色变成双重黑父亲颜色，双重黑父亲颜色变成黑色，双重黑颜色减去一层
• 双重黑点（根节点左儿子）的兄弟节点右儿子（根节点右儿子的右儿子）的（３点的右儿子）是红色，那么以３点父亲为root，左旋３点成为根节点，３点颜色变成双重黑父亲颜色，双重黑父亲颜色变成黑色，双重黑颜色减去一层

删除与删除调整操作:

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 ;
}