红黑树

定义：是平衡搜索树的一种，可以保证最坏情况下基本动态集合操作的时间复杂度为O(lgn)

性质：

1.每个结点是红色的，或是黑色的

2.根结点是黑色的

3.每个叶结点是黑色的

4.如果一个结点是红色的，则他的两个子结点都是黑色的

5.对每个结点，从该结点到其所有后代页结点的简单路径上，均包含数目相同的黑色节点

---

黑高：从某个结点x出发(不包含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数

---

旋转

typedef struct node {
    node *left;
    int key;
    node *right 
    node *parent;
    char color[21]
} *NODE;

void left_rotate(NODE T, NODE x) { //左旋转
    NODE y = x->right;
    x->right = y->left; 
    if(y->left != NULL) { 
        y->left->parent = x;
    }
    y->parent = x->parent;
    if(y->parent == NULL) { //判断x是否为根节点
        T = y;
    }
    else if(x->parent->right == x) { 
        x->parent->right = y;
    }
    else {
        x->parent->left = y;
    }
    x->parent = y;
    y->left = x;
}


void right_rotate(NODE T, NODE x) { //右旋转
    NODE y = x->left;
    x->left = y->right; 
    if(y->right != NULL) { 
        y->right->parent = x;
    }
    y->parent = x->parent;
    if(y->parent == NULL) { //判断x是否为根节点
        T = y;
    }
    else if(x->parent->right == x) { 
        x->parent->right = y;
    }
    else {
        x->parent->left = y;
    }
    x->parent = y;
    y->right = x;
}

---

插入

typedef struct node {
    node *left;
    int key;
    node *right 
    node *parent;
    char color[21]
} *NODE;

void RB_insert_fixup(T, z) {
    while(strcmp(z->parent->color,RED) == 0) { //判断z的父亲结点是否等于RED，因为z为RED，所以若z的父亲结点为RED，则不符合红黑树的性质
        if(z->parent->parent->left == z->parent) { // 左孙子

            NODE y = z->parent->parent->right; //z的叔
            if(y->color == RED) { //z的叔为红色
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }else if(z->parent->right == z){ //z的叔为黑色，且z是右孩子，将z旋转成左孩子
                z = z->parent;
                left_rotate(T, z);
            }
            z->parent->color = BLACK;
            z->parent->parent->color = RED;
            right_rotate(T, z->parent->parent);

        }else { //右孙子

            NODE y = z->parent->parent->left;
            if(y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }else if(z->parent->left == z){
                z = z->parent;
                right_rotate(T, z);
            }
            z->parent->color = BLACK;
            z->parent->parent->color = RED;
            left_rotate(T, z->parent->parent);

        }
    }
    T->color = BLACK;
}

RB_insert(NODE T, NODE z) {
    NODE x = T, y = NULL;
    while(x != NULL) {
        y = x;
        if(z->key < x->key) {
            x = x->left;
        }else {
            x = x->right;
        }
    }
    z->parent = y;
    if(y == NULL) {
        T = z;
    }else if(z->key < y->key) {
        y->left = z;
    }else {
        y->right = z;
    }
    z->color = RED;
    RB_insert_fixup(T, z);
}

删除

在删除后的调整中，针对删除黑色节点，所在子树缺少一个节点，需要进行弥补或者对别人造成一个黑色节点的伤害。具体调整方法取决于兄弟节点所在子树的情况。

红黑树的插入、删除在树形数据结构中算比较复杂的，理解起来比较难，但只要记住，红黑树有其特殊的平衡规则，而我们为了维持平衡，根据邻树的状况进行旋转或者涂色。