第二讲：红黑树与 B+ 树¶

enum Color { RED, BLACK };

struct Node {
    int key;
    Color color = RED;
    Node *left = nullptr, *right = nullptr, *parent = nullptr;
};

bool isRed(Node *x) { return x && x->color == RED; }

void rotateLeft(Node *&root, Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    y->parent = x->parent;
    if (!x->parent)
        root = y;
    else if (x->parent->left == x)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

void rotateRight(Node *&root, Node *x) {
    Node *y = x->left;
    x->left = y->right;
    if (y->right) y->right->parent = x;
    y->parent = x->parent;
    if (!x->parent)
        root = y;
    else if (x->parent->left == x)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->right = x;
    x->parent = y;
}

// 对应 1.3 的三种情况，z 是新插入的红节点
void insertFixup(Node *&root, Node *z) {
    while (isRed(z->parent)) {
        Node *p = z->parent, *g = p->parent;
        if (p == g->left) {
            Node *u = g->right;
            if (isRed(u)) {                       // 情况 1：叔叔是红的
                p->color = BLACK;
                u->color = BLACK;
                g->color = RED;
                z = g;
            } else {
                if (z == p->right) {              // 情况 2：先把它转成外侧
                    z = p;
                    rotateLeft(root, z);
                    p = z->parent;
                }
                p->color = BLACK;                 // 情况 3
                g->color = RED;
                rotateRight(root, g);
            }
        } else {                                  // 镜像
            Node *u = g->left;
            if (isRed(u)) {
                p->color = BLACK;
                u->color = BLACK;
                g->color = RED;
                z = g;
            } else {
                if (z == p->left) {
                    z = p;
                    rotateRight(root, z);
                    p = z->parent;
                }
                p->color = BLACK;
                g->color = RED;
                rotateLeft(root, g);
            }
        }
    }
    root->color = BLACK;
}

void insert(Node *&root, int key) {
    Node *parent = nullptr, *cur = root;
    while (cur) {
        if (key == cur->key) return;              // 重复键不插
        parent = cur;
        cur = (key < cur->key) ? cur->left : cur->right;
    }
    Node *z = new Node{key};
    z->parent = parent;
    if (!parent)
        root = z;
    else if (key < parent->key)
        parent->left = z;
    else
        parent->right = z;
    insertFixup(root, z);
}

bool isBlack(Node *x) { return !isRed(x); }              // NIL 也算黑
bool onLeft(Node *x, Node *p) { return p->left == x; }
Node *sibling(Node *x, Node *p) { return onLeft(x, p) ? p->right : p->left; }
Node *innerChild(Node *x, Node *p) {
    Node *w = sibling(x, p);
    return onLeft(x, p) ? w->left : w->right;
}
Node *outerChild(Node *x, Node *p) {
    Node *w = sibling(x, p);
    return onLeft(x, p) ? w->right : w->left;
}

// 情况 1：兄弟 w 是红的。w 染黑、p 染红，绕 p 旋转，把问题变成情况 2、3 或 4
void deleteCase1(Node *&root, Node *x, Node *p) {
    Node *w = sibling(x, p);
    w->color = BLACK;
    p->color = RED;
    if (onLeft(x, p))
        rotateLeft(root, p);
    else
        rotateRight(root, p);
}

// 情况 2：兄弟 w 黑，且 w 的两个孩子都是黑的。w 染红，多出来的一重黑上移给 p
void deleteCase2(Node *x, Node *p) { sibling(x, p)->color = RED; }

// 情况 3：兄弟 w 黑，内侧孩子红、外侧孩子黑。先把内侧的红孩子转到外侧，变成情况 4
void deleteCase3(Node *&root, Node *x, Node *p) {
    Node *w = sibling(x, p), *c = innerChild(x, p);
    c->color = BLACK;
    w->color = RED;
    if (onLeft(x, p))
        rotateRight(root, w);
    else
        rotateLeft(root, w);
}

// 情况 4：兄弟 w 黑，外侧孩子 d 是红的。绕 p 旋转让 w 顶上来，重新分配颜色，修复结束
void deleteCase4(Node *&root, Node *x, Node *p) {
    Node *w = sibling(x, p), *d = outerChild(x, p);
    w->color = p->color;
    p->color = BLACK;
    d->color = BLACK;
    if (onLeft(x, p))
        rotateLeft(root, p);
    else
        rotateRight(root, p);
}

// x 是带了一重额外黑的节点（可能是 nullptr），p 是它的父节点
void deleteFixup(Node *&root, Node *x, Node *p) {
    while (x != root && isBlack(x)) {
        Node *w = sibling(x, p);
        if (isRed(w)) {                                      // 情况 1
            deleteCase1(root, x, p);
            w = sibling(x, p);                               // 兄弟换人了，重新取
        }
        if (isBlack(w->left) && isBlack(w->right)) {          // 情况 2
            deleteCase2(x, p);
            x = p;                                           // 额外的一重黑上移，继续往上
            p = x->parent;
        } else {
            if (isBlack(outerChild(x, p)))                    // 情况 3
                deleteCase3(root, x, p);
            deleteCase4(root, x, p);                          // 情况 4，修复结束
            return;
        }
    }
    if (x) x->color = BLACK;                                  // 根节点或者红节点，直接染黑
}

Node *minimum(Node *x) {
    while (x->left) x = x->left;
    return x;
}

// 用 v 顶替 u 的位置，v 可以是 nullptr
void transplant(Node *&root, Node *u, Node *v) {
    if (!u->parent)
        root = v;
    else if (u->parent->left == u)
        u->parent->left = v;
    else
        u->parent->right = v;
    if (v) v->parent = u->parent;
}

bool erase(Node *&root, int key) {
    Node *z = root;
    while (z && z->key != key) z = (key < z->key) ? z->left : z->right;
    if (!z) return false;

    Node *x = nullptr, *p = nullptr;      // 顶替上来的节点和它的父节点
    Color gone = z->color;                // 真正离开这棵树的节点的颜色
    if (!z->left) {
        x = z->right;
        p = z->parent;
        transplant(root, z, z->right);
    } else if (!z->right) {
        x = z->left;
        p = z->parent;
        transplant(root, z, z->left);
    } else {
        Node *y = minimum(z->right);      // 用后继顶替
        gone = y->color;
        x = y->right;
        if (y->parent == z) {
            p = y;
        } else {
            p = y->parent;
            transplant(root, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(root, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    if (gone == BLACK) {
        if (isRed(x))
            x->color = BLACK;             // 顶上来的是红节点，直接染黑就补上了
        else
            deleteFixup(root, x, p);
    }
    delete z;
    return true;
}

Btree Insert(ElementType X, Btree T)
{
    从根往下找到 X 应该落在的叶子；
    把 X 插进这个叶子；
    while (这个节点超过上限) {
        // 叶子最多 M 个 key；内部节点最多 M-1 个 key（M 个孩子）
        把节点分裂成左右两半，再把中间那个 key 交给父节点：
          叶子有 M+1 个 key 时，一半 ⌈(M+1)/2⌉ 个，一半 ⌊(M+1)/2⌋ 个；
          内部节点有 M 个 key 时，中间那个提上去，两边各留一半；
        如果分裂的是根，新建一个根，让两个孩子指向分裂出来的两个节点；
        把提上去的 key 插进父节点，继续向上检查；
    }
}