问题

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 有序

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)

4. 红黑树的删除（Delete）如何影响平衡？

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

✅ 情况 1：删除红色节点 → 无需调整（不影响黑色平衡）。

✅ 情况 2：删除黑色节点，兄弟节点是红色

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

✅ 情况 3：删除黑色节点，兄弟节点也是黑色

• 解决方案：双重黑（Double Black）处理，需要递归调整祖先节点，可能引发额外旋转。

示例：删除 7 触发调整

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

  删除 7 后：
      10(B)
     /
   5(R)  <-- 需要变色调整，确保平衡

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
   • 正确方案：使用 HashMap 或 LinkedHashMap（允许 null Key）。

3. 忽视 Comparator 的影响

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

深入追问

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

相关面试题

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