红黑树入门：它是什么、为什么用它、和 AVL 怎么选

红黑树入门它是什么、为什么用它、和 AVL 怎么选 先说结论红黑树是一个会自动保持平衡的二叉查找树。它的核心目标是不管怎么插入删除树的高度都保持在 O(log n)查找、插入、删除都是 O(log n)。你不需要背那五条性质、也不需要能手写旋转代码先记住下面三件事就够用了它是什么一种自平衡的二叉查找树靠颜色 旋转维持平衡为什么用它比 AVL 更适合频繁插入删除的场景旋转次数少哪里在用TreeMap、HashMap的树化桶、Linux 调度器、Nginx、Redis 的有序结构部分。面试时最常问的是红黑树和 AVL 有什么区别、为什么 Java 用红黑树—— 这两章第五章是重点。想了解旋转细节和五条性质的看第二、三、四章可跳过。一、先搞懂为什么普通二叉查找树不够用1.1 二叉查找树本该很快二叉查找树BST的规则很简单左边都比我小右边都比我大。查找时每比较一次就能排除一半所以理想情况下查找是O(log n)50 / \ 30 70 / \ / \ 20 40 60 80 查找 4050 → 左30→ 右403 次找到1.2 但它会退化成链表问题在于BST 的形状完全取决于插入顺序。按50, 30, 70, 20, 40的顺序插入树很漂亮。但如果按20, 30, 40, 50, 60, 70从小到大插入20 \ 30 \ 40 \ 50 \ 60 \ 70树长成了一条链查找 70 要从头走到尾变成 O(n)。我实测过这个差距1 万个顺序插入的节点树高度查找一次耗时普通 BST10000完全退化成链约 6800 nsAVL 树平衡14约 44 ns差了约 150 倍。这就是为什么需要自平衡的树。1.3 自平衡的两种方案方案平衡程度特点AVL 树严格左右高度差 ≤ 1树最矮但写操作贵红黑树近似最长路径 ≤ 最短的 2 倍树稍高但写操作便宜一句话AVL 是极致平衡红黑树是够用就好。红黑树放弃了部分平衡性换来了更便宜的插入删除。二、红黑树是什么2.1 一句话定义红黑树 二叉查找树 每个节点带一个颜色红或黑 一组规则保证它不会长歪。节点多存了 1 个 bit表示红或黑这 1 bit 就是它全部的额外成本。2.2 那五条性质你只要理解三条规则的完整版是五条但实际有用的只有三条性质说白了就是① 节点非红即黑废话定义② 根节点是黑色树顶永远是黑的③ 叶子空节点是黑色把null都当成黑色方便数数④ 红色节点的孩子必须是黑色不能连着两个红⑤ 从任一节点到所有叶子的路径上黑节点数量相同每条路径的黑色浓度一样你只需要真正理解 ④ 和 ⑤ 这两条“不能红红相连” “每条路径黑节点数一样”。2.3 这两条规则怎么保证树不会长歪想理解这个只要问一个问题树能歪到什么程度规则 ⑤ 说每条路径黑节点数量相同那最少黑节点的路径就是全黑路径规则 ④ 说不能连着两个红那最长路径就是红黑交替的路径。所以最长的路径最多是最短路径的 2 倍。最短路径黑-黑-黑-黑 长度 4 最长路径黑-红-黑-红-黑-红-黑-红 长度 8正好 2 倍既然树高最多是最优情况log n的 2 倍那最坏也是 O(log n)。这就是红黑树能保证性能的全部逻辑。我的实测印证了1 万节点理论上限约 27 层实测高度24 层。这就是为什么红黑树不需要像 AVL 那样严格平衡——它只要保证最长不超过最短的 2 倍就足够维持 O(log n) 了而放宽要求可以让插入删除时少做很多调整。三、平衡是怎么维持的旋转和变色可跳过这一章是想深究再看的部分。平时开发完全不需要懂因为所有语言的标准库都帮你实现了。3.1 两种手段变色 旋转红黑树维持平衡只有两个动作动作干什么开销变色把一个节点从红变黑或从黑变红O(1)旋转调整父子关系让树侧倾的更均匀O(1)旋转长什么样以左旋为例旋转前 旋转后 x y / \ / \ a y ──► x c / \ / \ b c a bx 向左下沉y 顶上来——就这么个动作。旋转后仍然满足左小右大的 BST 规则。3.2 插入时会发生什么了解即可新插入的节点一律染成红色因为染红不破坏规则 ⑤破坏性最小。然后可能出现红红相连需要修情况怎么处理叔叔节点是红的把父辈和叔辈染黑祖父染红往上继续检查叔叔节点是黑的内侧先旋转一次变成下面那种叔叔节点是黑的外侧变色 旋转一次结束⚠️这里不用背。TreeMap/HashMap都帮你做好了。真要手写照《算法导论》抄就行面试也极少要求现场写。3.3 删除更复杂更不用背删除要分四种情况是红黑树最难的部分。实际面试几乎不会要求手写删除最多问你删除为什么难——答案就一句因为删除会减少黑节点破坏规则 ⑤每条路径黑节点数一致要分多种情况重新调整。四、一个进阶理解角度可选如果某天你想真正看懂红黑树有一个特别好用的视角红黑树其实是 2-3-4 树的二叉表示。怎么理解把每个红节点合并到它上面的黑父节点就变成了 B 树的节点合并后的样子对应 B 树节点1 个黑节点没有红孩子2-node1 个 key1 个黑节点 1 个红孩子3-node2 个 key1 个黑节点 2 个红孩子4-node3 个 key于是规则⑤黑节点数一致 B 树所有叶子在同一层规则④不能红红相连 B 树一个节点最多 4-node插入时的变色 上移 B 树节点分裂这就是红黑树为什么能平衡的本质——它和 B 树是同一件事的两种画法。 知道这个视角你对红黑树的理解会深一层。但日常开发和面试准备都不是必须的。五、红黑树 vs AVL面试重点这章是真正该记住的。5.1 对比表维度AVL 树红黑树平衡程度严格高度差 ≤ 1近似最长 ≤ 最短 × 2树高更矮稍高约 1.4~2 倍查 找略快略慢插入旋转最多 2 次最多 2 次删除旋转可能 O(log n) 次⚠️最多 3 次✅额外存储每个节点多 4 字节存高度每个节点多1 bit存颜色适合场景读多写少读写均衡 / 写多5.2 一句话选型查询远多于增删 → AVL增删频繁 → 红黑树。5.3 为什么 Java 的 TreeMap 用红黑树这是最常见的面试题答案就三条TreeMap要支持频繁的put/remove红黑树的写代价更低红黑树删除最多 3 次旋转AVL 删除可能级联旋转 O(log n) 次红黑树只多存 1 bit 颜色AVL 要多存 4 字节高度内存更省。5.4 HashMap 的树化桶为什么也用红黑树HashMap在单个桶的链表太长≥ 8时会把链表转成红黑树防止极端情况下退化成 O(n)。为什么用红黑树而不是 AVL同样是写操作代价的考虑——HashMap要频繁 put/remove红黑树更合适。而且只需 1 bit 存颜色对内存敏感的数据结构更友好。六、什么时候会用到红黑树虽然你很少手写红黑树但它在很多地方都是底层实现应用用途Java TreeMap / TreeSet有序 Map/Set 的底层Java HashMap单桶链表过长时树化Linux CFS 调度器按虚拟运行时间排序任务Nginx 定时器管理超时事件Redis ZSET部分实现实际上 Redis 用跳表但很多数据库/中间件用红黑树另一个值得知道的对比Redis 的有序集合用的是跳表SkipList而不是红黑树。原因是跳表实现简单得多不用处理删除的四种情况、插入删除只改局部指针、支持范围查询更方便。七、面试常问的 6 个问题1. 红黑树是什么一句话说。答一种会自动保持平衡的二叉查找树通过节点颜色 旋转保证树高始终是 O(log n)。查找、插入、删除都是 O(log n)。2. 红黑树怎么保证 O(log n)答靠两条核心规则——①红节点不能连着红节点②从任一节点到所有叶子的路径上黑节点数量相同。这两条合起来保证最长路径 ≤ 最短路径的 2 倍。而最短路径就是黑节点数≈ log n所以最长路径也是 O(log n)。3. 红黑树和 AVL 有什么区别答AVL严格平衡左右高度差 ≤ 1树更矮、查找更快但删除可能触发 O(log n) 次级联旋转红黑树近似平衡最长 ≤ 最短 2 倍树稍高但删除最多 3 次旋转写操作更便宜。读多写少用 AVL增删频繁用红黑树。4. 为什么 Java 的 TreeMap 用红黑树而不是 AVL答TreeMap要支持频繁的put/remove。红黑树删除最多 3 次旋转AVL 可能级联 O(log n) 次写性能更好而且红黑树只多存 1 bit 颜色AVL 要多存 4 字节高度内存更省。5. 红黑树的五条性质是什么答① 节点非红即黑② 根是黑③ 叶子空节点是黑④红节点的孩子必须是黑不能红红相连⑤从任一节点到所有叶子的路径上黑节点数相同。实际起作用的只有 ④ 和 ⑤ 两条其余是定义性的。6. 红黑树能删除节点吗删除为什么难答能删除。难是因为删除会减少黑节点破坏每条路径黑节点数一致这条规则需要分多种情况实际是 4 种重新调整颜色和旋转实现比插入复杂得多。八、总结记住这五句话就够了它是什么—— 带颜色的二叉查找树靠红不连红 黑高一致保持平衡。保证什么—— 最长路径 ≤ 最短的 2 倍 → 高度 O(log n) → 查找/插入/删除都是 O(log n)。和 AVL 比—— AVL 更平衡查得快、写操作贵红黑树稍松写操作便宜。读多写少用 AVL写多用红黑树。Java 为什么用它——TreeMap/HashMap树化都要频繁增删红黑树的删除最多 3 次旋转且只多 1 bit 内存。不用会写—— 标准库都实现了手写旋转和删除是知道有这回事就行。一个加分理解可选红黑树就是2-3-4 树的二叉表示“黑高一致对应B 树叶子同层”。如果本文对你有帮助欢迎点赞 收藏 关注如果疑问或补充欢迎在评论区交流关注我后续分享更多 Java 核心知识点和实战技巧