考研408的人几乎没有不认识2010年这道平衡二叉树选择题的。哪怕过去了这么多年它依然是数据结构科目里“平衡二叉树插入”最经典的一道真题。每年复习到AVL树的时候总有学生会拿着这道题来问我说选项里的LL、LR、RL、RR看着就头疼排列组合一样根本记不住。其实这道题并没有那么复杂。它就是一道披着“旋转”外衣的判断推理题核心考的是插入后如何确定失衡类型。只要搞清楚平衡因子怎么算、四种旋转分别对应什么结构特征再看到题目条件时能把它翻译成“新结点插在了哪棵子树的哪个方向”答案几乎是白送的。我当年备考的时候也在这道题上卡过很久后来把原理彻底捋了一遍才发现这类题就是这么点东西理清之后不光能秒杀这一题后面做红黑树、B树的插入调整思路都能顺带打通不少。这篇文章我会把2010年这道真题从题目条件到解题全过程拆开揉碎同时把平衡二叉树插入涉及的核心原理、四种旋转的形态判断、代码实现、常见坑点一次说清楚。不管你是刚开始复习408的小白还是已经在刷真题的二轮选手都能从中拿到可以直接用的方法。1. 2010年408第4题原题回顾与题型定位1.1 真题原题与选项设置先说题目本身。2010年408统考数据结构科目第4题题目大致是这样的在平衡二叉树中插入一个结点后造成了不平衡设最低不平衡结点为A并且已知A的左孩子的平衡因子为-1右孩子的平衡因子为0则应进行的调整是 。四个选项分别是LL型、LR型、RL型、RR型。如果你手头有真题册你可能会发现不同版本对“平衡因子”的定义略有差异——有的定义为左子树高度减去右子树高度有的定义为右子树高度减去左子树高度。2010年这道题采用的是左减右也就是平衡因子 左子树高度 - 右子树高度这个口径。这个口径一定要先确认否则后面推导方向完全会反掉。好消息是王道、天勤这些主流辅导书在这一题上口径是统一的。那道题的正确答案是LR型旋转也就是先对失衡结点的左孩子做一次左旋再对失衡结点做一次右旋俗称先左后右、双旋调整。我知道很多同学一上来就死记“LR型就是先左旋后右旋”结果做题的时候不是记反就是搞混最后干脆放弃这个知识点蒙一个。没必要记住背后的判断逻辑就不会乱。1.2 这道题到底在考什么这道题单从知识点归属上看考的是平衡二叉树AVL树的插入调整机制。但从考研命题的角度看它真正在考的其实是两件事第一你能不能根据插入后结点的平衡因子准确判断出新插入结点相对于失衡结点的方位第二你能不能把不同的失衡形态对应到正确的旋转操作上。这两件事恰恰是AVL树里面最容易出错的地方。很多人复习AVL树的时候只看旋转的图解觉得LL、RR就是“提上去一个结点”LR、RL就是“先转一下再提上去一个”看起来都懂但一到做题题目不会画图给你看只给你几个平衡因子数字你就不知道怎么用了。2010年第4题精准地戳中了这个痛点。另外这道题选在2010年也很有意思。那是408统考第二年命题组还在探索风格题目的整体难度比后来几年明显要温和一些。但正是在这种温和的年份命题人已经开始注意“不直接给树形图而是用平衡因子描述形态”这种出题方式了。后面几年凡是涉及AVL树的真题基本上都延续了这条思路只是改改数字、改改结点位置。所以把2010年第4题吃透等于提前掌握了这一类题目的命门。1.3 这道题的基本结论先给出来为了让后面读起来不悬着我先直接给出结论再慢慢展开推导题目说“最低不平衡结点为A”说明A是插入后从下往上找到的第一个平衡因子绝对值超过1的结点A的左孩子平衡因子为-1右孩子平衡因子为0因为A的左孩子平衡因子为负说明A的左子树往右偏再结合A本身的失衡方向可以判断新结点插在了A的左孩子的右子树上也就是LR型失衡对应先左旋后右旋的双旋调整。如果你现在看这个结论还觉得有点绕完全正常。下面我会从平衡因子的定义开始一步步把这件事讲透保证你看完之后再遇到同类题基本不用想太久就能写答案。2. 平衡二叉树插入的底层原理2.1 平衡因子与失衡判定要理解AVL树的插入调整第一步必须吃透“平衡因子”这个东西。所谓平衡因子就是一个结点左右子树高度之差。采用左减右口径时如果左子树比右子树高平衡因子为正如果右子树比左子树高平衡因子为负两棵子树一样高平衡因子就是0。AVL树规定任意结点的平衡因子绝对值不能超过1。也就是说平衡因子只能取-1、0、1这三个值一旦某个结点的平衡因子变成2或者-2整棵树就处于失衡状态需要立刻调整。平衡因子的绝对值为什么会超过1根因只有一个插入了一个新结点。因为插入一个叶子结点只可能让某个方向上的子树高度加1所以插入操作最多让某个祖先结点的平衡因子激动一下。如果这个“激动”超过了1失衡就产生了。这也正是为什么AVL树的插入调整不需要像删除那样麻烦只要沿着插入路径往上找找到第一个失衡的结点把它调整好整棵树就恢复了。注意一个细节题目里说的“最低不平衡结点A”这个“最低”不是高度最低而是离插入位置最近、但从下往上第一个平衡因子绝对值超过1的祖先结点。比如新结点插入后一直影响到根结点才失衡那最低不平衡结点可能是某个中间结点而不一定是根。调整AVL树的时候只需要对这个A做一次旋转A之上的所有祖先结点平衡因子会跟着自动恢复不需要逐层处理。这个原理听起来简单但很重要。2010年这道题问的就是“对A应做什么调整”所以你在判断的时候根本不需要管A上面还有什么结点只盯住A和它的下层子树关系就够了。2.2 四种失衡形态的本质接着来看四种失衡形态。LL型、LR型、RL型、RR型这四组字母很多人觉得难记其实它描述的是“新插入结点相对于失衡结点A的位置关系”而不是“旋转方向”。LL型新结点插在A的左孩子的左子树上。整棵左子树高且左子树自己也是左边高。形态上就是“一条直线向左下方延伸”也叫“左左”失衡。LL型用一次右旋就能解决。RR型对称情况新结点插在A的右孩子的右子树上整棵右子树高右子树也是右边高。形态上是一条向右下方的直线用一次左旋解决。LR型新结点插在A的左孩子的右子树上。A的左子树整体偏高但左子树内部是右子树更高形态上像一个先向左下方拐然后又向右下方拐的弯折不是直线。这种情况一次右旋解决不了必须先对A的左孩子做一次左旋把形态转化成LL型的样子再对A做右旋所以叫“先左后右”双旋。RL型对称情况。新结点插在A的右孩子的左子树上需要先对A的右孩子做右旋再对A做左旋叫“先右后左”双旋。我当年复习的时候用了一个特别生活化的类比帮助记忆失衡结点像一个重心不稳的人如果重心偏偏向左后方要往右扶一下如果重心先偏左又折向右光往右扶不行得先把这个“折”理顺。你不需要把这个类比背下来关键是理解“直线形态单旋解决折线形态双旋解决”这12个字的本质。为了更直观下面这张表把四种失衡形态和旋转策略对应起来复习的时候可以反复对照。失衡类型新结点位置相对于A形态特征调整方法操作次数LL型A的左孩子的左子树左子树内部左高对A右旋单旋RR型A的右孩子的右子树右子树内部右高对A左旋单旋LR型A的左孩子的右子树左子树内部右高先左旋A的左孩子再右旋A双旋RL型A的右孩子的左子树右子树内部左高先右旋A的右孩子再左旋A双旋表格看多了容易变成死记。我的建议是每次做这一类题的时候都先在草稿纸上画一棵简化的三角形树把结点位置标出来再对照上面的形态特征来判断做上十几道题自然就形成条件反射了。2.3 为什么新结点位置决定旋转方式一定有同学会问直接记住“LL单旋、LR双旋”不就行了吗为什么非要理解新结点位置答案很简单因为考题不会直接告诉你新结点插在哪它只会给你平衡因子让你自己推断位置。而平衡因子恰好能准确反映新结点的方位。一个结点的平衡因子等于左子树高度减右子树高度。如果失衡结点A的平衡因子为正说明A的左子树更高问题大概率出在A的左边如果为负说明A的右子树更高问题出在右边。然后继续看A的左孩子或右孩子的平衡因子二次判断失衡方向如果A的左孩子平衡因子为正说明左孩子的左子树高综合起来就是左左也就是LL型如果A的左孩子平衡因子为负说明左孩子的右子树高综合起来就是左右也就是LR型。这就是做题的完整逻辑链。2010年第4题里A的平衡因子题目没有直接说但既然A是“最低不平衡结点”它的平衡因子绝对值必然大于1。结合A的左孩子平衡因子为-1右孩子平衡因子为0你就可以反推A的平衡因子应该是2——因为只有A的左子树明显偏高它的左孩子的右子树才会在插入后变成-1而A的右孩子保持0不变。A是2左孩子是-1属于典型的左子树内部右偏即LR型。我再用一句话帮你串一遍这个过程失衡结点告诉你问题在左还是在右失衡结点的孩子告诉你问题在这个方向的内部是偏左还是偏右两者一组合四个类型就区分开了。这就是整个判断方法的核心也是下面解题过程中要用的武器。3. 真题的完整解题过程3.1 条件翻译把平衡因子变成旋转判断先把2010年第4题的关键条件列出来最低不平衡结点是A说明存在某个插入后失衡的子树以A为根A的左孩子平衡因子为-1A的右孩子平衡因子为0。逐条翻译。第一A是失衡结点所以A的平衡因子只能是2或-2绝对值超过1。题目说A的左孩子平衡因子是-1这就基本排除了A的平衡因子为-2的可能。为什么如果A的平衡因子是-2说明A的右子树比左子树高出2层失衡源头在右边这种情况下A的左孩子平衡因子不太可能成为判断依据的核心。更重要的是A的右孩子平衡因子为0说明右子树内部高度平衡并没有插入导致高度变化。统观全局失衡源头指向A的左子树。因此A的平衡因子只能是2即A的左子树比右子树高2层。这时候再问A的左子树为什么比右子树高2层因为新结点插入到了A的左子树方向让原本就偏高的左子树更高了。好那么问题聚焦到A的左孩子身上。第二A的左孩子平衡因子为-1用左减右口径翻译过来就是A的左孩子的右子树比左子树高1层。这说明什么说明新插入的结点位于A的左孩子的右子树方向。A的左孩子本身还是平衡的-1在合法范围内只是内部偏向右边。把这两句话拼到一起新结点插在A的左子树方向同时插在A的左孩子的右子树方向。整体来看新结点位于A的左孩子的右子树上这就是标准的LR型失衡。第三选出对应调整方式。LR型对应的调整是先对失衡结点的左孩子做左旋再对失衡结点做右旋也就是先左后右的双旋调整。所以这道题选LR型。3.2 题型变体换一组数字还是同一套打法真题做多了你就会发现这种题特别喜欢换数字考。比如把题目改成“A的左孩子平衡因子为1右孩子平衡因子为0”那答案就变成了LL型如果改成“A的平衡因子为-2A的右孩子平衡因子为1”那答案就是RL型。数字变了但推理框架完全一样。我建议你遇到这种变体时不要直接背答案而是用这套完整的推理路径走一遍。下面拿一个变体做示例。变体题在平衡二叉树中插入一个结点后造成了不平衡设最低不平衡结点为A并且已知A的右孩子的平衡因子为1左孩子的平衡因子为0则应进行的调整是翻译过程A失衡平衡因子绝对值大于1。A的左孩子平衡因子为0说明左边内部没有异常A的右孩子平衡因子为1说明右子树内部左高。综合判断问题出在A的右子树方向并且是右子树的左子树方向也就是新结点插在A的右孩子的左子树上对应RL型失衡。调整方式是先对A的右孩子做右旋再对A做左旋先右后左双旋。看只要掌握“失衡结点定左右孩子结点定内外”这句话再难的变体都能拆。我把这句话写在笔记扉页上考试前反复默念几遍比背十种题型都管用。3.3 动手验证把抽象条件还原成一棵树如果你还不放心可以在草稿纸上把抽象的条件还原成一棵具体的树亲手旋转一遍看最后是否恢复平衡。怎么还原先预设一棵只有三个关键结点的简化AVL树A是根A有左孩子B和右孩子C。已知C的平衡因子为0说明C的两棵子树等高。B的平衡因子为-1说明B有右孩子D但可能没有左孩子或者左子树比右子树低1。为了让树在插入前保持平衡A的平衡因子原本应该是0或1插入一个结点进入B的右子树后B的平衡因子变成-1A的平衡因子变成2触发失衡。在纸上画出来A的左子树已经比右子树高出2层并且B的右子树比左子树高1层。这时候直接对A做右旋是行不通的因为B的右子树下探了一层直接提B上去会导致B的右子树D无法安放。必须先对B做左旋把B的右子树D提上来让B的左子树变高形态变成LL型再对A做右旋整棵树就恢复了平衡。这么亲手画一遍之后你就完全理解为什么LR型不能简化为一个旋转而必须是先左后右两个旋转了。很多网课动图画得很快你看着觉得懂了实际上没跟上中间形态的变换过程。我强烈建议你自己手画一遍比看十遍动图都管用。4. 四种旋转方式的实操图解与代码实现4.1 LL型与RR型的单旋细节旋转操作本身不复杂但细节容易出错。先说LL型的右旋。假设失衡结点为AA的左孩子为BB的左孩子为C新结点的位置使C子树增高。右旋的目标是把B提到A的位置A变成B的右孩子B原来的右子树变成A的左子树。这个“B原来的右子树”是整棵旋转中最容易丢失的部分千万别忘了它。用文字描述就是B的右子树挂在A的左边。代码上就三步先暂存B的右子树再把A作为B的右孩子最后把B原来的右子树挂到A的左孩子位置。完成后返回B作为新的子树根。右旋之后整棵子树的高度比原来降低一层平衡恢复。RR型完全对称做左旋。失衡结点A的右孩子BB的右孩子C增高。左旋时B上位A变成B的左孩子B原来的左子树变成A的右子树。同样三步走方向反转。单旋为什么只需要一次本质原因在于失衡路径是一条直线直线形态下把中间的结点往上提一层其余结点的相对位置可以直接平移过去不需要额外的形态转换。这也解释了为什么单旋的操作代码那么短连多余的判断都不需要。4.2 LR型与RL型的双旋执行顺序双旋就是两次单旋的组合但顺序有讲究。LR型是“先左旋A的左孩子再右旋A”。注意第一次旋转的对象不是A而是A的左孩子B。对B左旋之后B的右孩子上位成了A左子树的新根子树形态从“折线”变成“直线”也就是变成LL型紧接着再对A执行一次右旋。这里有个特别容易犯的错有人会把LR型记成“先右旋再左旋”结果整棵树越旋越歪。判断顺序只需要记住一个原则第一旋的作用是“把折线段掰直”第二旋才是真正的平衡调整。LR型既然折点在左侧第一步就必须在左侧内部先掰直也就是对左孩子左旋然后整体已经变成LL直线形态再对A右旋。反过来RL型就是先对右孩子右旋掰直再对A左旋。如果你怕混淆可以用一个笨办法死记“LR L R先执行左边那个操作”。LR型先执行L也就是左旋作用在左孩子上之后执行R也就是右旋作用在失衡结点上。RL型先执行R也就是右旋作用在右孩子上之后执行L也就是左旋作用在失衡结点上。这个方法虽然不是原理层面的理解但应急和自检非常好用。4.3 AVL插入调整的C语言参考实现下面的代码是我结合考研常见代码风格整理的一份核心调整实现只包含旋转相关的函数可以直接用来对照理解。实际考试不要求写出完整AVL实现但对理解题目大有帮助。typedef struct AVLNode { int data; int height; // 结点高度 struct AVLNode *left, *right; } AVLNode; // 获取结点高度 int getHeight(AVLNode *p) { if (p NULL) return 0; return p-height; } // 计算平衡因子左减右 int getBalance(AVLNode *p) { if (p NULL) return 0; return getHeight(p-left) - getHeight(p-right); } // 更新结点高度 void updateHeight(AVLNode *p) { int lh getHeight(p-left); int rh getHeight(p-right); p-height (lh rh ? lh : rh) 1; } // 右旋 AVLNode *rotateRight(AVLNode *A) { AVLNode *B A-left; AVLNode *BRight B-right; B-right A; A-left BRight; updateHeight(A); updateHeight(B); return B; } // 左旋 AVLNode *rotateLeft(AVLNode *A) { AVLNode *B A-right; AVLNode *BLeft B-left; B-left A; A-right BLeft; updateHeight(A); updateHeight(B); return B; } // 插入后恢复平衡 AVLNode *rebalance(AVLNode *A) { updateHeight(A); int balance getBalance(A); if (balance 1) { // 左子树高 if (getBalance(A-left) 0) { // LL型 return rotateRight(A); } else { // LR型 A-left rotateLeft(A-left); return rotateRight(A); } } if (balance -1) { // 右子树高 if (getBalance(A-right) 0) { // RR型 return rotateLeft(A); } else { // RL型 A-right rotateRight(A-right); return rotateLeft(A); } } return A; }这段代码的关键判断在rebalance函数里先看A的平衡因子大于1还是小于-1确定问题是左还是右然后看子树的平衡因子符号确定是“直”还是“折”。这个判断逻辑就是前面讲的“失衡结点定左右孩子结点定内外”的代码化表达。把这段代码吃透你代码能力也能顺手提升408大题万一考到AVL相关算法设计你也有话可写。4.4 用具体序列走一遍LR型插入过程光看代码还是不够直观我拿一个完整的插入序列走流程。假设初始空的AVL树依次插入3020401025。前三次插入后树还是平衡的30为根20为左孩子40为右孩子三个结点高度分别为2、1、1。插入10之后10挂在20的左孩子位置20的平衡因子变成130的平衡因子变成1整棵树依然平衡。插入25的时候25挂在20的右孩子位置可以挂在20的右边比20大但比30小这时候20的平衡因子从1变成0还是1需要具体算。实际插入后20拥有左孩子10和右孩子25两棵子树高度相等平衡因子0但30的左孩子20这棵子树高度变成2右孩子40高度130的平衡因子变成1仍然平衡。这个序列没有触发失衡于是换一个序列30204025。插入25后25挂在20的右孩子位置。此时20左子树为空、右子树为25平衡因子-130的左子树高度2右子树高度1平衡因子1整棵树仍然平衡。好那再插入28试试28挂在25的右孩子25高度变成220的左子树空、右子树25高度2平衡因子-220首先失衡。从20角度看20的左孩子空、右孩子25新结点插在25的右子树方向属于RR型失衡对20左旋。调整后20的右孩子25上提为根25的左孩子20、右孩子28平衡恢复。30的左子树仍然高度2整体平衡。我在备课的时候试过很多序列发现一个规律想精准触发出LR型失衡关键是让插入位置落在左孩子的右子树方向。比如序列45305020354860中插入35后可能触发。这类手推练习不需要做太多我建议你认真推三个不同序列分别触发LL、RR、LR各一次就足够建立手感了。光看不练到考场上还是容易手生。5. 408备考中的常见坑与解题模板5.1 判断旋转类型的三步法根据我自己的备考经验和给学弟学妹答疑时反复讲的套路做这一类题可以归纳为一个固定三步法。第一步找失衡结点A。题目明确给出“最低不平衡结点”就直接用没给就沿着插入路径从新结点往祖先方向找第一个平衡因子绝对值大于1的结点。第二步看失衡结点A的平衡因子正负。正说明左子树高问题在左侧负说明右子树高问题在右侧。这一步确定第一个字母是L还是R。第三步看A的孩子中偏高那个子树的平衡因子符号。如果问题在左边就看A的左孩子左孩子平衡因子非负说明左孩子的左子树高或等高新结点落在左左方向属于LL型左孩子平衡因子为负说明右子树高新结点落在左右方向属于LR型。问题在右边时镜像处理。三步走完字母组合自然出来了。第四步才是对应旋转方向LL右旋、RR左旋、LR先左后右、RL先右后左。这个三步法听起来简单但它真的能救命。考试的时候时间紧张人容易慌一旦你发现自己开始纠结某个选项立刻停下来按这三步重新过一遍通常半分钟就能把正确答案拎出来。5.2 平衡因子口径问题408的教材体系默认平衡因子为左子树高度减右子树高度但很多地方参考书、网课以及互联网上流传的资料会采用右子树高度减左子树高度的口径。同一个题目用不同口径去套答案是相反的。2010年这道真题按左减右口径答案是LR型如果你用右减左口径去分析会发现结论倒过来变成RL型那么理解就出大问题了。怎么避免这个坑做题之前先确认你手上的资料采用的口径然后整份真题卷都保持同一个口径。千万不要中途换。好在408统考真题本身沿用的是严蔚敏教材体系也就是左减右所以备考阶段按这个口径统一即可。另外这个坑在代码实现上也有体现。有些同学的代码用getHeight左减右算平衡因子但在判断LR型时不小心写成getBalance(A-left) 0才右旋这种符号上的小错非常隐蔽编译不会报错运行结果看似正常但插入某些序列后树会悄悄失衡。我在写代码的时候习惯在注释里显式写清楚“左减右为负说明右高”防止自己过两天忘掉。5.3 历年同类题扩展与练习方向只做2010年这一道题肯定是不够的。我建议把历年408中涉及AVL树的题目全部拉出来集中刷一遍重点看2011年之后有没有类似的平衡因子判断题、选择题以及2009年的树形结构综合题。虽然每年AVL直接命题的频率不算特别高但它作为基础知识点经常穿插在其他考点里比如和排序、查找结合出综合题。如果你想刻意训练还可以自己出题。方法很简单先任意构造一棵平衡二叉树选定某个结点A插入一个新结点插到A的左孩子的右子树方向然后计算失衡后各关键结点的平衡因子把题目改成“A的左孩子平衡因子是多少、右孩子平衡因子是多少应做什么调整”再对比答案。这样出上三五道题你基本就变成这一类题型的老手了。我当年备考时做了好几组这样的自问自答效果比盲目刷题要好很多。练习的方向也不要只盯选择题。408统考的大题偶尔也会涉及树的高度调整逻辑虽然写法上不要求你写完整的AVL代码但如果你能在算法设计题里用上旋转调整的思想并写出伪代码阅卷时会很加分。5.4 实际备考安排建议平衡二叉树插入这个知识点放在整个408复习进度里通常是在第一轮数据结构复习的中后期接触在第二轮刷真题阶段要完全吃透。我个人的建议是第一轮只要求理解四种旋转的形态和判断方法能做对教材后的基础习题第二轮开始集中做真题分类汇编把2010年第4题这类题目按年份排在一起对比着看第三轮冲刺阶段再回过头来看一眼本节的三步法和易错点就足够了。时间安排上第一轮大概花2到3天足够因为AVL树插入的代码量不大重点在理解第二轮做真题时注意控制单题时间这类题理想情况下30秒内要出答案超过1分钟说明判断方法还不熟需要回头重新梳理形态特征而不是盲目刷量。还有一个小技巧考前冲刺时可以把四种旋转形态画成一页纸的笔记随身带着。不是让你背图而是帮助你形成视觉记忆。等你在考场上看到平衡因子数字时能条件反射地联想到对应的树形速度和准确率都会提升一大截。6. 常见问题与排查技巧实录6.1 总是分不清LR和RL怎么办我见过太多学生问这个问题包括我自己当年也绕了好一阵。最有效的解决办法不是背字母而是每次做判断时先画一个最简单的三层树。画法很简单失衡结点画在最上面第二层画一个孩子结点第三层用箭头标出新插入结点的位置。只要画出来是直线还是折线一目了然答案自然水落石出。比如LR型新结点在A的左孩子右侧画出来A到左孩子是左下方线左孩子再到新结点是右下方线整条路径是一个“V”形先左后右的折线这种折线要双旋。RL型对称是一个先右后左的折线。画这么一棵简化树花不了十秒钟但能为你节省下纠结的好几分钟。考试时不要吝啬这几秒钟。6.2 插入后多个结点失衡怎么处理严格来说AVL树插入只需要处理一个失衡结点也就是最低不平衡结点A。但有的同学在做题时会遇到一种情况插入后不只一个结点的平衡因子绝对值超过1比如祖父和父亲都变成2这时候应该调整哪个调整最下面那个A。因为旋转以A为根的子树的整体高度会降低一层A之上的所有失衡结点都会因子树高度恢复而自动回到合法范围。这个结论在AVL树里是成立的前提是你找的是“最低”的那个失衡结点而不是任意一个失衡结点。如果题目给的不是“最低不平衡结点”而是笼统说“某个结点失衡”那就要先找到最低的那个再判断类型。2010年第4题直接给了最低不平衡结点A四十就不折腾了。但如果真题换了说法你就得保留这个心眼。6.3 平衡树插入后高度一定会降一层吗不一定。单旋或双旋的核心作用是把失衡子树的高度从“插入后的异常高度”恢复到“插入前的高度”而不是无条件降一层。比如插入前A子树高度为h插入后A子树高度变成h2失衡旋转后高度恢复为h。如果插入前后高度没有变化就需要重新检查是不是找错了失衡结点或者题目给的平衡因子与树形不匹配。这个细节在代码层面表现为旋转后一定要更新结点高度而且要先更新下面结点的height再更新上面结点的height。顺序反了代码会出错或者影响后续比较。我的代码里rotateRight先updateHeight(A)再updateHeight(B)这步顺序很多人会弄反调了几次bug之后才注意到这个小问题。6.4 相关扩展知识点要不要学AVL树只是平衡树大家庭的一员408考纲里还涉及红黑树、B树等。很多同学纠结要不要把红黑树也学得和多深。我的看法是408笔试阶段红黑树主要以概念辨析为主不太会要求手写红黑树删除调整代码。但AVL的旋转思想对理解红黑树的旋转操作有很大帮助因为红黑树的左旋、右旋本质上和AVL树的旋转是同一套操作逻辑。所以我的建议是先把AVL树的插入调整吃透理解旋转的形态判断和方向规则然后去对比红黑树的插入调整。你会发现红黑树的旋转虽然多了一个“颜色调整”但形态判断的思路是一致的。这样一来你历年真题里那些看似独立的红黑树小题也能串起来记。6.5 一道自测题验证掌握程度分享一道我经常拿来检验学弟学妹的变体题你可以测一下自己是否真的掌握了。某平衡二叉树插入一个结点后失去平衡已知最低不平衡结点A的平衡因子为-2A的右孩子的平衡因子为1A的左孩子平衡因子为0问需要进行哪种旋转调整按照三步法走一遍A的平衡因子-2说明右子树更高问题在右侧第一个字母是R右孩子平衡因子为1说明右孩子的左子树更高新结点落在右孩子的左子树方向第二个字母是L于是是RL型调整方式是先对A的右孩子做右旋再对A做左旋。如果这道题你能毫不犹豫地说出答案和推理过程说明你已经完全掌握了这套题型的解法。这类“换一个方向再把答案写出来”的自测比盲目做十道重复题有价值得多。我备考期间就是用这种办法把高频题型全部过了一遍到了考场上碰到类似的平衡因子数字组合基本就是秒杀。AVL树的插入调整是那种“原理懂了就很简单原理没懂就全靠蒙”的知识点。我自己从最初看着LL、RR、LR、RL四个字母头大到现在看到平衡因子组合就能条件反射写出旋转顺序中间隔的就是彻底理解那层窗户纸。希望这篇文章能帮你把这层纸捅破。如果在实际做题中遇到了新的变体欢迎按三步法自己推演一遍相信你会回来感谢这个方法的。