红黑树

今天复习一下红黑树。

• 什么是红黑树
• 红黑树的插入
• 红黑树的删除
• 红黑树代码实现

什么是红黑树

红黑树本质上是一棵自平衡的二叉查找树（BST），其时间复杂度为$O(\log n)$）。红黑树之所以能够自动保持平衡，是因为它给每个节点都涂上了红色或者黑色。并且所有节点必须遵循以下五点规则（满足二叉树的条件：左子树 <= 根节点 <= 右子树 的基础上）：

1. 节点非红即黑：每个节点，要么是红色的，要么是黑色的。
2. 根节点永远是黑色：最顶端的根节点必须是黑色的。
3. 叶子节点都是黑色：树最底端的那些看不见的空节点（null），都算作黑色。
4. 红节点不相邻：红色节点的儿子和父亲绝对不能是红色，也就是不允许有连续的红色。
5. 黑高相等：从任意一个节点出发，走到它最下面的任何一个最底端的叶子节点，路径上的黑色节点数量必须完全相同，这是最主要的。

记忆口诀：左根右、根叶黑、不红红、黑路同。

如何保持平衡

当新增数据时，新数据默认都是红色的。（因为红节点不会破坏黑高相等）。

但如果新节点的父节点也是红色的，那就违反了红节点不相连的规范，这时候红黑树就会启动自动化防御机制，组合使用以下两招：

• 第一招：变色

  如果发现红红相连，节点吗就会互相商量交换颜色（红变黑，黑变红），把红色往树的上方堆，直到不冲突为止

• 第二招：旋转

  如果光靠变色解决不了，那就说明二叉树长歪了，此时就需要通过旋转（左旋、右旋）来改变书的局部结构（父节点变成子节点的儿子、子节点变成父节点的父亲），此时就可以把二叉树提平。

红黑树比较难理解的地方就是插入、删除。

红黑树的插入

核心原则：先斩后奏，看叔叔眼(颜)色行事。

红黑树插入可以参考如下流程图：

大体上，红黑树的数据插入有两个阶段：普通二叉查找树（BST）的插入阶段，以及红黑树的自平衡调整阶段。

阶段一：标准BST插入

1. 按大小寻找位置：从根节点开始，比当前节点小九往左走，比当前节点大就往右走，直到找到一个空位(null)。
2. 默认染成红色：将新节点安插在这个空位上后，默认设置为红色。
   • 默认红色的原因：如果染成黑色，会直接破坏每条路径高黑相等的硬性规定，不容易修复。如果是红色，只会违反不红红，更容易修复。
3. 特例处理：如果树是空的，那么新节点就是根节点，并且直接设置为黑色，插入数据结束。

阶段二：自平衡调整

如果新节点（假设X）的父亲P是黑色的，那就直接插入数据。

如果父亲P是红色的，就违反了不红红的规定。因为父亲P是红色的，那么爷爷节点就一定存在并且是黑色的，此时调整的核心就是看叔叔节点U的颜色，有以下三种情况：

情况1：叔叔U是红色的（口诀：叔叔富裕，变色升级）

• 状态：父亲是红的，叔叔也是红的
• 解决方案： 只变色，不旋转。
  • 把父亲P和叔叔U都染成黑色（把黑色下发给儿子）
  • 把爷爷G染成红色（把红色上提到爷爷）
• 后续：因为爷爷变红了，可能会和曾爷爷出现红色冲突,所以，把当前节点X执行爷爷G，把爷爷当作新插入的节点，继续向上循环检查。

情况2：叔叔U是黑色的，且新节点X与父亲、爷爷呈折线关系（拐弯抹角，拉直再说：把LR转换为LL，把RL转换为RR）

• 状态：叔叔是黑色的（或者是空节点），并且如果父亲是爷爷的左孩子，新节点确实父亲的右孩子，或者反过来。
• 解决方案： 通过一次局部旋转，把折线拉直。
  • 如果是左亲右子的拐角，就对父亲P做一次左旋。
• 后续：旋转后，原父亲变成了新节点的儿子，此时结构贝拉之，直接变成情况3处理。

情况3：叔叔U是黑色的，且新节点X与父亲、爷爷呈直线关系（LL、RR）

• 状态： 叔叔是黑色的，并且父亲的爷爷的左孩子，新节点也是父亲的左孩子
• 解决方案：先变色，再旋转
  • 把父亲P染成黑色 （辈分上升）
  • 把爷爷G染成红色 （辈分下降）
  • 对爷爷G进行一次右旋（父亲变爷爷节点的父节点，爷爷节点变父亲的儿子节点【好乱】）
