红黑树(Red-Black Tree)详解 / GUYONG

红黑树 (Red-Black Tree) 详解

红黑树（Red-Black Tree）是一种自平衡二叉查找树（Self-balancing Binary Search Tree）。它在计算机科学中被广泛应用，能在最坏情况下保证基本动态集合操作（如插入、删除、查找）的时间复杂度为 $\mathcal{O}(\log n)$ 。

相比于普通的二叉查找树（BST），红黑树通过在每个节点上增加一个存储位来表示节点的颜色（红色或黑色），并通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长出两倍，因而是近似平衡的。

红黑树必须满足以下 5条严格的性质（这是红黑树保持平衡的基石）：

直观理解：性质4和性质5共同决定了红黑树的平衡性。因为路径上不能有连续的红节点，且每条路径的黑节点数量必须相同，所以最短的可能路径（全黑）和最长的可能路径（红黑交替）之间的长度比最多是 1:2。

虽然 AVL 树也是自平衡二叉查找树，且比红黑树更加严格平衡（左右子树高度差不超过1），但红黑树在工程实践中更为常用。

特性	红黑树 (Red-Black Tree)	AVL 树
平衡程度	近似平衡（最长路径不超过最短路径的2倍）	严格平衡（高度差 $\le 1$ ）
查找效率	$\mathcal{O}(\log n)$ ，略慢于 AVL	$\mathcal{O}(\log n)$ ，极快
插入效率	$\mathcal{O}(\log n)$ ，最多只需 2次旋转	$\mathcal{O}(\log n)$ ，最多只需 2次旋转
删除效率	$\mathcal{O}(\log n)$ ，最多只需 3次旋转	$\mathcal{O}(\log n)$ ，可能需要 $\mathcal{O}(\log n)$ 次旋转
适用场景	频繁插入、删除操作的动态数据集合	查找极其频繁，插入删除较少的静态数据集合

结论：红黑树在插入和删除时的旋转次数有严格的常数上限（最多3次），维护平衡的开销较小，因此在综合性能（查找、插入、删除）上表现更加稳定。

为了在插入和删除后维持红黑树的5条性质，主要依赖两种操作：变色（Recoloring） 和 旋转（Rotation）。

旋转是一种局部操作，用于在不破坏二叉查找树性质（左小右大）的前提下，改变树的拓扑结构。

初始插入：将新节点按照普通二叉查找树的规则插入。
初始颜色：新插入的节点一律染成红色。（原因：如果染成黑色，必然会破坏性质5（黑高一致性），处理起来极其麻烦；染成红色只可能破坏性质4（不能有连续红节点），可以通过较少的操作修复）。
修复失衡（Fixup）：如果插入节点的父节点也是红色（破坏了性质4），则需要根据**叔叔节点（父节点的兄弟节点）**的颜色分为三种情况处理：
- 情况1：叔叔节点是红色。
  - 策略：父节点和叔叔节点变黑，祖父节点变红。然后将当前节点指针指向祖父节点，继续向上递归处理。
- 情况2：叔叔节点是黑色，且当前节点是右孩子（内侧）。
  - 策略：以父节点为支点进行左旋，转化为情况3。
- 情况3：叔叔节点是黑色，且当前节点是左孩子（外侧）。
  - 策略：父节点变黑，祖父节点变红，然后以祖父节点为支点进行右旋。

删除操作是红黑树中最复杂的部分。

按照普通 BST 的规则删除节点。
如果被删除的节点是红色，树的红黑性质不受影响，直接结束。
如果被删除的节点是黑色，会破坏性质5（导致某条路径少了一个黑节点），此时需要引入“双重黑色（Double Black）”的概念，并根据兄弟节点及其子节点的颜色，分为4种复杂情况进行“变色+旋转”修复，最终将“缺失的黑色”向上推或者通过旋转消化掉。

由于红黑树优秀的综合性能，它在底层系统和基础库中无处不在：

C++ STL：std::map, std::set, std::multimap, std::multiset 的底层实现通常都是红黑树。
Java：java.util.TreeMap, java.util.TreeSet，以及 JDK 1.8 之后 HashMap 中的链表长度大于8时会转化为红黑树。
Linux 内核：
- CFS (Completely Fair Scheduler)：完全公平调度器使用红黑树来管理进程的运行时间（虚拟运行时间 vruntime 作为 Key）。
- epoll：使用红黑树来管理和维护注册的 socket 文件描述符。
- 内存管理：如 VMA (Virtual Memory Area) 的管理。

红黑树通过牺牲严格的平衡性（允许高度差达到2倍），换取了在插入和删除时更少的旋转次数。它是一种在查找、插入、删除三个操作上都达到了极佳平衡的数据结构，时间复杂度稳定在 $\mathcal{O}(\log n)$ ，是工程界最受欢迎的动态查找树。