红黑树原理 红黑树五大性质 二叉搜索树 平衡树 HashMap红黑树 面试

基础不牢，地动山摇。

上一期讲HashMap，我们提到一个关键词：链表过长，会转成红黑树。

很多新手卡在这：

二叉搜索树是什么？平衡树是什么？红黑树到底好在哪？HashMap为什么不直接用AVL树？

网上很多教程一上来甩一堆复杂定义、旋转代码，越看越懵。

今天我们循序渐进，从最简单二叉树开始，大白话拆解红黑树，搞懂HashMap引入红黑树的目的。

一、铺垫：二叉搜索树（BST）

二叉搜索树规则，想象一个图书馆书架：

• 每个书架格子（节点）最多分出左右两个分支：左格子、右格子
• 左边分支放的书编号 ＜ 当前格子书编号
• 右边分支放的书编号 ＞ 当前格子书编号

✅ 优点：找书很快，类似二分查找，理想情况下O(logn)，每次排除一半分支

❌ 致命缺陷：如果按顺序放书（1、2、3、4、5依次放进去），书架会直接变成一条竖长的单列！

例子：依次放编号1、2、3、4、5的书，全部只能往右放。此时找编号5的书，必须一本一本从头翻，查询从O(logn)降级成O(n)，和一条链表没有区别。

👉 所以就诞生了平衡二叉树，目标：不让书架“长歪”，左右两边高度差距不能太大。

二、AVL平衡树（平衡二叉搜索树）

AVL树规则：书架左右两个分支高度差不能超过1。一旦左右高度差超标，立刻挪动书本（旋转）调整平衡。

✅ 查询极快，书架永远整齐对称

❌ 缺点：每次新增/拿走一本书，很容易触发挪动书本，调整成本很高。

放到HashMap场景：频繁put新增、remove删除元素，AVL树不停挪节点，开销太大，不合适。

三、红黑树是什么？一句话总结

红黑树：一种弱平衡二叉搜索树。

类比：它不会像AVL树那样要求绝对平衡，不追求书架绝对左右对称，只做一条硬性限制：从起点到最远端，最长的找书路径，不能超过最短路径的2倍。

怎么做到？给每本书贴标签：红色标签、黑色标签，5条标签规则约束书架，防止书架严重歪掉。

平衡要求放宽，换来：新增、拿走书本时，挪动书本（旋转）次数更少，写操作性能更好。

通过给节点标记红色/黑色，加上5条约束规则，限制树不会严重“长歪”。

权衡之后：插入、删除时旋转次数更少，写操作性能更好，查询不错，增删代价低。HashMap选择它，就是看中这个取舍。

四、红黑树五大核心性质

✅ 记住核心推论：因为规则4、5，最长路径最多是最短路径2倍，树不会极端倾斜。

五、红黑树如何维持平衡：变色 + 旋转

新增/拿走一本书，会破坏上面5条标签规则，红黑树用两种方式修复书架：

• 变色（改标签） ：红标签改成黑、黑改成红，成本最低，优先用这个方案。只换标签，不用挪动书本。
• 旋转（挪动书本：左旋、右旋） ：调整书本的上下父子位置，不改变书本编号的大小顺序。

对比AVL：AVL书架稍微不对称就要挪书（旋转）；红黑树优先换标签（变色），实在不行才挪书，旋转次数很少。

六、回到HashMap：为什么要用红黑树，而不是AVL？

回顾HashMap场景：哈希桶上链表过长（≥8），链表查询O(n)太慢，需要升级树。

• AVL树：严格平衡，查询快，但是增删频繁旋转，put/remove旋转多开销大。
• 红黑树：弱平衡，查询接近AVL，增删旋转次数少，综合性能更好。

所以很多标准库都用红黑树，比如：

• C++ 的 std::map、std::set
• Java 的 TreeMap、TreeSet
• Linux 内核里的一些数据结构

HashMap的访问模式：查询多，但是put、remove也不少，红黑树综合性价比更高。

补充：当树节点减少到≤6，红黑树退化成链表。因为节点很少的时候，链表遍历更快，省去树维护成本。

七、高频坑点

专栏总结

欢迎点赞收藏关注，下一期继续更新：Java 泛型，让我们一起轻松学习每个知识点。