# 问题

8. TreeMap 是如何保证有序的?红黑树的插入和删除如何影响平衡?

# 标准答案

TreeMap 依靠 红黑树(Red-Black Tree) 作为底层数据结构,保证 Key 的有序性。插入和删除操作会动态调整红黑树的结构,确保 树的平衡性和查询效率,避免退化为链表。红黑树通过 变色、左旋、右旋 来维持近似平衡,使得所有操作的时间复杂度维持在 O(log n)

# 答案解析

# 1. 为什么 TreeMap 能保证有序?

TreeMap 基于 红黑树 实现,每个节点存储 Key-Value,并按照 Key 的 自然顺序(Comparable)或自定义 Comparator 顺序 组织数据。

  • 插入、查找、删除 操作都遵循二叉搜索树(BST)规则:
    • 左子树的所有 Key 小于当前节点
    • 右子树的所有 Key 大于当前节点
  • 中序遍历(LNR)保证有序输出,即 firstKey() 获取最小 Key,lastKey() 获取最大 Key。
  • 红黑树的平衡性 确保操作始终是 O(log n),避免二叉搜索树退化为 O(n) 的链表。

示例:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "A");
map.put(1, "B");
map.put(2, "C");
System.out.println(map.keySet()); // 输出 [1, 2, 3],保证 Key 有序
1
2
3
4
5

# 2. 红黑树的核心特性

红黑树是一种 自平衡二叉搜索树(BST),满足以下规则:

  1. 每个节点要么是红色,要么是黑色
  2. 根节点始终是黑色
  3. 红色节点的子节点必须是黑色(不能有两个连续的红色节点)。
  4. 从根节点到叶子节点的每条路径,黑色节点数相同(黑色平衡)。
  5. 新插入的节点默认为红色,可能会触发调整。

红黑树主要通过 变色、左旋、右旋 操作维持平衡:

  • 变色(Recoloring):调整红黑色,保持黑色平衡。
  • 左旋(Left Rotate):逆时针旋转节点,使较大的 Key 作为新的根。
  • 右旋(Right Rotate):顺时针旋转节点,使较小的 Key 作为新的根。

# 3. 红黑树的插入(Insert)如何影响平衡?

新节点插入时,遵循二叉搜索树(BST)的 Key 规则,但会引发以下三种情况,需要调整:

情况 1:插入节点的父节点是黑色无需调整

情况 2:父节点是红色,叔叔节点也是红色(需要变色)

  • 解决方案:变色(父节点和叔叔节点变黑,祖父节点变红)。

情况 3:父节点是红色,叔叔节点是黑色或不存在(需要旋转)

  • 解决方案:左旋 / 右旋(依赖父节点是左子树还是右子树)。

示例:插入 5 触发调整

  原始结构:
      10(B)
     /
   7(R)
  /
 5(R)  <-- 连续两个红色,不满足规则,需要调整

  右旋变色调整后:
      7(B)
     /   \
   5(R)  10(R)
1
2
3
4
5
6
7
8
9
10
11

# 4. 红黑树的删除(Delete)如何影响平衡?

删除操作比插入复杂,因为删除节点后可能破坏平衡,涉及 兄弟节点的颜色。常见情况:

情况 1:删除红色节点无需调整(不影响黑色平衡)。

情况 2:删除黑色节点,兄弟节点是红色

  • 解决方案:变色 + 旋转,让兄弟节点变黑,维持黑色平衡。

情况 3:删除黑色节点,兄弟节点也是黑色

  • 解决方案:双重黑(Double Black)处理,需要递归调整祖先节点,可能引发额外旋转。

示例:删除 7 触发调整

  原始结构:
      7(B)
     /   \
   5(B)  10(B)

  删除 7 后:
      10(B)
     /
   5(R)  <-- 需要变色调整,确保平衡
1
2
3
4
5
6
7
8
9

# 5. 为什么选择红黑树而不是 AVL 树?

  • 红黑树:插入/删除 O(log n),但不要求严格平衡,适合写多的场景
  • AVL 树:严格平衡,查找比红黑树快(更少旋转),但插入/删除开销更大
  • TreeMap 侧重插入/删除效率,因此选择红黑树

# 6. TreeMap 的常见问题

常见误区

  1. 误认为 TreeMap 线程安全

    • TreeMap 不是线程安全的,多个线程同时 put() 可能导致数据异常。
    • 正确方案:使用 Collections.synchronizedSortedMap(new TreeMap<>())ConcurrentSkipListMap(并发有序)。
  2. 误认为 TreeMap 可以存储 null Key

    • 错误示例:treeMap.put(null, "A"); // NullPointerException
    • 正确方案:使用 HashMapLinkedHashMap(允许 null Key)。
  3. 忽视 Comparator 的影响

    • 自定义 Comparator 影响 Key 的排序方式,不同 Comparator 可能导致不同顺序。

# 深入追问

🔹 为什么红黑树比 AVL 树更适合 TreeMap?
🔹 红黑树的最坏情况时间复杂度是多少?
🔹 TreeMap 如何在高并发环境下使用?
🔹 TreeMap 和 LinkedHashMap 在遍历顺序上的区别?

# 相关面试题

红黑树插入、删除的详细过程?
TreeMap、HashMap、LinkedHashMap 的区别?
TreeMap 如何优化范围查询?
ConcurrentSkipListMap 为什么比 TreeMap 适合并发环境?