红黑树：自平衡二叉搜索树的工程实现

enum Color { RED, BLACK }

class Node {
    int key;
    Color color = Color.RED;   // 新节点默认红色
    Node left, right, parent;

    Node(int key) { this.key = key; }
}

public class RBTree {
    private Node root;
    private final Node NIL = new Node(0);   // 哨兵
    { NIL.color = Color.BLACK; }

    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != NIL) y.left.parent = x;
        y.parent = x.parent;
        if (x.parent == NIL) root = y;
        else if (x == x.parent.left) x.parent.left = y;
        else x.parent.right = y;
        y.left = x;
        x.parent = y;
    }

    private void rightRotate(Node y) {
        Node x = y.left;
        y.left = x.right;
        if (x.right != NIL) x.right.parent = y;
        x.parent = y.parent;
        if (y.parent == NIL) root = x;
        else if (y == y.parent.right) y.parent.right = x;
        else y.parent.left = x;
        x.right = y;
        y.parent = x;
    }

    private void fixInsert(Node z) {
        while (z.parent.color == Color.RED) {
            Node gp = z.parent.parent;
            if (z.parent == gp.left) {
                Node uncle = gp.right;
                if (uncle.color == Color.RED) {        // 情况 1
                    z.parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    gp.color = Color.RED;
                    z = gp;
                } else {
                    if (z == z.parent.right) {         // 情况 2 → 转情况 3
                        z = z.parent;
                        leftRotate(z);
                    }
                    z.parent.color = Color.BLACK;       // 情况 3
                    gp.color = Color.RED;
                    rightRotate(gp);
                }
            } else { /* 对称情形：父是祖父右子 */ }
        }
        root.color = Color.BLACK;
    }

    private void fixDelete(Node x) {
        while (x != root && x.color == Color.BLACK) {
            if (x == x.parent.left) {
                Node w = x.parent.right;               // 兄弟
                if (w.color == Color.RED) {            // 情况 1
                    w.color = Color.BLACK;
                    x.parent.color = Color.RED;
                    leftRotate(x.parent);
                    w = x.parent.right;
                }
                if (w.left.color == Color.BLACK && w.right.color == Color.BLACK) {  // 情况 2
                    w.color = Color.RED;
                    x = x.parent;
                } else {
                    if (w.right.color == Color.BLACK) {  // 情况 3 → 转 4
                        w.left.color = Color.BLACK;
                        w.color = Color.RED;
                        rightRotate(w);
                        w = x.parent.right;
                    }
                    w.color = x.parent.color;             // 情况 4
                    x.parent.color = Color.BLACK;
                    w.right.color = Color.BLACK;
                    leftRotate(x.parent);
                    x = root;
                }
            } else { /* 对称情形 */ }
        }
        x.color = Color.BLACK;
    }
}