• 后续：此时结构完美平衡。

对于右边的孩子，和左边反着来就行。

最后，不管如何，根节点一定要是黑色的。

红黑树的删除

红黑树的删除是最难理解的部分，不过理解它的核心秘诀就是：先按照BST删除流程，一旦删了黑色，就通过【多出来的黑色】看兄弟脸色来处理 。

阶段一：按照BST删除

删除的第一步，不考虑颜色，先按普通二叉查找树BST的规则，找i到目标节点并删除：

1. 寻找替代节点：
   • 如果被删节点没有子节点：直接删除。
   • 如果被删节点只有一个子节点：让这个子节点直接顶替它的位置。
   • 如果被删除节点有两个子节点：先找到它右子树里面最小的节点（后继节点），把后继节点的值复制到目标节点上，然后变成删除那个后继节点（后继节点一定没有左子树）
2. 记录丢失的颜色： 真正断开链接或移走的那个节点，假设她原本的颜色是originalColor。
3. 判断是否需要调整：
   • 如果originalColor == RED： 直接结束，因为红节点不影响黑高，删了它也不会引发连续红节点。
   • 如果originalColor == BLACK：此时少了一个黑色节点，违反了每天路径黑高相等，需要做出调整。

阶段二：自平衡修复

当一个黑色节点被删掉后，相当于被删掉的黑色节点，覆盖了顶替它的子节点的颜色，此时X节点就成了双黑。此时就需要通过变色和旋转，把覆盖在X上的黑色处理掉。，修复的时候，就需要紧紧盯着X的兄弟节点S的联系，一共有4种情况（假设X是左孩子）：

情况1：兄弟S是红色的（长辈顶包）

• 状态：兄弟S是红色的（此时父亲必然是黑色的，兄弟的孩子也必然是黑色的）。
• 解决方案： 通过旋转，换一个黑色的兄弟给X
  • 把兄弟S设置为黑色，父亲设置为红色
  • 对父亲进行一次左旋。
• 后续：树结构变了，X有了一个全新的黑色兄弟，局面转化为了情况2、3、4。

情况2：兄弟S是黑色的，且它的两个孩子也都是黑色的

• 状态： 兄弟是黑的，侄子们也是黑色的。
• 解决方案： 都卸下一层黑色，让父节点去处理。
  • 把兄弟S染成红色（兄弟路径少了一个黑）
  • 把X身上多余的黑色向上剥离给父亲，让X = X.parent
• 后续：
  • 如果父亲原来是红色的，那父亲直接变成红黑节点，直接把它染成黑色。
  • 如果夫妻原来是黑色的，那父亲就成了新的双黑，继续网速循环即可。

情况3：兄弟S是黑色的，近侄子是红色的，远侄子是黑色的（拐角拉直）

• 状态：兄弟S是黑色的，近侄子（右兄弟的左孩子，靠近X的那一边）是红色的，远侄子是黑色的。
• 解决方案：通过旋转拉成直线
  • 把兄弟S设置为红色，近侄子染成黑色。
  • 对兄弟S进行一次右旋。
• 后续：此时红色的侄子被转到了外侧，结构拉直，直接变成情况4。

情况4：兄弟S是黑色的，远侄子是红色的

• 状态：兄弟是黑的。远侄子（右兄弟的右孩子，即远离X的那一边）是红色的（近侄子红黑都行），比较完美的位置。
• 解决方案：从兄弟家借一个黑色过来，彻底消灭双黑。
  • 把兄弟S染成父亲的颜色
  • 把父亲染成黑色，把远侄子也染成黑色。
  • 对父亲进行一次左旋。
• 后续：经过调整，X身上多余的黑色被完美抵消。把X直接指向根节点root，修复完成。

补充总结，可按照下面的方式去判断。

├─ 有左右子树，直接后继替代它，删除直接后继
├─ 只有一个子节点（左子节点或者右子节点），子节点代替它后变黑
└─ 没有子节点，查看节点颜色
   ├─ 节点是红色，直接删除。
   └─ 节点是黑色，删除变双黑，查看双黑的兄弟颜色
      ├─  兄弟是黑色： 查看兄弟孩子颜色
      |	├─ 兄弟孩子全黑色： 兄弟染红，双黑上移（继续消除双黑） 双黑遇到红色或根节点变单黑
      |	└─ 兄弟孩子有红色：变色，旋转（双黑变单黑）
      |		├─ LL: 红子变兄，兄变父，父变黑，父右旋
      |		├─ RR: 红子变兄，兄变父，父变黑，父左旋
      |		├─ LR: 红子变父，父变黑，先左旋再右旋
      |		└─ RL：红子变父，父变黑，先右旋再左旋
      └─ 兄弟是红色：兄父换色，向双黑方向旋转（保持双黑不变，继续调整）

