红黑树介绍
红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它是由 Rudolf Bayer 在 1972 年发明的。它在每个节点上增加一个存储位表示节点的颜色，可以是红色或黑色，通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因此是近似平衡的。
红黑树的五大性质
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL 节点，即空节点）都是黑色。（通常将叶子视为虚拟的、黑色的空节点，方便处理边界。）
- 如果一个节点是红色，则它的两个子节点都是黑色。（即不能有两个连续的红色节点。）
- 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。（这条性质被称为“黑色完美平衡”或“黑色高度一致”）
这些性质保证了红黑树的关键特性：从根到叶子的最长路径不超过最短路径的两倍。因此，红黑树的高度大致维持在 O(log n)，从而在动态插入和删除时仍能保持较高的查找效率。
为什么需要红黑树？
普通的二叉查找树在极端情况下（如插入有序数据）会退化成链表，导致查找效率从 O(log n) 降至 O(n)。红黑树通过颜色和旋转操作来维持平衡，避免了这种退化，保证了在最坏情况下基本动态操作（查找、插入、删除）的时间复杂度为 O(log n)。
常见应用
- 许多编程语言的集合类或标准库中的有序关联容器，如 C++ STL 中的
map和set，Java 中的TreeMap和TreeSet，都基于红黑树实现。 - 在 Linux 内核中，红黑树用于管理内存区域、调度器等。
- 一些文件系统（如 Ext4）也使用红黑树来组织目录项。
插入与删除
红黑树的插入和删除操作会破坏上述性质，因此需要执行重新着色和旋转（左旋或右旋）来恢复平衡。这些调整通常需要 O(log n) 的时间，并且最多进行 O(1) 次旋转，因此整体效率很高。
插入过程（简略）：
- 按二叉查找树规则插入新节点，并将其着色为红色（因为红色更容易调整，且不会立即破坏性质 5）。
- 如果父节点是黑色，则无需调整；如果父节点是红色，则违反了性质 4，需要根据叔叔节点的颜色进行重新着色或旋转，直到满足所有性质。
删除过程（简略）：
删除节点可能破坏性质 5（黑色节点数量变化），因此需要引入“双重黑色”的概念，并通过旋转和着色来修复。
旋转操作
- 左旋：以某个节点为支点，将其右子节点提升为新的父节点。
- 右旋：以某个节点为支点，将其左子节点提升为新的父节点。
旋转操作不改变二叉查找树的性质，但能调整树的结构以恢复平衡。
与 AVL 树的对比
红黑树和 AVL 树都是自平衡二叉查找树。AVL 树平衡更严格（左右子树高度差不超过 1），因此查找更快，但插入和删除的旋转次数可能更多。红黑树在插入和删除时通常需要的旋转次数更少（平均），因此更适用于频繁插入删除的场景。在大多数实际应用中，红黑树是更常用的选择。
总结来说，红黑树是一种高效、可靠的平衡二叉查找树，通过颜色约束和旋转操作，保证了动态集合操作的对数时间复杂度，广泛应用于系统底层和标准库中。
红黑树可视化演示：用括号表示法
你也可以将红黑树想象为每个节点带有颜色标记的二叉查找树。在线演示网站（如 Red/Black Tree Visualization）提供了动态的图片和动画，帮助你直观理解插入、删除和旋转过程。