基础不牢地动山摇。上一期讲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条标签规则红黑树用两种方式修复书架变色改标签红标签改成黑、黑改成红成本最低优先用这个方案。只换标签不用挪动书本。旋转挪动书本左旋、右旋调整书本的上下父子位置不改变书本编号的大小顺序。对比AVLAVL书架稍微不对称就要挪书旋转红黑树优先换标签变色实在不行才挪书旋转次数很少。六、回到HashMap为什么要用红黑树而不是AVL回顾HashMap场景哈希桶上链表过长≥8链表查询O(n)太慢需要升级树。AVL树严格平衡查询快但是增删频繁旋转put/remove旋转多开销大。红黑树弱平衡查询接近AVL增删旋转次数少综合性能更好。所以很多标准库都用红黑树比如C 的std::map、std::setJava 的TreeMap、TreeSetLinux 内核里的一些数据结构HashMap的访问模式查询多但是put、remove也不少红黑树综合性价比更高。补充当树节点减少到≤6红黑树退化成链表。因为节点很少的时候链表遍历更快省去树维护成本。七、高频坑点红黑树不是绝对平衡树是弱平衡不要和AVL混淆。红黑树平衡不靠高度差靠颜色规则约束黑高。HashMap树化不是只要链表≥8就转树还要求数组容量≥64数组容量不足优先扩容不树化。红黑树的节点除了key/value还会保存左右子节点、父节点、颜色标记内存占用比链表节点更大。节点少的时候链表更省内存。专栏总结二叉搜索树有序但是容易长歪退化成链表。AVL树严格平衡查询快但是增删旋转开销巨大。红黑树是弱平衡二叉搜索树通过红黑5条规则约束最长路径不超过最短路径2倍。修复手段优先变色必要时左旋/右旋。增删的旋转次数远少于AVL。HashMap选用红黑树在查询性能和增删维护成本之间做权衡。节点少时链表更合适节点多了升级红黑树节点变少再退回链表。欢迎点赞收藏关注下一期继续更新Java 泛型让我们一起轻松学习每个知识点。