红黑树面试常考知识点
红黑树的 5 条性质（必背）
(1) 每个节点非红即黑
(2) 根节点是黑色
(3) 叶节点（NIL）是黑色
(4) 红色节点的两个子节点都是黑色（红节点不能相邻）
(5) 任意节点到其每个叶子路径上，黑色节点数量相同（黑高相等）
记忆口诀：根黑叶黑、红不相邻、黑高相等
红黑树 vs AVL 树
| 对比维度 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡标准 | 近似平衡（最长 ≤ 2×最短） | 严格平衡（|leftH - rightH| ≤ 1） |
| 查找 | O(log n) | O(log n) |
| 插入/删除 | O(log n)，旋转 ≤ 3 次 | O(log n)，旋转可能 O(log n) 次 |
| 适用场景 | 插入删除频繁（如 HashMap、TreeMap） | 查找远多于修改（如数据库索引） |
| 额外开销 | 1 bit 颜色标记 | 每个节点存高度 |
ConcurrentHashMap 选红黑树的理由：
- 哈希表写入频繁，红黑树旋转次数更少，写竞争更低
- 近似平衡足够保证 O(log n) 性能，无需 AVL 的严格平衡
插入修复的 3 种情况（高频考点）
插入新节点默认红色（破坏性质 4 时修复）：
前提：父节点是红色（否则无需修复），祖父节点存在
Case 1：叔叔节点是红色
操作：父节点变黑、叔叔节点变黑、祖父节点变红
效果：把红色上移，继续以祖父为当前节点向上修复
Case 2：叔叔节点是黑色，当前节点是右孩子
操作：左旋父节点
效果：转换为 Case 3
Case 3：叔叔节点是黑色，当前节点是左孩子
操作：父节点变黑、祖父节点变红，右旋祖父节点
效果：修复完成
删除操作的核心思想
- 删除节点后，路径上的黑高可能被破坏（性质 5）
- 引入 “双重黑” 概念：删除黑色节点后，用双黑标记该路径少了一个黑色
- 通过旋转和变色将双黑消除或向上传递
- 面试要求：理解思想即可，很少要求手写删除代码
ConcurrentHashMap 树化的 3 个特殊点
- 双向链表 + 红黑树并存：TreeNode 同时维护
prev/next链表指针和parent/left/right树指针，两者共存 - 扩容时先拆分再退化：扩容时按
hash & oldCap拆分为高低位链表，若链表长度 ≤ 6 则退化为普通 Node 链表 - 读写锁优化：
TreeBin.lockState用 CAS 实现轻量锁，写操作加锁时不影响读操作遍历first链表
面试高频追问
-
为什么树化阈值是 8？为什么退化阈值是 6？ → 泊松分布下 8 的概率极低；6 与 8 之间有 2 的缓冲，避免临界震荡。
-
table.length < 64 时为什么优先扩容而非树化？ → 冲突的根源是桶太少，扩容让节点分散到更多桶，比树化更根本地解决问题。
-
读操作在红黑树上如何保证线程安全？ →
TreeBin.find()遍历first链表而非树结构，无需加锁；Node.val和next用 volatile 保证可见性。 -
红黑树在扩容时怎么处理？ → 拆分为低位（索引不变）和高位（索引 + oldCap）两条链表，长度 ≤ 6 退化为链表，否则重建红黑树。
-
HashMap 和 ConcurrentHashMap 树化实现有何不同？ → HashMap（JDK 1.8+）直接用
TreeNode做桶头；ConcurrentHashMap 用TreeBin封装树，额外维护读写锁和 first 链表。
参考链接
- 链表与红黑树的转换机制 - 链表/红黑树转换机制
- 锁机制实现详解 - 锁机制原理