红黑树 插入、删除调整

红黑树的平衡条件

1. 每个节点非黑即红
2. 根节点是黑色
3. 叶节点（NIL）是黑色
4. 如果一个节点是红色，则它的两个子节点都是黑色的
5. 从根节点出发到所有叶节点路径上，黑色节点的数量相同

红黑树的特性

1. 最长路径是最短路径的2倍
2. NIL节点对于删除操作很重要
3. 新插入的节点是红色的

平衡调整法门

• 插入调整站在祖父节点看
• 删除调整站在父节点看
• 插入调整的情况处理一共2种
• 删除调整的情况处理一共4种

插入调整的原则

调整前后，保持路径上黑色节点的数量相同。

---

操作：祖父节点变为红色，父节点和uncle节点变为黑色

插入调整情况二：

LL类型的失衡：左子树是红色 左子树的左子树也是红色

• 大右旋
• 将祖父节点和两个父节点调整为红-黑-黑（红色上浮） or 黑-红-红（红色下沉）

LR类型的失衡：左子树是红色 左子树的右子树也是红色

• 小左旋
• 变为LL类型的失衡

RR类型的失衡：右子树是红色 右子树的右子树也是红色

• 大左旋
• 红色上浮 or 红色下沉

RL类型的失衡：右子树是红色 右子树的左子树也是红色

• 小右旋
• 变为RR类型的失衡

---

删除什么样的节点会导致红黑树失衡？

• 删除度为2的节点 可以转换为删除度为0的节点（删除前驱或后继节点 并替换根节点的值）
• 删除度为0的红色节点：不会失衡，黑色节点数量不变。
• 删除度为1的红色节点：红黑树中不存在度为1的红色节点，子节点不能为红，如果子节点为黑并只有一个，则红黑树失衡。
• 删除度为0的黑色节点：失衡，删除后的位置为NIL（双重黑）
• 删除度为1的黑色节点：不会失衡，删除后 红色子节点变黑即可（度为1的黑色节点 其子节点必然为红色 且红色下面再无子树）

删除调整情况一：

操作：

• 当前节点（95）变为黑色（-1）
• 兄弟节点（9）变为红色（-1）
• 父节点（43）变为双重黑（+1）

删除调整情况二：

RR类型 / LL类型的失衡：

• 抓着父节点（38）左旋 / 右旋
• 当前节点（28）【双重黑】改为黑色
• 父节点（38）【可能红 可能黑】改为黑色（旋转后的两个子节点改为黑色）
• borther节点的同测子节点（72）【红色】改为黑色（旋转后的两个子节点改为黑色）
• borther节点（51）【黑色】改为原根节点（38）的颜色【可能红 可能黑】

删除调整情况三：

RL类型 / LR类型的失衡：

• 抓着brother节点小右旋 / 小左旋
• brother【黑色】变为红色
• brother异侧的失衡子节点【红色】变为黑色
• 转换为RR / LL 类型的失衡

删除调整情况四：

brother节点为红色节点：

• 大左旋 / 大右旋
• 原根节点【黑色】改为红色
• brother节点【红色】改为黑色
• 转换为双重黑的兄弟节点是黑色的情况，判断其为“情况一/二/三”中的哪一种，再递归的进行处理

---

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

#define NIL &(node::__NIL)
struct node {
    node(int key = 0, int color = 0, node *lchild = NIL, node *rchild = NIL)
    : key(key), color(color), lchild(lchild), rchild(rchild) {}
    int key;
    int color; // 0 red, 1 black, 2 double black
    node *lchild, *rchild;
    static node __NIL;
};

node node::__NIL(0, 1);

node *getNewNode(int key) {
    return new node(key);
}

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

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

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

node *insert_maintain(node *root) {
    int flag = 0;
    if (root->lchild->color == 0 && has_red_child(root->lchild)) flag = 1;
    if (root->rchild->color == 0 && has_red_child(root->rchild)) flag = 2;
    if (flag == 0) return root;
    if (root->lchild->color == 0 && root->rchild->color == 0) {
        root->color = 0;
        root->lchild->color = root->rchild->color = 1;
        return root;
    }
    if (flag == 1) {
        if (root->lchild->rchild->color == 0) {
            root->lchild = left_rotate(root->lchild);
        }
        root = right_rotate(root);
    } else {
        if (root->rchild->lchild->color == 0) {
            root->rchild = right_rotate(root->rchild);
        }
        root = left_rotate(root);
    }
    root->color = 0;
    root->lchild->color = root->rchild->color = 1;
    return root;
}

node *__insert(node *root, int key) {
    if (root == NIL) return getNewNode(key);
    if (key == root->key) return root;
    if (key < root->key) {
        root->lchild = __insert(root->lchild, key);
    } else {
        root->rchild = __insert(root->rchild, key);
    }
    return insert_maintain(root);
}

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

node *erase_maintain(node *root) {
    if (root->lchild->color != 2 && root->rchild->color != 2) return root;
    // 情况四
    int flag = 0;
    if (has_red_child(root)) {
        root->color = 0;
        if (root->lchild->color == 0) {
            root = right_rotate(root); flag = 1;
        } else {
            root = left_rotate(root); flag = 2;
        }
        root->color = 1;
        if (flag == 1) root->rchild = erase_maintain(root->rchild);
        else root->lchild = erase_maintain(root->lchild);
        return root;
    }
    // 情况一
    if ((root->lchild->color == 1 && !has_red_child(root->lchild))
        || (root->rchild->color == 1 && !has_red_child(root->rchild))) {
        root->lchild->color -= 1;
        root->rchild->color -= 1;
        root->color += 1;
        return root;
    }
    // 情况二/三
    if (root->lchild->color == 1) {
        // L*
        root->rchild->color = 1; // 双重黑改为黑
        if (root->lchild->lchild->color != 0) {
            // LR
            root->lchild->color = 0;
            root->lchild = left_rotate(root->lchild);// 左旋
            root->lchild->color = 1;
        }
        // LL
        root->lchild->color = root->color; // borther改为root颜色
        root = right_rotate(root);
    } else {
        // R*
        root->lchild->color = 1; // 双重黑改为黑
        if (root->rchild->rchild->color != 0) {
            // RL
            root->rchild->color = 0;
            root->rchild = right_rotate(root->lchild);
            root->rchild->color = 1;
        }
        // RR
        root->rchild->color = root->color; // borther改为root颜色
        root = left_rotate(root);
    }
    root->lchild->color = root->rchild->color = 1; // 旋转后的左右子节点为黑色
    return root;
}

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

node *__erase(node *root, int key) {
    if (root == NIL) return root;
    if (key < root->key) {
        root->lchild = __erase(root->lchild, key);
    } else if (key > root->key) {
        root->rchild = __erase(root->rchild, key);
    } else {
        if (root->lchild == NIL || root->rchild == NIL) {
            node *temp = root->lchild == NIL ? root->rchild : root->lchild;
            temp->color += root->color;
            delete root;
            return temp;
        } else {
            node *temp = predecessor(root);
            root->key = temp->key;
            root->lchild = __erase(root->lchild, temp->key);
        }
    }
    return erase_maintain(root);
}

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

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