代码实现

JavaGoPython

package cn.net.dev.tree;

public class RedBlackTree<K extends Comparable<K>, V> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    private class Node {
        K key;
        V value;
        Node left, right, parent;
        // 新增节点默认是红色
        boolean color = RED;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 左旋 把当前节点变成它右子节点的左子节点
    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;  // 将Y的左子树挂到X的右边
        if (y.left != null) {
            y.left.parent = x;
        }

        y.parent = x.parent;
        // 将y接替X的位置
        if (x.parent == null) {
            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) {
        // 1. 拿到y的左孩子 x (x即将要升辈分当爸爸)
        Node x = y.left;
        // 2.[核心改动 1] 把 x的右子树，挪给y当左子树
        // 因为x 变成 y 的爸爸后， x的右子树没地方放了，而y的左边刚好空出来了
        y.left = x.right;
        // 3. 如果 x 的 右子树不是空的，得告诉右子树： 以后y就是你爸爸了
        if (x.right != null) {
            x.right.parent = y;
        }
        // 4. [核心改动 2] x要顶替 y得位置，所以 x得新爸爸就是y原来的爸爸
        x.parent = y.parent;
        // 5. 得高速y得爸爸（也就是爷爷），他儿子换人了
        if (y.parent == null) {
            // 如果y原来就是根节点，那就现在 x就是新的根节点了
            root = x;
        } else if (y == y.parent.right) {
            // 如果y原来是右孩子，现在爷爷得右孩子变成x
            y.parent.right = x;
        } else {
            // 如果y原来是左孩子，现在爷爷的左孩子变成x
            y.parent.left = x;
        }
        // 6 [核心改动 3] x 真正当上了y得爸爸，y变成了x的右孩子
        x.right = y;
        // 7. 赶紧让y 认新爹 x
        y.parent = x;
    }

    public void insert(K key, V value) {
        Node node = new Node(key, value);
        if (root == null) {
            root = node;
            root.color = BLACK;
            return;
        }

        Node parent = null;
        Node current = root;
        while (current != null) {
            parent = current;
            int cmp = key.compareTo(current.key);
            if (cmp < 0) {
                current = current.left;
            } else if (cmp > 0) {
                current = current.right;
            } else {
                current.value = value;
                return;
            }
        }

        node.parent = parent;
        if (key.compareTo(parent.key) < 0) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        // 插入数据后，需要修复红黑树
        fixAfterInsertion(node);
    }

    private void fixAfterInsertion(Node x) {
        // 只有当父节点时红色时，才需要调整
        while (x != null && x != root && x.parent.color == RED) {

            // 父亲是爷爷的左孩子
            if (x.parent == x.parent.parent.left) {
                Node uncle = x.parent.parent.right;
                // 情况1 ，叔叔是红色 LLM
                if (uncle != null && uncle.color == RED) {
                    x.parent.color = BLACK;
                    uncle.color = BLACK;
                    x.parent.parent.color = RED;
                    x = x.parent.parent;
                } else {
                    // 情况2： 当前节点是右孩子（拐角），先左旋
                    if (x == x.parent.right) {
                        x = x.parent;
                        leftRotate(x);
                    }

                    //情况3，变色并右旋
                    x.parent.color = BLACK;
                    x.parent.parent.color = RED;
                    rightRotate(x.parent.parent);
                }
            } else {
                // 父亲是爷爷的右孩子（完全对称）
                Node uncle = x.parent.parent.left;
                if (uncle != null && uncle.color == RED) {
                    x.parent.color = BLACK;
                    uncle.color = BLACK;
                    x.parent.parent.color = RED;
                    x = x.parent.parent;
                } else {
                    if (x == x.parent.left) {
                        x = x.parent;
                        rightRotate(x);
                    }

                    x.parent.color = BLACK;
                    x.parent.parent.color = RED;
                    leftRotate(x.parent.parent);
                }
            }
        }
        // 确认根节点是黑色
        root.color = BLACK;
    }

