基础不牢，地动山摇。
上一期讲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选择它，就是看中这个取舍。
四、红黑树五大核心性质
- 节点只有两种颜色：红色、黑色。
- 根节点一定是黑色。
- 所有叶子节点（NIL空节点）都是黑色。
- 红色节点的两个子节点，必须是黑色。不能出现两个红节点相连。
- 从任意一个节点，到它所有后代叶子节点，经过的黑色节点数量必须相同（黑高一致）。
✅ 记住核心推论：因为规则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，红黑树退化成链表。因为节点很少的时候，链表遍历更快，省去树维护成本。
七、高频坑点
- 红黑树不是绝对平衡树！是弱平衡，不要和AVL混淆。
- 红黑树平衡不靠高度差，靠颜色规则约束黑高。
- HashMap树化不是只要链表≥8就转树，还要求数组容量≥64，数组容量不足优先扩容，不树化。
- 红黑树的节点，除了key/value，还会保存左右子节点、父节点、颜色标记，内存占用比链表节点更大。节点少的时候，链表更省内存。
专栏总结
二叉搜索树，有序但是容易长歪退化成链表。
AVL树严格平衡，查询快，但是增删旋转开销巨大。
红黑树是弱平衡二叉搜索树，通过红黑5条规则约束，最长路径不超过最短路径2倍。
修复手段：优先变色，必要时左旋/右旋。增删的旋转次数远少于AVL。
HashMap选用红黑树：在查询性能和增删维护成本之间做权衡。
节点少时链表更合适，节点多了升级红黑树，节点变少再退回链表。
欢迎点赞收藏关注，下一期继续更新：Java 泛型，让我们一起轻松学习每个知识点。
