红黑树

红黑树是一种高效的自平衡二叉搜索树，通过以下5条规则确保平衡性：

五大核心规则：

1. 节点非红即黑
2. 根节点必须为黑
3. 叶子节点（NIL）全黑
4. 红色节点不能有红子节点（无连续红）
5. 任意节点到叶子路径的黑色节点数相同

平衡原理：

通过约束黑色节点数量（规则5）和限制红色节点连续出现（规则4），确保最长路径不超过最短路径的两倍，从而维持近似平衡。当插入/删除破坏规则时，通过颜色翻转+旋转修复。

插入操作示例（插入后修复平衡）：

假设初始红黑树如下（B表示黑，R表示红）：

       B8
       / \
     R5  B10
    /  \
  B3   B7

步骤1：插入红色节点6

插入时新节点默认为红色，减少破坏规则5的可能性：

       B8
       / \
     R5  B10
    /  \
  B3   B7
         \
          R6  ← 新增节点

此时父节点7是黑色，不违反规则，插入完成。

步骤2：触发颜色翻转（父节点为红，叔节点为红）

假设插入节点4到3的右侧：

        B8
       / \
     R5  B10
    /  \
  B3   B7
 / \
NIL R4 ← 新增节点

此时父节点3为红，违反规则4。检查叔节点7：

• 父红、叔红 → 进行颜色翻转
• 父、叔变黑，祖父5变红
• 祖父5变为红后，检查其父节点8是否为红（此处8为根节点需保持黑）

调整后：

        B8
       / \
     B5  B10
    /  \
  R3   R7
 / \
NIL R4

步骤3：触发旋转（父红叔黑，形成三角结构）

假设继续插入节点2到3左侧：

        B8
       / \
     B5  B10
    /  \
  R3   R7
 / \
R2  R4 ← 新增节点2

此时父节点3为红，子节点2也为红，违反规则4。检查叔节点7（红）：

• 父红、叔红 → 颜色翻转（同步骤2）
• 父3、叔7变黑，祖父5变红
• 但祖父5的父节点8为黑，无需进一步调整

调整后：

        B8
       / \
     R5  B10
    /  \
  B3   B7
 / \
B2  B4

关键修复操作总结：

1. 颜色翻转：当父节点和叔节点均为红时，将父、叔变黑，祖父变红。
2. 左旋/右旋：当父红叔黑且形成"三角结构"时，通过旋转将问题转换为线性结构。
3. 旋转+变色：线性结构下（如父红且同侧子红），旋转后调整颜色。

对比AVL树：

• 红黑树：通过颜色约束宽松平衡，减少旋转次数，适合频繁插入删除场景。
• AVL树：严格平衡（左右子树高度差≤1），查找更快但维护成本高。

通过上述机制，红黑树在动态数据场景下以较低维护成本维持高效操作（O(log n)）。

⬅️ TreeMap源码解析 🏠 00-Java ➡️ 00-容器选型总对比