树 - 红黑树(R-B Tree)

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组，是平衡二叉树和AVL树的折中。

其实不同版本的平衡二叉查找树，最大的区别在于，维护平衡的方式不同。红黑树基于颜色变量。 AVL树基于左右子树的高度差。树堆基于节点的优先级。

提示

红黑树的讲解在JDK TreeMap&TreeSet源码解读中有详细的展示。这里再补充一些其它内容。

为什么要有红黑树

平衡二叉树(AVLTree)，了解到AVL树的性质，其实平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。 AVL树的效率就是高在这个地方。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树。为了让它重新维持在一个平衡状态，就需要对其进行旋转处理, 那么创建一颗平衡二叉树的成本其实不小. 这个时候就有人开始思考，并且提出了红黑树的理论，那么红黑树到底比AVL树好在哪里?

红黑树与AVL树的比较:

1.AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异，所以红黑树的查询效率略低与AVL的查询。
2.红黑树的插入删除比AVL树更便于控制操作，红黑树和AVL插入的速度差不多。
3.红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)，红黑树删除的速度比AVL快，因为AVL删除最多需要log(N)次旋转。

红黑树的性质: 红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK。通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。

具体性质如下:

每个结点是红的或者黑的
根结点是黑的
每个叶子结点是黑的（因为这条性质，一般用叶子结点在代码中被特殊表示）
如果一个结点是红的，则它的两个儿子都是黑的（不存在相邻红色）
从任一节点到叶子节点，所包含的黑色节点数目相同（即黑高度相同，黑色节点高度一致性）
最长路径长度不超过最短路径长度的2倍（2n-1，一条黑红黑红…一条全黑）

时间复杂度

平均和最坏情况下都是O(logn)

一颗包含n个节点的红黑树的高度最多是2倍的log(n+1)

节点的旋转算法

// 左旋操作
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.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }

    x.right = y;
    y.parent = x;
}

Java ConcurrentHashMap & TreeMap
c++ stl map,set（红黑树的封装）
linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块，进程调度cfs（用红黑树存储进程的集合，把调度的时间作为key，那么树的左下角时间就是最小的）
内存管理（每次使用malloc的时候都会分配一块小内存出来，那么这么块就是用红黑树来存，如何表述一段内存块呢，用开始地址+长度来表示，所以key->开始地址，val->大小）
epoll中使用红黑树管理socketfd
nginx中使用红黑树管理定时器，中序遍历第一个就是最小的定时器

红黑树的代码实现和实例

public class RedBlackTree {
    // 颜色常量
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    // 节点类
    private class Node {
        int key;
        Node left, right, parent;
        boolean color;

        Node(int key) {
            this.key = key;
            this.color = RED; // 新节点默认为红色
        }
    }

    private Node root;
    private Node NIL; // 哨兵节点（所有叶子节点指向它）

    public RedBlackTree() {
        NIL = new Node(0);
        NIL.color = BLACK;
        root = NIL;
    }

