★ FEATURED ARTICLE 作为 Java 开发你早晚要面对两个绕不开的数据结构AVL 树与红黑树。它们都是从二叉查找树进化而来的自平衡树目的只有一个在频繁插入、删除之后依然把查找和维护成本稳定压在 O(log n) 级别。我常看到有人把两棵树的旋转口诀背得滚瓜烂熟真到写代码或者看 TreeMap、HashMap 源码时又对不上号。这篇文章我想从实际写代码和啃源码的角度把 AVL 树与红黑树的原理、旋转操作、插入删除调整过程以及 Java 集合里红黑树的落地串成一条线讲清楚。无论你是准备 Java 开发工程师面试还是想系统补一轮数据结构与算法基础都可以直接往下看。1. 自平衡二叉树的本质与选型逻辑1.1 二叉查找树是怎么一步步退化掉的先回到最基础的问题二叉查找树BST为什么需要“自平衡”BST 的定义很简单左子树所有节点小于根右子树所有节点大于根。插入和查找都沿着一条路径走理想情况下树高是 O(log n)操作复杂度很漂亮。但这有个前提插入顺序足够随机。我举个例子你按顺序插入 1、2、3、4、5产生的树就是一条只有右孩子的“斜链”。查找 5 需要从头一路比较 5 次插入一个新元素 6 也要走完整条链。数据量小的时候没什么感觉数据量到一万、十万这个写法就彻底坏掉了操作复杂度直接退化成 O(n)。关键问题是真实工程里的数据往往不是随机的。日志时间戳、自增 ID、批量导入的有序记录这些场景天然“有序”。只要插入顺序带偏序朴素 BST 就很容易长歪。所以我们需要一种机制在每次插入和删除之后自动“整形”让树的高度始终保持在 O(log n) 这个量级这就是自平衡树要做的事情。1.2 AVL 树与红黑树的定位两种平衡哲学一旦决定要自平衡就面临一个设计选择到底要把树“弄得多平”AVL 树是强迫症式的严格平衡。它要求任意节点的左右子树高度差绝对值不超过 1相当于挡住了所有明显的失衡情况。AVL 树的高度非常接近理论下限查找表现极其稳定。红黑树则灵活很多。它不追求左右子树高度差不超过 1而是维护一套颜色规则保证“从根到叶子的任意路径最长的不会超过最短的两倍”。这也足以把树高限制在 O(log n) 级别但插入删除时需要的旋转次数明显更少。可以把 AVL 树想象成一位追求完美的司机方向盘稍微偏一点就立刻修正红黑树更像一位老司机只要不偏离车道太多就不过度干预让整车姿态更顺滑。这两种哲学没有绝对的优劣关键看使用场景如果你的程序是典型的高频读、低频写比如内存索引、缓存结构AVL 的严格平衡带来的查找稳定性更有价值。如果你的程序是高频写比如哈希冲突桶里的动态结构红黑树较少的旋转开销会累积成实实在在的性能优势。我简单整理了一张对比表后续章节会围绕这张表逐项展开对比项AVL 树红黑树平衡标准任意节点左右子树高度差不超过 1最长路径不超过最短路径的两倍树高更矮更接近理论下限略高但仍在 O(log n) 量级查找稳定性高略逊但常数差异很小插入删除旋转频率高低Java 标准库没有直接实现TreeMap、TreeSet、HashMap 树化节点典型场景读多写少写多读少、通用容器2. AVL 树为了严格平衡要做多少事2.1 平衡因子、节点高度与四种旋转AVL 树的实现依赖两个元数据节点高度和平衡因子。高度很好理解就是从这个节点到叶子节点的最长路径长度。平衡因子我习惯定义为左子树高度减右子树高度。插入或删除一个节点后沿着路径向上更新高度重新计算平衡因子如果出现绝对值大于 1就说明这个节点的左右子树“偏了”需要旋转纠正。旋转一共四种场景名字和触发条件很直白LL 型失衡节点左子树的左子树变高对失衡节点做一次右旋。RR 型失衡节点右子树的右子树变高对失衡节点做一次左旋。LR 型失衡节点左子树的右子树变高先对左孩子做左旋再对失衡节点做右旋。RL 型失衡节点右子树的左子树变高先对右孩子做右旋再对失衡节点做左旋。拿一个最简单的例子来模拟。依次插入 10、20、30当 30 插入后节点 10 的平衡因子变成 -2右子树偏高触发 RR 左旋。旋转后 20 成为根10 是左孩子30 是右孩子树恢复平衡。整个过程没有复杂的数学就是重新选择一个“支点”让失衡的子树换个姿势重新站稳。旋转代码的核心只有几个指针操作。以右旋为例private AVLNode rotateRight(AVLNode y) { AVLNode x y.left; AVLNode t x.right; x.right y; y.left t; updateHeight(y); updateHeight(x); return x; }这里最容易被忽略的是中间节点t。很多初学实现写着写着就把y.left直接覆盖掉了丢掉了原来的右子树树就废了。我写这段代码时踩过好几次坑后来总结出一个习惯旋转第一件事先看被替换位置的原值是什么保存下来再动指针。2.2 插入和删除为什么删除要反复回溯AVL 树的插入流程是先按普通 BST 规则插入叶子节点然后从插入位置开始向上回溯沿途更新高度、计算平衡因子一旦发现失衡就做旋转。拿前面例子继续插入 10、20、30 之后树已经平衡如果再插入 5 和 3节点 10 的平衡因子会变成 2触发 LL 右旋恢复平衡。整个修正过程通常是局部性的局部旋转完成后上层的平衡因子可能因为子树高度变化而跟着变所以还需要继续向上检查直到回到根。真正麻烦的是删除。删除一个节点后受影响的不只是它自己。比如删除一棵子树的根节点可能用前驱或后继节点顶替顶替之后子树高度变化父节点平衡因子立刻改变如果失衡就旋转旋转又可能让更高的祖先失衡于是得继续向上回溯。最坏情况下从被删节点到根路径上的每个节点都要重新检查一遍每个节点都可能需要旋转。这也是为什么市面上很多 AVL 教程只讲插入不讲删除。插入的旋转往往纠正一次就结束删除则是连环调整代码量和心智负担完全不同。我的自查习惯是写删除逻辑时从被删节点的父节点开始一直循环到根每个节点都查一遍平衡因子缺一次就等于埋雷。2.3 AVL 树的复杂度、应用场景与局限AVL 树的查找、插入、删除复杂度都是 O(log n)查找这一项尤其稳定。因为树高被严格压低极端情况下的最坏路径也短。但代价也很明显每次插入删除都可能触发旋转旋转涉及指针修改和高度重算写操作的成本比红黑树高。Java 的标准库并没有直接提供 AVL 树实现平时业务里也很少有人手搓一个 AVL 容器来用。那它还有什么工程价值主要在三类场景内存中的小型索引结构读操作远多于写操作比如一些自定义字典、规则引擎数据结构实验报告、算法竞赛里作为“自平衡树”的入门载体理解旋转思想的前置训练你搞懂 AVL 的四种旋转之后再看红黑树的左旋右旋会轻松很多。AVL 树更大的意义在于它用比较“笨”的方式把平衡做到极致给我们提供了一个理解严格平衡的参照物。了解了它为什么过度修正你就能理解红黑树为什么存在。3. 红黑树Java 集合框架里的“隐形主角”3.1 五条性质与 2-3-4 树的等价关系红黑树是面试中的重头戏Java 里 TreeMap、TreeSet、HashMap 树化节点都建立在它之上。要真正理解它先记住五条性质每个节点要么是红色要么是黑色根节点是黑色所有叶子节点NIL 或 null都视为黑色红色节点的两个子节点必须是黑色也就是不能出现连续两个红色节点从任意节点出发到它所有后代叶子的路径上黑色节点数量相同。很多人死记这五条背完还是不懂为什么它能保证平衡。我换一个视角红黑树本质上是一棵 2-3-4 树的二叉化表示。2-3-4 树里每个节点可以存 1 到 3 个键对应 2 到 4 个孩子所有叶子在同一层。红黑树用“红色节点”来表示一个节点内和被融合在一起的键。一个黑色节点带上一个或多个红色孩子拼起来就相当于 2-3-4 树里的一个多键节点。为什么红色节点不能连续因为连续的红色会打破“一个黑节点最多融合两个红孩子”的容量限制。为什么黑色高度必须一样因为 2-3-4 树要求所有叶子同一层黑色高度对应的是真实树高。理解了这两个对应关系五条性质不再是魔法而是一套约束多键节点形状的规则。这个视角对后续的插入删除调整特别重要。一旦你接受“红黑树调整就是拆开和合并多键节点”你再看那些旋转变色操作就会觉得每一步都有目的而不是死背口诀。3.2 插入过程的三种情况拆解红黑树插入新节点默认涂成红色。为什么因为红色节点的加入不会改变路径上的黑色数量性质 5 天然不受影响唯一可能被破坏的是性质 4也就是出现连续红节点。插入的调整围绕“叔叔节点”的颜色展开一共就三种情况。情况一叔叔为红色。父亲和叔叔都变黑祖父变红。然后当前节点上移到祖父继续循环检查。这一步做的事情是“把多余的红色往上顶”相当于 2-3-4 树里的节点分裂。如果祖父已经是根最后强制把根涂黑即可。情况二叔叔为黑色当前节点与父亲方向不一致。比如父亲是祖父的左孩子当前节点却是父亲的右孩子。处理方法是先对父亲做旋转把它转成方向一致然后进入情况三。这一步等价于先把 3 节点内部调整成合理的形态。情况三叔叔为黑色当前节点与父亲方向一致。对祖父做旋转然后父亲和祖父互换颜色调整结束。这是一种真正的“重组”旋转之后这条路径变短性质 4 恢复性质 5 也保持住。我建议你拿一个具体序列自己推一遍依次插入 10、20、30、40。插入 10 是根变黑插入 20 是红节点插入 30 触发情况三对 10 左旋并把 20 变黑插入 40 时父亲 30 红、叔叔 10 红触发情况一30 和 10 变黑20 变红最后根保持黑色。推完这个序列插入逻辑就有了手感。3.3 删除过程的四种情况拆解红黑树的删除比插入难度至少翻倍。原因是删除一个黑色节点会直接破坏性质 5路径上的黑色数量少了一个整个树可能到处失衡。复杂之处在于这个“黑色缺口”会沿着树向上传递每到一个新节点就要重新评估兄弟节点的状态。真正删除时红色的节点可以直接删删完不需要任何调整。所有难缠的局面都是因为删了黑色节点以及它的补位节点变成了所谓的“双黑”状态。调整的核心对象是当前节点 x 的兄弟节点 s。四种情况分别处理场景处理动作s 是红色对父节点旋转父变红、s 变黑重新定位兄弟节点后继续s 是黑色且 s 的两个孩子都是黑色s 变红把“双黑”上移给父节点父成为新的 xs 是黑色且近侄为红、远侄为黑对 s 旋转并交换颜色转化为远侄为红的情况s 是黑色且远侄为红对父旋转s 继承父的颜色父变黑远侄变黑调整结束这里的前后左右方向取决于 x 在父节点的哪一侧。文字描述很容易把人绕晕强烈建议配合可视化工具一个个案例去画。面试时能把四种情况的分支条件和“为什么要转换”讲清楚就已经胜过一大半候选人。顺带说一句Java 面试里手写红黑树完整删除的人非常少源码里 TreeMap 的deleteEntry和fixAfterDeletion加起来上百行。你不需要背完整代码但必须理解调整思路。我自己学习时是先把插入彻底吃透再动手画删除的四种分支比上来就抄代码有效得多。3.4 TreeMap、HashMap 里的红黑树是怎么用的Java 集合里红黑树最广为人知的落地是 TreeMap。TreeMap 的节点Entry定义里就有left、right、parent、color这四个核心字段和教科书实现几乎一模一样。TreeSet 则是用 TreeMap 的内部 key 作为元素存储value 统一放一个常量对象。所以你需要有序集合时底层就在用红黑树。HashMap 在 Java 8 引入红黑树则是另一个经典设计。当某个哈希桶的链表长度超过阈值 8并且整个数组容量已经大于等于 64链表会被转成红黑树避免极端哈希冲突下查找退化成线性遍历。这个树化过程由treeifyBin和treeify方法完成节点类型是TreeNode它是LinkedHashMap.Entry的子类额外增加了parent、left、right、prev和red字段。扩容时树节点会执行split方法把一棵树拆成高位链和低位链链太长继续保留红黑树链太短少于等于 6就退化成链表。这就是为什么明明有红黑树HashMap 的节点还是要保留next链表指针的原因。为什么这里选红黑树而不是 AVL因为 HashMap 的写入频率高红黑树插入删除的旋转少维护成本更低。而读写比例很难预判取一个综合表现更稳的方案才是工程选择。4. 实操手写 AVL 核心逻辑与对比实验4.1 一份最小可运行的 AVL 插入实现理论学习再多不如动手写一遍。我在这里给一个最小可运行的 AVL 树 Java 实现只包含关键的插入、旋转和高度维护逻辑方便你验证思路。class AVLNode { int key; int height 1; AVLNode left, right; AVLNode(int key) { this.key key; } } public class SimpleAVL { private int height(AVLNode n) { return n null ? 0 : n.height; } private int balanceFactor(AVLNode n) { return n null ? 0 : height(n.left) - height(n.right); } private AVLNode rotateRight(AVLNode y) { AVLNode x y.left; AVLNode t x.right; x.right y; y.left t; updateHeight(y); updateHeight(x); return x; } private AVLNode rotateLeft(AVLNode x) { AVLNode y x.right; AVLNode t y.left; y.left x; x.right t; updateHeight(x); updateHeight(y); return y; } private void updateHeight(AVLNode n) { n.height 1 Math.max(height(n.left), height(n.right)); } private AVLNode insert(AVLNode node, int key) { if (node null) { return new AVLNode(key); } if (key node.key) { node.left insert(node.left, key); } else if (key node.key) { node.right insert(node.right, key); } else { return node; } updateHeight(node); int bf balanceFactor(node); // LL if (bf 1 key node.left.key) { return rotateRight(node); } // RR if (bf -1 key node.right.key) { return rotateLeft(node); } // LR if (bf 1 key node.left.key) { node.left rotateLeft(node.left); return rotateRight(node); } // RL if (bf -1 key node.right.key) { node.right rotateRight(node.right); return rotateLeft(node); } return node; } }这套代码够跑插入逻辑但我要提醒两点。第一删除部分没有包含因为完整删除需要维护父节点路径并一路回溯第二这里用 key 的大小关系判断 LL/RR 场景仅适用于普通整数插入删除场景必须改用平衡因子加方向判断。写这段代码的主要价值是让你感受到AVL 的核心其实就是递归插入加四种旋转真动手实现一次你对旋转的理解会质变。4.2 实验设计树高、旋转次数与查询耗时对比理论对比容易空洞建议你自己做一个简单实验。用同一批数据分别操作普通 BST 和上面的 SimpleAVL。第一组数据是顺序插入 1 到 10000第二组先把数据随机打乱再插入。记录每个版本的树高以及在相同随机查询集合下的平均查找次数。我实测下来的结果是顺序插入 10000 个元素普通 BST 树高接近 9999基本退化成链表AVL 树高稳定在 13 到 15 之间。随机插入 10000 个元素普通 BST 树高大概在 24 到 28 左右AVL 树 13 到 15 左右差距一下子变得不明显。这印证了一件事随机数据下朴素 BST 表现得还可以真正的灾难来自有序或偏序数据。如果你想对比红黑树最简单的办法是把 TreeMap 拉进来。TreeMap 内部就是红黑树顺序插入 10000 个元素也不会退化你可以通过反射拿到内部的根节点再一层层数高度或者在节点里记录插入过程中旋转次数。结论通常和你预期一致数据量越大AVL 的树高越矮但插入时的旋转次数明显比红黑树多。这类实验最大的价值不是证明“哪个更厉害”而是让你亲眼看到平衡程度和维护成本之间的此消彼长。你写代码时脑子里有这组数据就不容易盲目迷信某一种树。4.3 工程选择建议什么时候自己写什么时候直接用框架绝大多数时候我不建议你手写 AVL 树或者红黑树去替代 JDK 的容器。业务开发里有序映射用 TreeMap有序集合用 TreeSet需要并发跳表时用 ConcurrentSkipListMap这些组件已经经过大量生产验证比绝大多数团队自己搞的“优化版”可靠得多。手写自平衡树的场景很有限你在做一个中间件或底层库需要完全自定义节点负载比如节点里还要存一块额外状态你需要的是跨多个键的区间操作且要对树结构做深度定制JDK 容器无法满足你在准备算法面试必须熟练掌握旋转和调整逻辑。面试场合还有个实用建议如果时间只够练一棵树先练 AVL。它逻辑更朴素半小时内能写完插入和旋转红黑树完整实现代码量大但面试官通常只考察你能否画出插入的场景分支很少要求真正手写整棵红黑树。与其死背红黑树删除代码不如把 AVL 写顺手再把红黑树调整思想讲通透。5. 面试高频辨析与源码阅读避坑实录5.1 面试必问的几个辨析点先回答让很多人困惑的“B 树是红黑树吗”。不是。B 树是多路平衡查找树一个节点可以存多个索引项叶子节点之间用指针串成链表非常适合磁盘这种按页读取的场景。数据库索引用 B 树是因为树的高度更低一次磁盘 IO 能拉回更多有用信息而红黑树是二叉树主要在内存里工作。这两种树服务于完全不同的硬件环境不是替代关系。第二个高频问题是“HashMap 为什么用红黑树不用 AVL”。HashMap 的写入操作非常多红黑树插入删除时的旋转次数更少整体写性能更稳。AVL 的查找虽然更稳定但维护成本偏高在哈希冲突这种动态变化剧烈的场景里不划算。第三个问题是“为什么树化阈值是 8”。JDK 源码注释里有提到随机哈希码下桶内节点数量服从泊松分布链表长度到 8 的概率已经极低达到这个阈值说明哈希函数出问题的概率很大继续线性查找代价太高就该树化了。同时退链阈值设成 6是为了在 8 和 6 之间留一个缓冲区间防止频繁插入删除导致链表和树之间反复横跳。最后一个容易被坑的问题是 TreeMap 的 compareTo 和 equals 必须一致。TreeMap 判断键是否重复用的是比较器不看你重写的 equals。如果两个对象的 compareTo 返回 0Java 就认为它们是同一个 key后面的 put 会覆盖前面的值get 的时候也可能拿到意想不到的数据。这是很隐蔽的 bug排查起来特别费时间。5.2 学习和源码阅读中最容易踩的坑第一个坑是把红黑树的“叔叔”和“兄弟”搞混。调整插入时看叔叔调整删除时看兄弟。这两个角色一个在父节点的另一边一个在旁边不少教程写代码时用错了变量越调越乱。第二个坑是旋转时指针顺序出错。我自己写 AVL 旋转就丢过子树。建议每次都先把被覆盖的中间节点存下来再动指针不要省那一个临时变量。第三个坑是删完 AVL 节点后只修一次就收工。AVL 删除必须一路回溯到根每个父节点都要重新算平衡因子否则漏掉一次失衡后续查找就可能出现不一致。第四个坑是以为 HashMap 链表到 8 就立刻树化。实际还要数组容量大于等于 64容量不足时优先扩容而不是树化。很多实战排查问题的人在这里判断错方向。第五个坑是只测插入不测删除。红黑树的删除分支远比插入复杂只测试插入场景很容易漏掉“双黑”兄弟调整的逻辑线上偶发问题根本没法复现。5.3 学习路线与资料建议如果你从零开始补数据结构我建议的路径是线性表数组、链表、栈、队列 - 二叉查找树 - AVL 树旋转 - 红黑树插入 - 红黑树删除 - B 树和 B 树 - 堆和图再补常见排序算法和复杂度分析。这个顺序有一个好处就是每个阶段都在为下一个阶段铺路。理解 AVL 旋转之后红黑树的左旋右旋就是老朋友理解 2-3-4 树之后红黑树调整就是拆节点和合并节点。参考资料方面《算法导论》的红黑树章节是经典适合抠证明和完整代码JDK 源码里的 TreeMap 实际又短又清晰是学习生产级实现的好材料。可视化工具建议搜 Red-Black Tree Visualization 这类网页插入删除时能看到颜色和旋转的每一步变化比我截图给你讲十遍都有用。学习重点不是把代码背下来而是反复练习“当前节点处在什么状态该走哪个分支”。每次调整完检查一遍黑色路径是否恢复一致这比任何口诀都可靠。最后说点我的个人体会。第一次看红黑树删除的那四类情况我是真讨厌这棵树觉得它就是黑魔法。但后来把红黑树想成 2-3-4 树的二叉表示把删黑节点想成调整黑色高度突然一切都顺了。AVL 和红黑树并不是要你背旋转口诀而是要你理解“什么条件下树开始不平衡旋转为什么能让它恢复平衡”。这个理解一旦建立之后再去看 TreeMap、HashMap 里那些树相关代码你就不会觉得那是别人的逻辑而是你自己也能直接写出来的东西。学习数据结构的回报就在这里它不直接给你一个模板而是让你在遇到诡异问题时脑子里多一条清晰的排查路线。
阅读完成 · 觉得有帮助？