    public void delete(K key) {
        Node node = findNode(root, key);
        if (node == null) return;

        Node x; // 顶替 node 的节点
        Node y = node; // 真正被断开连接的节点
        boolean originalColor = y.color;

        if (node.left == null) {
            x = node.right;
            transplant(node, node.right);
        } else if (node.right == null) {
            x = node.left;
            transplant(node, node.left);
        } else {
            // 左右子树都在，找后继节点（右子树里最小的）
            y = minimum(node.right);
            originalColor = y.color;
            x = y.right;
            if (y.parent == node) {
                if (x != null) x.parent = y;
            } else {
                transplant(y, y.right);
                y.right = node.right;
                y.right.parent = y;
            }
            transplant(node, y);
            y.left = node.left;
            y.left.parent = y;
            y.color = node.color;
        }

        // 关键：如果真正被删掉的节点 y 是黑色的，必须修复平衡
        if (originalColor == BLACK) {
            fixAfterDeletion(x);
        }
    }

    // 辅助方法：用 v 替换 u 的位置
    private void transplant(Node u, Node v) {
        if (u.parent == null) root = v;
        else if (u == u.parent.left) u.parent.left = v;
        else u.parent.right = v;
        if (v != null) v.parent = u.parent;
    }

    private Node minimum(Node node) {
        while (node.left != null) node = node.left;
        return node;
    }

    private Node findNode(Node node, K key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.key);
        if (cmp < 0) return findNode(node.left, key);
        if (cmp > 0) return findNode(node.right, key);
        return node;
    }

    private void fixAfterDeletion(Node x) {
        // 只要 x 不是根节点，且它背负着“双黑”（颜色为黑色），就要一直调整
        while (x != root && (x == null || x.color == BLACK)) {
            if (x == x.parent.left) { // x 是左孩子
                Node sibling = x.parent.right; // 兄弟节点

                // 情况 1：兄弟是红色的
                if (sibling.color == RED) {
                    sibling.color = BLACK;
                    x.parent.color = RED;
                    leftRotate(x.parent);
                    sibling = x.parent.right; // 更新最新的兄弟
                }

                // 情况 2：兄弟是黑色的，且两个侄子也是黑色的
                if ((sibling.left == null || sibling.left.color == BLACK) &&
                        (sibling.right == null || sibling.right.color == BLACK)) {
                    sibling.color = RED; // 兄弟变红
                    x = x.parent;        // 双黑转移给父亲
                } else {
                    // 情况 3：兄弟是黑色的，右侄子是黑色（左侄子是红色）
                    if (sibling.right == null || sibling.right.color == BLACK) {
                        if (sibling.left != null) sibling.left.color = BLACK;
                        sibling.color = RED;
                        rightRotate(sibling);
                        sibling = x.parent.right;
                    }
                    // 情况 4：兄弟是黑色的，右侄子是红色
                    sibling.color = x.parent.color;
                    x.parent.color = BLACK;
                    if (sibling.right != null) sibling.right.color = BLACK;
                    leftRotate(x.parent);
                    x = root; // 修复完毕，退出循环
                }
            } else { // x 是右孩子（完全对称）
                Node sibling = x.parent.left;
                if (sibling.color == RED) {
                    sibling.color = BLACK;
                    x.parent.color = RED;
                    rightRotate(x.parent);
                    sibling = x.parent.left;
                }
                if ((sibling.left == null || sibling.left.color == BLACK) &&
                        (sibling.right == null || sibling.right.color == BLACK)) {
                    sibling.color = RED;
                    x = x.parent;
                } else {
                    if (sibling.left == null || sibling.left.color == BLACK) {
                        if (sibling.right != null) sibling.right.color = BLACK;
                        sibling.color = RED;
                        leftRotate(sibling);
                        sibling = x.parent.left;
                    }
                    sibling.color = x.parent.color;
                    x.parent.color = BLACK;
                    if (sibling.left != null) sibling.left.color = BLACK;
                    rightRotate(x.parent);
                    x = root;
                }
            }
        }
        if (x != null) x.color = BLACK; // 确保最终节点或根节点为黑色
    }

    public void printTree() {
        printTree(root, "", true);
    }

    public void printTree(Node node, String indent, boolean last) {
        System.out.print(indent);
        if (last) {
            System.out.print("└─ ");
            indent += "   ";
        } else {
            System.out.print("├─ ");
            indent += "│  ";
        }

        if (node == null) {
            System.out.println("NIL(B)");
            return;
        }

        String colorStr = node.color == RED ? "\u001B[31m(R)\u001B[0m" : "(B)";
        System.out.println(node.key + colorStr);

        printTree(node.left, indent, false);
        printTree(node.right, indent, true);
    }
}

// 研究中。。。

"""
研究中。。。
"""