    // 左旋操作
    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.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }

        x.right = y;
        y.parent = x;
    }

    // 插入后修复红黑性质
    private void insertFixup(Node z) {
        while (z.parent.color == RED) {
            if (z.parent == z.parent.parent.left) {
                Node y = z.parent.parent.right; // 叔叔节点

                // 情况1：叔叔是红色
                if (y.color == RED) {
                    z.parent.color = BLACK;
                    y.color = BLACK;
                    z.parent.parent.color = RED;
                    z = z.parent.parent;
                } else {
                    // 情况2：叔叔是黑色，且z是右孩子
                    if (z == z.parent.right) {
                        z = z.parent;
                        leftRotate(z);
                    }

                    // 情况3：叔叔是黑色，且z是左孩子
                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    rightRotate(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 == z.parent.left) {
                        z = z.parent;
                        rightRotate(z);
                    }

                    z.parent.color = BLACK;
                    z.parent.parent.color = RED;
                    leftRotate(z.parent.parent);
                }
            }

            if (z == root) {
                break;
            }
        }

        root.color = BLACK; // 根节点始终为黑色
    }

    // 插入节点
    public void insert(int key) {
        Node z = new Node(key);
        Node y = NIL;
        Node x = root;

        // 找到插入位置
        while (x != NIL) {
            y = x;
            if (z.key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        z.parent = y;
        if (y == NIL) {
            root = z;
        } else if (z.key < y.key) {
            y.left = z;
        } else {
            y.right = z;
        }

        z.left = NIL;
        z.right = NIL;
        z.color = RED; // 新节点默认为红色

        insertFixup(z); // 修复红黑性质
    }

    // 查找最小节点
    private Node minimum(Node node) {
        while (node.left != NIL) {
            node = node.left;
        }
        return node;
    }

    // 替换子树
    private void transplant(Node u, Node v) {
        if (u.parent == NIL) {
            root = v;
        } else if (u == u.parent.left) {
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }
        v.parent = u.parent;
    }

    // 删除后修复红黑性质
    private void deleteFixup(Node x) {
        while (x != root && x.color == BLACK) {
            if (x == x.parent.left) {
                Node w = x.parent.right; // 兄弟节点

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

                // 情况2：兄弟是黑色，且兄弟的两个孩子都是黑色
                if (w.left.color == BLACK && w.right.color == BLACK) {
                    w.color = RED;
                    x = x.parent;
                } else {
                    // 情况3：兄弟是黑色，且兄弟的左孩子是红色，右孩子是黑色
                    if (w.right.color == BLACK) {
                        w.left.color = BLACK;
                        w.color = RED;
                        rightRotate(w);
                        w = x.parent.right;
                    }

                    // 情况4：兄弟是黑色，且兄弟的右孩子是红色
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.right.color = BLACK;
                    leftRotate(x.parent);
                    x = root;
                }
            } else {
                // 镜像对称情况
                Node w = x.parent.left;

                if (w.color == RED) {
                    w.color = BLACK;
                    x.parent.color = RED;
                    rightRotate(x.parent);
                    w = x.parent.left;
                }

                if (w.right.color == BLACK && w.left.color == BLACK) {
                    w.color = RED;
                    x = x.parent;
                } else {
                    if (w.left.color == BLACK) {
                        w.right.color = BLACK;
                        w.color = RED;
                        leftRotate(w);
                        w = x.parent.left;
                    }

                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.left.color = BLACK;
                    rightRotate(x.parent);
                    x = root;
                }
            }
        }

        x.color = BLACK;
    }

    // 删除节点
    public void delete(int key) {
        Node z = search(key);
        if (z == NIL) return; // 节点不存在

        Node y = z;
        Node x;
        boolean yOriginalColor = y.color;

        if (z.left == NIL) {
            x = z.right;
            transplant(z, z.right);
        } else if (z.right == NIL) {
            x = z.left;
            transplant(z, z.left);
        } else {
            y = minimum(z.right);
            yOriginalColor = y.color;
            x = y.right;

            if (y.parent == z) {
                x.parent = y;
            } else {
                transplant(y, y.right);
                y.right = z.right;
                y.right.parent = y;
            }

            transplant(z, y);
            y.left = z.left;
            y.left.parent = y;
            y.color = z.color;
        }

        if (yOriginalColor == BLACK) {
            deleteFixup(x);
        }
    }

    // 查找节点
    public Node search(int key) {
        Node x = root;
        while (x != NIL && key != x.key) {
            if (key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        return x;
    }

    // 中序遍历（验证树的有序性）
    public void inorderTraversal() {
        inorderHelper(root);
        System.out.println();
    }

    private void inorderHelper(Node node) {
        if (node != NIL) {
            inorderHelper(node.left);
            System.out.print(node.key + " ");
            inorderHelper(node.right);
        }
    }

    // 打印树结构（用于调试）
    public void printTree() {
        printHelper(root, "", true);
    }

    private void printHelper(Node node, String prefix, boolean isTail) {
        if (node != NIL) {
            System.out.println(prefix + (isTail ? "└── " : "├── ") + node.key + "(" + (node.color ? "RED" : "BLACK") + ")");
            printHelper(node.left, prefix + (isTail ? "    " : "│   "), false);
            printHelper(node.right, prefix + (isTail ? "    " : "│   "), true);
        }
    }

    // 测试红黑树性质
    public boolean isRedBlackTree() {
        if (root == NIL) return true;
        if (root.color == RED) return false;

        // 检查红节点的子节点是否为黑
        if (!checkRedProperty(root)) return false;

        // 检查所有路径的黑高度是否相同
        int blackHeight = -1;
        if (!checkBlackHeight(root, 0, blackHeight)) return false;

        return true;
    }

    private boolean checkRedProperty(Node node) {
        if (node == NIL) return true;

        if (node.color == RED) {
            if (node.left.color == RED || node.right.color == RED) {
                return false;
            }
        }

        return checkRedProperty(node.left) && checkRedProperty(node.right);
    }

    private boolean checkBlackHeight(Node node, int currentHeight, int expectedHeight) {
        if (node == NIL) {
            if (expectedHeight == -1) {
                expectedHeight = currentHeight;
                return true;
            }
            return currentHeight == expectedHeight;
        }

        if (node.color == BLACK) {
            currentHeight++;
        }

        return checkBlackHeight(node.left, currentHeight, expectedHeight) &&
                checkBlackHeight(node.right, currentHeight, expectedHeight);
    }

    // 主函数（测试用例）
    public static void main(String[] args) {
        RedBlackTree rbTree = new RedBlackTree();

        // 测试插入
        System.out.println("=== 测试插入 ===");
        int[] keys = {5, 3, 7, 2, 4, 6, 8, 1, 9};
        for (int key : keys) {
            rbTree.insert(key);
            System.out.println("插入 " + key + " 后：");
            rbTree.printTree();
            System.out.println("是否为红黑树: " + rbTree.isRedBlackTree());
            System.out.println();
        }

        // 测试中序遍历
        System.out.println("=== 测试中序遍历 ===");
        System.out.print("中序遍历结果: ");
        rbTree.inorderTraversal();

        // 测试删除
        System.out.println("\n=== 测试删除 ===");
        int[] deleteKeys = {3, 7, 5};
        for (int key : deleteKeys) {
            System.out.println("删除 " + key + " 前：");
            rbTree.printTree();
            rbTree.delete(key);
            System.out.println("删除 " + key + " 后：");
            rbTree.printTree();
            System.out.println("是否为红黑树: " + rbTree.isRedBlackTree());
            System.out.println();
        }

        // 测试查找
        System.out.println("=== 测试查找 ===");
        int[] searchKeys = {1, 5, 9};
        for (int key : searchKeys) {
            Node node = rbTree.search(key);
            if (node != rbTree.NIL) {
                System.out.println("找到节点 " + key + "，颜色: " + (node.color ? "RED" : "BLACK"));
            } else {
                System.out.println("未找到节点 " + key);
            }
        }
    }
}

其它参考

<@skywang12345写的红黑树实现 https://www.cnblogs.com/skywang12345/p/3245399.html <30张图带你彻底理解红黑树 https://www.cnblogs.com/kumufengchun/p/11169138.html> <浅析红黑树(RBTree)原理及实现 https://blog.csdn.net/tanrui519521/article/details/80980135> https://www.douyin.com/video/7307637407816437003 数据结构之红黑树实现（全）https://blog.csdn.net/qq_74811378/article/details/142411372 红黑树(一)之原理和算法详细介绍 https://www.cnblogs.com/skywang12345/p/3245399.html 红黑树(五)之 Java的实现 https://www.cnblogs.com/skywang12345/p/3624343.html

树 - 红黑树(R-B Tree)

为什么要有红黑树

时间复杂度

节点的旋转算法

双红颜色修正

红黑树3种插入维护

红黑树4种删除维护

应用场景

红黑树的代码实现和实例

其它参考