红黑树的概念
红黑树（Red-Black Tree） 是一种自平衡的二叉查找树。它在每个节点上增加了一个颜色属性（红色或黑色），通过严格的颜色约束规则来保证树的大致平衡。
红黑树的核心设计哲学是“弱平衡”：它不追求像 AVL 树那样绝对的高度平衡，而是通过限制最长路径不超过最短路径的 2 倍，大幅减少了插入和删除时的旋转次数，从而在工程实践中取得了极高的综合性能。
以下是红黑树的核心知识体系：
1. 核心性质（五大铁律）
一棵有效的红黑树必须严格满足以下 5 条性质：
- 颜色约束：每个节点只能是红色或黑色。
- 根节点规则：根节点必须是黑色。
- 叶子节点规则：所有的叶子节点（即 NIL 空节点）都是黑色。
- 红色隔离规则：如果一个节点是红色，那么它的两个子节点必须都是黑色（即不能存在连续的红色节点）。
- 黑高一致规则：从任意一个节点出发，到达其所有叶子节点的路径上，包含的黑色节点数量相同（这个数量称为“黑高”）。
重要推论：基于上述规则，红黑树的最长可能路径不会超过最短可能路径的 2 倍，从而保证了整棵树的高度稳定在
O(log n)，不会出现退化为链表的情况。2. 基础调整操作
当插入或删除节点破坏了红黑树的性质时，需要通过以下两种手段进行修复：
- 变色（Recoloring）：修改节点的红黑颜色，这是最简单的修复手段，优先使用。
- 旋转（Rotation）：分为左旋和右旋。旋转操作仅仅是调整节点的位置关系，不会破坏二叉查找树“左小右大”的排序属性。
3. 插入操作逻辑
插入新节点时，默认将其染为红色。因为如果染成黑色，会直接破坏“黑高一致”规则，导致全局调整；而染成红色，最多只会违反“红色隔离”规则（父节点也是红色），修复代价较小。
插入后的修复策略主要看叔叔节点的颜色：
- 情况 1：叔叔节点是红色。无需旋转，直接将父节点和叔叔节点变黑，祖父节点变红，然后以祖父节点为新起点向上递归检查。
- 情况 2：叔叔节点是黑色，且新节点与父节点构成“折线”（如 LR 或 RL）。先对父节点进行一次小旋转，将其转化为“直线”形态（情况 3）。
- 情况 3：叔叔节点是黑色，且新节点与父节点构成“直线”（如 LL 或 RR）。将父节点变黑，祖父节点变红，然后对祖父节点进行一次大旋转，修复完成。
4. 删除操作逻辑
删除操作比插入复杂得多。首先按照普通二叉查找树的规则删除节点，如果被删除的节点是黑色，就会破坏“黑高一致”规则，需要从替代节点开始向上逐层修复。修复的核心思想是“向兄弟节点借黑色”，通过兄弟节点变色和旋转来补足缺失的黑高。
5. 红黑树 vs AVL 树
- AVL 树：严格平衡（左右子树高度差不超过 1）。树更矮，查找性能略快；但插入和删除时极易失衡，旋转频繁，增删开销大。
- 红黑树：弱平衡（最长路径 ≤ 2 × 最短路径）。树相对高一点，查找略慢于 AVL；但插入和删除时的旋转次数显著减少，增删性能更优。
6. 工业级应用场景
因为红黑树在增、删、改、查之间取得了完美的平衡，它成为了众多底层核心组件的首选数据结构：
- Java：
TreeMap、TreeSet以及 JDK 1.8 之后HashMap中链表过长时转化的结构。 - C++：STL 标准库中的
std::map、std::set。 - Linux 内核：完全公平调度器（CFS）用于管理进程调度，以及内存管理中的虚拟内存区域（VMA）管理。