红黑树 (Red-Black Tree)

发表于 分类于

红黑树是一种自平衡二叉搜索树，通过 5 条性质保证树”近似平衡”——最长路径不超过最短路径的 2 倍，确保查找/插入/删除都是 O(log n)。

5 条性质：

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 叶子节点 (NIL) 是黑色
  4. 红色节点的两个子节点必须是黑色（不能两红相邻）
  5. 从任意节点到其叶子节点的所有路径上，黑色节点数相同（黑高相等）
1
2
3
4
5
6
7
8
红黑树示例:
                    [● 10]          ← 黑
                   /       \
              [● 5]        [● 20]   ← 黑
             /    \        /    \
           nil    nil  [R 15] [R 25] ← 红
                      /  \   /  \
                    nil nil nil nil

自平衡三连：左旋 + 右旋 + 变色。 旋转：儿子变爹，爹变儿子。插入时默认插入红色节点，然后根据叔叔节点 (uncle) 的颜色分三种情况处理：

  • 叔叔红 → 父黑、叔黑、爷红 → 递归处理爷爷
  • 叔叔黑 + 当前是父的右子 → 绕父左旋 → 变成第三种情况
  • 叔叔黑 + 当前是父的左子 → 父黑、爷红 → 绕爷右旋

在 Java 中的应用：

  • HashMap：链表长度 ≥ 8 且数组 ≥ 64 时树化为红黑树 (final void treeifyBin(Node<K,V>[] tab, int hash))
  • TreeMap：底层就是红黑树，put、get、remove 都是 O(log n)
  • TreeSet：基于 TreeMap 实现

为什么 HashMap 选红黑树而不是 AVL？ AVL 树更严格（平衡因子 ≤ 1），查找更快但对插入删除的旋转次数更多。HashMap 的树化场景下插入频率高，红黑树的”松散平衡”更合适。