# 问题
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
3
4
5
# 2. 红黑树的核心特性
红黑树是一种 自平衡二叉搜索树(BST),满足以下规则:
- 每个节点要么是红色,要么是黑色。
- 根节点始终是黑色。
- 红色节点的子节点必须是黑色(不能有两个连续的红色节点)。
- 从根节点到叶子节点的每条路径,黑色节点数相同(黑色平衡)。
- 新插入的节点默认为红色,可能会触发调整。
红黑树主要通过 变色、左旋、右旋 操作维持平衡:
- 变色(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)
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) <-- 需要变色调整,确保平衡
2
3
4
5
6
7
8
9
# 5. 为什么选择红黑树而不是 AVL 树?
- 红黑树:插入/删除 O(log n),但不要求严格平衡,适合写多的场景。
- AVL 树:严格平衡,查找比红黑树快(更少旋转),但插入/删除开销更大。
- TreeMap 侧重插入/删除效率,因此选择红黑树。
# 6. TreeMap 的常见问题
❌ 常见误区
误认为 TreeMap 线程安全
- TreeMap 不是线程安全的,多个线程同时
put()
可能导致数据异常。 - 正确方案:使用
Collections.synchronizedSortedMap(new TreeMap<>())
或ConcurrentSkipListMap
(并发有序)。
- TreeMap 不是线程安全的,多个线程同时
误认为 TreeMap 可以存储 null Key
- 错误示例:
treeMap.put(null, "A"); // NullPointerException
- 正确方案:使用
HashMap
或LinkedHashMap
(允许null
Key)。
- 错误示例:
忽视 Comparator 的影响
- 自定义 Comparator 影响 Key 的排序方式,不同 Comparator 可能导致不同顺序。
# 深入追问
🔹 为什么红黑树比 AVL 树更适合 TreeMap?
🔹 红黑树的最坏情况时间复杂度是多少?
🔹 TreeMap 如何在高并发环境下使用?
🔹 TreeMap 和 LinkedHashMap 在遍历顺序上的区别?
# 相关面试题
• 红黑树插入、删除的详细过程?
• TreeMap、HashMap、LinkedHashMap 的区别?
• TreeMap 如何优化范围查询?
• ConcurrentSkipListMap 为什么比 TreeMap 适合并发环境?