JAVA-AVL 树与红黑树详解(一文看懂如何做到平衡？如何旋转？)

从二叉搜索树到自平衡AVL 树与红黑树详解目录一、为什么需要自平衡树二、AVL 树是什么三、AVL 树与 Java 集合的关系四、AVL 树的平衡策略四种旋转五、AVL 树的插入与删除六、红黑树是什么七、红黑树与 Java 集合的关系八、红黑树的平衡策略变色与旋转九、红黑树的插入与删除十、AVL 树与红黑树对比十一、我的总结一、为什么需要自平衡树我先把问题说清楚。二叉搜索树BST的规则很简单左子树上所有节点的值小于根节点右子树上所有节点的值大于根节点左右子树也分别是二叉搜索树。查找时从根一路比较下去每层排除一半理想情况下复杂度是O(log₂N)。但问题是——BST 的形状完全取决于插入顺序。比如同样是{1, 2, 3, 4, 5}一旦退化成单支树BST 的性能就彻底废了。所以核心问题是能不能让二叉搜索树在插入、删除的过程中自动保持平衡把高度控制在 O(logN)答案就是自平衡二叉搜索树。最经典的两套方案就是本文要讲的AVL 树严格平衡和红黑树近似平衡。二、AVL 树是什么AVL 树是最早发明的一种自平衡二叉搜索树由两位苏联数学家 G. M.Adelson-Velsky 和 E. M.Landis 在 1962 年提出名字就取自他们姓名的首字母。AVL 树一棵二叉搜索树且任意节点的左右子树高度差的绝对值不超过 1。为了让这个约束可量化我给每个节点引入平衡因子Balance FactorBFB F ( n o d e ) 左子树高度 − 右子树高度 BF(node) \text{左子树高度} - \text{右子树高度}BF(node)左子树高度−右子树高度AVL 树要求每个节点的BF ∈ {-1, 0, 1}一旦某个节点的 BF 变成±2就说明失衡了必须立刻通过旋转修复。举个直观的例子下面这棵树的节点3左高右低BF -2已经违反 AVL 性质AVL 树的高度结论设高度为 h 的 AVL 树最少需要 N(h) 个节点则有递推式N ( h ) N ( h − 1 ) N ( h − 2 ) 1 N(h) N(h-1) N(h-2) 1N(h)N(h−1)N(h−2)1这个递推的结果是 N(h) 关于 h 呈指数增长反过来可得h O(log₂N)。也就是说AVL 树的高度被严格锁死在 O(logN)查找、插入、删除都能稳定保持在 O(logN)。我理解的 AVL 树特点一句话总结它是一棵极度强迫症的 BST左右高度差一点都要旋转修正所以查询极快但维护成本高。三、AVL 树与 Java 集合的关系这一点我专门去查了结论有点出乎意料集合类底层结构是否用 AVLTreeMap红黑树❌TreeSet红黑树底层用 TreeMap 实现❌HashMap链表过长时红黑树❌也就是说Java 标准库中没有内置 AVL 树。java.util里的有序容器TreeMap/TreeSet底层用的是红黑树而不是 AVL 树。原因我后面会详细对比简单说就是AVL 树对平衡要求太严格插入/删除时旋转次数多红黑树稍微放宽了平衡条件牺牲一点查询效率换来大幅减少的旋转次数。对于TreeMap这种读写都频繁的场景红黑树的综合性价比更高。不过 AVL 树依然是必须掌握的知识它的旋转逻辑是红黑树、B 树等结构的基础面试也经常拿来和红黑树对比着问。四、AVL 树的平衡策略四种旋转AVL 树的灵魂就是旋转。失衡只有四种情况对应四种旋转。旋转的目标是在不破坏 BST 中序有序性的前提下把树拧回来。我的记忆口诀先看失衡节点往哪边歪再看它的孩子往哪边歪两个方向组合起来就确定了旋转类型。4.1 LL 型 —— 右单旋特征失衡节点左孩子的左子树过高。操作以z为轴做右旋——把y提上来当新根z挂到y的右边。4.2 RR 型 —— 左单旋特征失衡节点右孩子的右子树过高。LL 的镜像。操作以z为轴做左旋——把y提上来当新根z挂到y的左边。4.3 LR 型 —— 先左旋再右旋特征失衡节点左孩子的右子树过高。单旋解决不了需要双旋。关键点先对孩子y做左旋把它变成 LL 型再对失衡节点z做右旋。4.4 RL 型 —— 先右旋再左旋特征失衡节点右孩子的左子树过高。LR 的镜像。4.5 四种旋转总结类型失衡原因旋转方式记忆LL左孩子的左子树过高右单旋同向单旋RR右孩子的右子树过高左单旋同向单旋LR左孩子的右子树过高先左旋孩子再右旋自己异向双旋RL右孩子的左子树过高先右旋孩子再左旋自己异向双旋一句话记住方向相同用单旋方向相反用双旋“先旋孩子、再旋自己”。五、AVL 树的插入与删除5.1 插入操作插入其实分两步先按 BST 插入再回溯修复。完整流程按 BST 规则插入新节点一定插在叶子位置从插入点向上回溯到根依次更新每个祖先节点的高度 / 平衡因子一旦发现某个节点的|BF| 2判断它属于 LL / RR / LR / RL 哪种类型做对应旋转旋转后该子树高度恢复原状向上不再需要继续修复可以直接结束。举个走一遍的例子依次插入10, 20, 305.2 删除操作删除比插入更麻烦因为删除可能引发一路的连锁失衡。我把删除分成三种标准情况 回溯修复第一步按 BST 规则删除节点情况处理方式① 待删节点是叶子直接删除② 待删节点只有一个孩子用该孩子顶替它的位置③ 待删节点有两个孩子用左子树最大节点或右子树最小节点即中序前驱/后继替换它的值然后转去删除那个前驱/后继节点第二步从删除位置的父节点向上回溯逐层修复⚠️删除的一个重要区别删除修复不能像插入那样提前结束插入最多旋转一次就恢复但删除可能让祖先节点接连失衡必须一路回溯到根逐个判断修复。AVL 操作复杂度插入、删除、查找都是O(log₂N)算上旋转也只是常数级别。六、红黑树是什么如果说 AVL 树是强迫症那红黑树就是松弛感选手。它不要求严格的高度平衡而是通过给节点染色 几条规则保证最长路径不超过最短路径的 2 倍从而让树高维持在 O(logN)。红黑树一棵二叉搜索树每个节点额外带一个颜色属性红或黑并满足以下五条性质。红黑树的五条性质我背了很久每个节点要么是红色要么是黑色根节点必须是黑色所有叶子节点NIL 空节点都是黑色红色节点的子节点必须是黑色即不能有两个连续的红色节点从任一节点出发到其所有叶子节点的路径上黑色节点数目相同简称黑高相同。第 4、5 条是核心。第 4 条保证不会出现红红相连的长链第 5 条保证各路径黑色节点数一致——两条合起来就把最长路径红黑交替限制在了最短路径全黑的 2 倍以内。举个例子·表示黑色 NIL 叶子在红黑树里我们把从某节点到叶子的路径上黑色节点的个数称为该节点的黑高bh。一条关键结论最长路径 ≤ 2 × 最短路径 \text{最长路径} \le 2 \times \text{最短路径}最长路径≤2×最短路径因此红黑树的高度h ≤ 2·log₂(N1)依然是 O(logN)只是常数比 AVL 大一点。七、红黑树与 Java 集合的关系这是我在学 Map/Set 时印象最深的一点Java 集合类底层结构说明TreeMap红黑树按 key 有序查找 O(logN)TreeSet红黑树底层用TreeMap实现只存 keyHashMap数组 链表 红黑树链表长度 ≥ 8 且数组长度 ≥ 64 时链表转红黑树HashSet底层HashMap只存 key具体说几个细节TreeMap/TreeSetJava 中利用搜索树实现的Map/Set实际上用的就是红黑树——在二叉搜索树的基础上加上颜色以及红黑树性质验证。因为红黑树是近似平衡的所以能保证 O(logN) 的有序查找。HashMap默认是哈希桶开散列但当某个桶的链表长度超过阈值TREEIFY_THRESHOLD 8且数组容量达到 64 时就会把链表转换成红黑树把该桶的查找从 O(n) 优化到 O(logN)。所以红黑树在 Java 里的地位比 AVL 树重要得多是标准库的亲儿子。八、红黑树的平衡策略变色与旋转红黑树的平衡靠两个动作变色和旋转。旋转和 AVL 一样是左旋/右旋但红黑树的旋转次数远少于 AVL因为它更多靠变色来吸收不平衡。8.1 变色把节点由红变黑、或由黑变红用来满足性质 4、5。比如把红色节点染黑 → 增加了这条路径的黑节点数影响性质5 把黑色节点染红 → 减少黑节点数但要注意别和父节点撞红性质48.2 旋转左旋、右旋与 AVL 完全一致左旋 / 右旋的完整过程可回看 4.1 LL 型 和 4.2 RR 型 的配图。8.3 关键的叔叔节点概念红黑树插入修复时必须看叔叔节点父节点的兄弟的颜色这是判断处理方式的依据我记的口诀叔叔是红色→ 只变色爷爷变红往上递归叔叔是黑色或不存在→旋转 变色。九、红黑树的插入与删除9.1 插入操作第一步按 BST 规则插入新节点一律染成红色。为什么染红因为染红只会影响性质 4不能红红相连如果染黑会直接破坏性质 5黑高一致修复起来更麻烦。第二步从新节点向上修复。分情况讨论设新节点 N、父 P、爷爷 G、叔叔 U情况 1P 是黑色→ 无需任何操作直接结束 ✔情况 2P 是红色U 也是红色→只变色把 P、U 变黑G 变红然后把 G 当作新的当前节点继续向上检查因为 G 变红后可能和它的父亲撞红。情况 3P 是红色U 是黑色或不存在→旋转 变色这里再分P 是左孩子还是P 是右孩子以及N 是 P 的左孩子还是右孩子3a. LL 型P 是 G 的左孩子N 是 P 的左孩子—— 对 G 右旋3b. LR 型P 是 G 的左孩子N 是 P 的右孩子—— 先对 P 左旋再对 G 右旋3c / 3d. RR / RL 型—— 是上面两种的镜像分别是对 G 左旋和先对 P 右旋再对 G 左旋。和 AVL 的对比AVL 插入最多旋转 1 次双旋算 2 次红黑树插入最多旋转 2 次但可能多次变色。9.2 删除操作删除是红黑树最烧脑的部分我分了几个层次来理解。第一步按 BST 规则删除节点和 AVL 一样叶子 → 直接删只有一个孩子 → 孩子顶替两个孩子 → 用**中序后继右子树最小节点**的值替换转去删除后继节点。第二步判断是否需要修复这里有个关键点——删除的节点是什么颜色决定了要不要修被删除节点的颜色是否破坏性质处理红色不影响黑高也不会有红红相连直接删无需修复✔黑色该路径黑高 −1破坏性质 5需要修复⚠️被删节点是黑色时它所在的路径会少一个黑节点于是我们要把这个缺失的黑向兄弟借、或者往上递归——这就是所谓的**“双黑”Double Black**问题。第三步修复双黑问题设被删节点是 N此时 N 位于原来位置带着一个假想的黑兄弟节点是 S情况 A兄弟 S 是红色让 S 变黑、父节点变红然后对父节点旋转把 S 转成黑兄弟转化为下面的情况继续处理。情况 B兄弟 S 是黑色且 S 的两个孩子都是黑色把 S 染红让缺失的黑上移到父节点 P把 P 当作新的 N 继续向上递归。情况 C兄弟 S 是黑色且 S 至少有一个红色孩子进一步看红色孩子在 S 的哪一侧C1LL 型S 的左孩子红 → S 变父色、父变黑、S 左孩子变黑对 P右旋C2LR 型S 的右孩子红 → 先对 S 右旋转成 C1再按 C1 处理C3 / C4是 C1 / C2 的镜像。修复的终止条件双黑被完全消除遇到红色节点吸收掉或者递归到了根节点直接把根染黑结束。第四步根节点始终染黑不管修复过程如何最后都要保证根节点是黑色性质 2。删除复杂度红黑树删除最多旋转 3 次但变色可能一路传到根整体仍是O(logN)。相比之下 AVL 删除可能旋转 O(logN) 次这也是红黑树在写密集场景更受欢迎的原因。9.3 操作复杂度一览操作AVL 树红黑树查找O(logN)O(logN)常数略大插入O(logN)O(logN)删除O(logN)O(logN)插入旋转次数≤ 1 次双旋 2 次≤ 2 次删除旋转次数O(logN) 次≤ 3 次十、AVL 树与红黑树对比把这两者放一起对比我才能真正理解它们各自的定位对比维度AVL 树红黑树平衡标准严格|BF| ≤ 1近似最长路径 ≤ 2 × 最短路径树高更矮约 1.44 logN略高≤ 2 logN查找效率更快树更矮稍慢但同量级插入效率慢旋转多更快旋转少删除效率慢旋转可达 O(logN) 次更快旋转 ≤ 3 次适合场景查多写少如静态索引读写均衡 / 写多如通用容器实现难度旋转逻辑清晰但代码量大删除修复复杂但工程优化好Java 中的应用❌ 标准库未采用✅TreeMap/TreeSet/HashMap我的一句话理解AVL 树用更频繁的旋转换来更矮的树红黑树用更宽松的平衡换来更少的旋转。前者适合查询密集后者适合增删频繁。Java 选择了红黑树作为标准库的有序容器正是看中了它读写综合性能更均衡。十一、我的总结学完这两棵树我把自己最该记住的东西浓缩成下面几点关于本质AVL 树和红黑树都是自平衡二叉搜索树目的都是防止 BST 退化成链表二者的查找、插入、删除复杂度都是 O(logN)差别在平衡的严格程度与维护成本。关于 AVL 树核心指标是平衡因子 BF 左高 − 右高要求每个节点|BF| ≤ 1失衡分四种LL右单旋、RR左单旋、LR先左后右、RL先右后左记忆同向单旋异向双旋插入修复最多旋转一次即可结束删除修复可能连锁必须回溯到根。关于红黑树五条性质里最重要的是不能红红相连黑高一致→ 最长路径 ≤ 2 × 最短路径插入新节点默认染红修复看叔叔颜色叔叔红只变色叔叔黑才旋转删除只在被删节点是黑色时才需要修复核心是解决双黑问题Java 中TreeMap/TreeSet底层就是红黑树HashMap的桶在链表过长时也会转成红黑树。关于选择查询多、增删少 → AVL 树读写均衡、增删频繁 → 红黑树。这也是为什么我在看 Java 源码时看到的是红黑树而不是 AVL 树——工程上稳定可控的常数开销往往比理论上的最优更重要。这两棵树一开始确实容易绕晕建议一定要手动在纸上画几遍旋转过程画顺了自然就通了。如果这篇博客对你有帮助欢迎点赞收藏有问题也欢迎在评论区一起讨论如果文中哪里有理解偏差也欢迎指正我随时回来更新。