红黑树是一种特殊的二叉搜索树，它通过颜色标记和一系列规则来保证树的平衡，从而让插入、删除、查找等操作都能在近似O(log n)的时间复杂度内完成。对于初学者来说，理解红黑树的核心规则是关键，下面我们一步步拆解它的“平衡密码”。
为什么需要红黑树？¶
普通的二叉搜索树在插入有序数据时会退化成链表（比如按1、2、3、4、5顺序插入，树会变成一条向右的链），此时查找时间复杂度会从O(log n)退化为O(n)。为了解决这个问题，我们需要一种“自平衡”的二叉搜索树——红黑树就是其中的经典代表。它通过给节点涂颜色（红/黑）和严格的规则约束，让树始终保持近似平衡状态。
红黑树的5条核心规则¶
红黑树的每个节点有一个颜色属性（红或黑），加上以下5条规则，共同保证了树的平衡：
规则1：每个节点要么是红色，要么是黑色¶
最简单的颜色标记，没有其他颜色。
规则2：根节点必须是黑色¶
根节点固定为黑色，避免“根节点是红色”导致后续路径的黑高不一致。
规则3：所有空叶子节点（NIL节点）被视为黑色¶
在画图或代码中，我们通常用NIL表示空的子节点（比如叶子节点的左右子节点），这些NIL节点本身也是黑色的。这是为了统一规则——所有路径都从实际节点到NIL节点，无需单独处理叶子的颜色。
规则4：如果一个节点是红色的，则它的两个子节点必须是黑色¶
红色节点不能有红色的子节点。
举个例子：如果父节点是红色，那么左孩子和右孩子必须是黑色（如图1）；如果父节点是黑色，子节点可以是红色或黑色。
（图示：红色节点下挂两个黑色子节点）
为什么？ 避免连续两个红色节点，否则会导致“红色链”，破坏平衡。
规则5：从任一节点到其所有后代NIL节点的路径上，黑色节点的数量必须相同¶
这条规则定义了“黑高”的一致性：从根到叶子的所有路径中，黑色节点的数量（称为“黑高”）必须相等。
举个例子：假设从根节点到某个叶子的路径上有3个黑色节点，那么所有其他路径的黑高也必须是3。
为什么？ 黑高相等意味着树的最长路径（由红黑交替组成）不会比最短路径长太多，从而保证树的高度稳定在O(log n)。
规则如何保证平衡？¶
这5条规则共同作用，让红黑树“近似平衡”：
- 规则4 阻止了连续红色节点，确保红色节点不会形成“红色块”；
- 规则5 强制所有路径的黑高一致，最长路径最多是最短路径的2倍（黑高相等，红节点可以穿插在黑色节点之间）。
最终，红黑树的高度被限制在2倍log n（n为节点数），因此查找、插入、删除的时间复杂度都稳定在O(log n)。
插入节点时的调整逻辑¶
插入新节点时，我们先按二叉搜索树规则找到插入位置，然后将新节点标记为红色（规则2允许根是黑色，其他节点默认红色更安全，因为红色节点不能有红色子节点，初始插入红色更容易满足规则4）。但此时可能违反规则4或规则5，需要调整：
情况1：新节点是红色，但父节点是黑色
此时不违反任何规则，直接插入即可（父节点黑色，子节点红色，满足规则4）。
情况2：新节点是红色，父节点也是红色
此时违反规则4（父红子红），需要调整：
- 步骤1：将父节点设为黑色（避免父红）；
- 步骤2：如果祖父节点是黑色，则将祖父节点设为红色（因为祖父节点是黑色，不违反规则4）；
- 步骤3：如果祖父节点是红色（此时祖父节点的父节点可能是红色，需要递归调整），则可能需要旋转（左/右旋转）或重新着色。
（注：具体旋转操作需根据父节点和叔叔节点的颜色决定，此处不深入细节，但核心是通过调整颜色和旋转，让树重新满足所有规则。）
红黑树的应用场景¶
红黑树因为平衡稳定、插入删除灵活，被广泛应用于需要高效有序操作的场景：
- Java的TreeMap/TreeSet：基于红黑树实现，保证键值对的有序性和快速插入删除；
- Redis的有序集合（Sorted Set）：用红黑树维护有序数据，支持范围查询；
- Linux的进程调度：用于维护进程优先级的有序结构。
总结¶
红黑树通过5条规则（颜色标记+黑高一致）实现自平衡，它不需要严格限制树的高度（如AVL树的高度差），而是通过“避免连续红节点”和“强制黑高一致”来平衡树的结构。这让它在插入、删除、查找操作中都能保持高效，成为平衡二叉搜索树的经典方案。理解这些规则，你就能明白红黑树“平衡”的本质——用颜色约束和黑高一致性，在效率和稳定性之间找到完美平衡点。