1. 从AVL到红黑树为什么这两棵树总是绑在一起考考研408的数据结构部分树这个章节历来是出题的重灾区。而在树的所有考点里平衡二叉树和红黑树又是一对“黄金搭档”——几乎每年都有学校在这两个知识点上做文章要么考概念性质要么考插入删除的过程模拟要么放在综合题里让你分析复杂度。先说个很多人问过的问题既然有了平衡二叉树为什么还要搞出个红黑树这两个东西到底有什么区别我用一句大白话回答平衡二叉树管得太严红黑树管得刚刚好。平衡二叉树要求任何节点的左右子树高度差绝对值不超过1这个约束非常严格导致每次插入或删除之后很可能需要一路回溯到根节点做多次旋转来恢复平衡。更“烦人”的是删除操作在AVL里实现起来异常麻烦你刚把左旋右旋搞清楚换个删除场景又懵了。红黑树就不一样它不追求严格的高度差限制而是用“节点颜色”和一组相对宽松的规则把树的高度控制在(O(\log n))级别。从根到叶子的最长路径最多是最短路径的两倍这个“约等于平衡”的性质让红黑树在插入删除时旋转次数明显更少整体性能更稳定。这也是为什么C STL里的map、setJava里的TreeMap、TreeSet底层全是红黑树而不是AVL。所以408考官的思路很清晰**AVL考的是你对平衡机制的理解红黑树考的是你对工业级数据结构设计的认知。**两棵树放在一天复习本质上就是在训练你“同一目标下不同约束策略”的对比思维。2. 平衡二叉树四种旋转与一条不能破的底线2.1 什么情况下必须旋转先复习一个最基础的定义平衡因子Balance Factor等于左子树高度减去右子树高度取值只能是-1、0、1。一旦某个节点的平衡因子绝对值超过1这棵树就失衡了必须通过旋转恢复。旋转虽然看起来有左旋、右旋、先左后右、先右后左四种但它们的触发条件是固定的逻辑也完全可以归成一类。我建议你不要死记四种旋转的流程而是抓住一个核心原则找最小不平衡子树沿着插入路径确定“方向”然后对着方向转。举个例子。假设插入节点后某个节点A的平衡因子变成2说明左子树比右子树高。此时要看A的左孩子B的平衡因子如果B的平衡因子是1说明新节点插在B的左子树上属于LL型对A做一次右旋。如果B的平衡因子是-1说明新节点插在B的右子树上属于LR型先对B做左旋再对A做右旋。反过来A的平衡因子变成-2时就看右孩子C的平衡因子对称处理即可。RR型直接左旋RL型先右旋再左旋。这里有个非常容易踩的坑**判断LR和RL时看的不是新节点在哪个子树而是失衡节点孩子的平衡因子。**很多人因为搞混这一步把LR当LL处理转完发现树还是歪的。2.2 插入过程全模拟用一个具体数字序列走一遍光讲理论没用我给你走一个完整的插入模拟。现在往空树里依次插入50, 30, 80, 20, 35, 33。第一步插入50、30、80都很正常。50是根30是50的左孩子80是50的右孩子此时平衡因子全部为0。第二步插入20。20比30小成为30的左孩子。此时节点50的左子树高度变成2右子树高度为1平衡因子为1没超限。节点30呢左子树高度1右子树0平衡因子1也没问题。第三步插入35。35比30大比50小成为30的右孩子。注意看现在节点30的左子树高度220在下面右子树高度135在下面平衡因子1正常。但节点50的左子树高度变成2右子树高度1平衡因子还是1也正常不对你再仔细算——30的左子树下还有2030的右子树下有35所以50的左子树高度是2右子树高度是1平衡因子是1确实没超。第四步插入33。33比30大比35小成为35的左孩子。此时检查各节点平衡因子节点30左子树高度220右子树高度235下面挂33平衡因子0。节点50左子树高度3不对左子树根是3030的高度是2因为30的右子树35下面还有33所以50的左子树高度是3右子树高度是1平衡因子变成2失衡了。好现在找到最小不平衡子树根是50。50的平衡因子是2左孩子30的平衡因子是0。这里注意LL和LR的判断看的是左孩子的平衡因子30的平衡因子是0但实际插入在30的右子树上所以是LR型。也就是说当失衡节点左孩子的平衡因子为-1或0时如果插入方向实际在右子树必须按LR处理。于是先对30做左旋30的右孩子35提上来35的左孩子33变成30的右孩子。旋转后35变成50的左孩子30变成35的左孩子33还是30的右孩子。然后对50做右旋35提为根50变成35的右孩子30还是35的左孩子33留在30的右子树。最终树的结构是35为根左孩子3030的左孩子20、右孩子33右孩子5050的左孩子为空、右孩子80。检查一遍平衡因子35的左右高度都是2平衡因子030左右高度都是1平衡因子050左右高度0和1平衡因子-1。完美。这个过程看起来繁琐但你只要记住“失衡就沿插入路径向上找第一个平衡因子绝对值大于1的节点再看它的孩子的平衡因子定旋转类型”就能应对所有插入题。2.3 平衡二叉树的高度与ASL计算除了旋转408还喜欢考平衡二叉树的最大高度和查找成功的平均查找长度。结论先记住**含有n个节点的平衡二叉树的最大深度不超过(\lfloor \log_2 n \rfloor 1)但更精确的估算要用斐波那契数列。**设(N_h)表示高度为h的平衡二叉树的最少节点数则(N_00)(N_11)(N_hN_{h-1}N_{h-2}1)。这道题的典型出处是王道和李春葆教材上的习题高度为8的平衡二叉树最少有多少个节点按递推算(N_2N_1N_012)(N_34)(N_47)(N_512)(N_620)(N_733)(N_854)。所以答案至少是54个节点。为什么这个结论重要因为它直接关联到“平衡二叉树能把最坏查找时间控制在(O(\log n))”这个核心考点。如果不加限制一棵二叉树可能退化成链表查找复杂度变成(O(n))。而平衡二叉树的节点数按斐波那契规律增长反过来就是高度被牢牢限制在对数级别。ASL的计算题就老老实实把树画出来逐层累加“层数×该层节点数”再除以总节点数。需要警惕的是408有时候会把“成功查找ASL”和“失败查找ASL”混在一起考。失败ASL是对所有外部节点也就是空指针位置做累加很多人漏算这个维度丢分很冤。2.4 删除操作与失衡调整的“连坐机制”删除比插入麻烦的地方在于删除一个节点可能导致多个祖先同时失衡而且调整完局部上层可能又失衡了。408在这里的出题风格是给一棵现成的平衡二叉树删除某个节点问你最终树的形态。我的处理思路分三步按二叉排序树的删除规则把目标节点删掉。三种情况叶子直接删只有一个孩子就让孩子顶上来有两个孩子就用前驱或后继替换。从被删节点的父节点开始向上逐个检查平衡因子找到第一个失衡的节点。对失衡节点按插入时的四种旋转方式调整调整完后继续向上检查直到根节点。这里有个我当年踩过的坑**删除时如果用前驱替换前驱可能在左子树深处删除前驱后失衡点可能出现在左子树的根往上多层的某个位置而不是紧挨着替换位置的那个节点。**所以很多题看起来旋转方向很怪其实就是因为失衡点不是明面上那个“替换后”的节点。说到底AVL的删除是没有捷径的必须一遍遍画图模拟。我建议你至少亲手画掉10道删除调整题形成肌肉记忆后再上考场。3. 红黑树五条性质里藏着全部逻辑3.1 五条性质逐条翻译成人话红黑树的定义很抽象五条性质摆在那里每个节点不是红色就是黑色。根节点是黑色。所有叶子节点NIL都是黑色。红色节点的两个子节点必须是黑色也就是说不能出现连续两个红色节点。从任一节点到其每个叶子节点的所有路径包含相同数目的黑色节点称为黑高相等。很多人背得很熟但做题还是废。问题在于没有理解这五条性质的用途。性质4和性质5是一对配合性质4限制了红色节点不能连续出现性质5限制了所有路径的黑高必须相等。把这两条合起来就能推导出红黑树最重要的结论——最长路径不超过最短路径的两倍。为什么最短路径全是黑节点设黑高为h最长路径因为不能出现连续红色最多只能是黑红黑红交替长度不超过2h。所以整棵树的高度不超过(2\log_2(n1))查找复杂度依然是对数级这就是红黑树“弱平衡”的数学基础。性质3里的NIL叶子节点很多人第一次看到会懵。这里说的叶子不是我们平时理解的“没有孩子的节点”而是每个节点的空指针都要当作一个虚拟的黑色叶子。这个概念在处理红黑树插入和删除时很关键因为性质5的“每条路径”是算到NIL节点的。我见过不少同学问既然所有NIL都是黑色那红色节点的NIL子节点算不算违反性质4答案是不算性质4说的是“红色节点的两个子节点必须是黑色”NIL就是黑色自然满足。3.2 插入的三种修正比想象中好记红黑树的插入规则一句话概括新插入的节点先涂成红色然后从父节点开始检查是否违反性质。为什么新节点要涂红因为涂红至少能保证性质5暂时不破你只需要对付性质4。如果涂黑所有路径的黑高全变了调整范围瞬间失控。插入后根据父节点的颜色分三种情况第一种父节点是黑色。恭喜什么都没违反直接结束。第二种父节点是红色且叔叔节点是红色。此时爷爷节点必然是黑色否则早就违反性质4了。修正方法是把父节点和叔叔节点都变成黑色把爷爷节点变成红色。然后以爷爷节点为“新插入节点”继续向上检查。第三种父节点是红色叔叔节点是黑色或者NIL。此时需要做旋转规则和AVL的旋转一模一样如果当前节点、父节点、爷爷节点三者形成“直线”转一次形成“折线”先转一次变成直线再转一次。转完之后把爷爷节点变红原来的父节点或者折线转完后那个提上来的节点变黑。这里有一个细节容易被忽略**叔叔是NIL节点时也按“黑色”处理。**很多题目给的红黑树图中NIL不画出来导致叔叔位置看起来是空的有些人就不知道该归到哪种情况。记住空就是黑归到第三种。具体走一个例子往空的红黑树插入10, 20, 30。插入10根节点涂红但根必须黑所以直接涂黑完成。插入20涂红。20的父节点10是黑的不用调整结构是10黑的右孩子是20红。插入30涂红。父节点20是红色叔叔节点是20的兄弟位置上的NIL黑色所以属于第三种。三个节点10、20、30形成右右直线对10做左旋旋转后20上提为根10变左孩子30变右孩子。接着改色20变黑10和30变红。最终20为黑根左右红孩子满足全部性质。如果继续插入更多节点就会触发第二种情况叔叔为红需要把父叔变黑、爷爷变红再向上递归。这个过程和AVL的“向上回溯查失衡”一样思路是相通的。3.3 为什么考试重点偏向插入而不是删除我翻了近十年的408真题和各校自命题发现一个规律平衡二叉树的删除题偶尔出现红黑树的删除题几乎不考。原因很现实。红黑树的删除修正情况比插入更复杂总共分四种情况还要涉及“双黑”“兄弟节点旋转”等概念在笔试有限时间内画完整棵树的状态变化对命题人来说也很难控制难度和区分度。那备考要不要完全放弃红黑树删除我的建议是**把删除的“思想”理解到位但不必死记四种情况的完整流程。**你至少要清楚红黑树删除节点后如果破坏了性质5通常是因为“被删的黑色节点导致某条路径黑高少1”需要把问题向上传递通过兄弟节点与叔侄的颜色变化和旋转来恢复。这个“向上传递黑色缺失”的思想和AVL删除的向上检查本质一致理解了就不慌。408考察红黑树的常见姿势还是给一棵树判断是不是红黑树、给插入序列让你画出最终红黑树、给定红黑树的黑色高度问最多/最少节点数。这三类题用五条性质和插入规则就能解决性价比很高。3.4 基于黑高的节点数估算题红黑树最少节点数全部为黑色且尽可能紧凑。若黑高为h根据性质5所有路径黑高相等为了让总节点数最少应该只有一条路径并且这条路径上全是黑节点共有h个节点不对这里要小心根节点的黑高算1还是算0不同教材可能略有差异。按408的惯例黑高是从某节点出发到达叶子NIL路径上黑色节点的数量不包含该节点本身。那么一棵红黑树若黑高为h最少节点数是(2^h-1)也就是一棵全黑满二叉树加一层其实准确说高度为h的“完全黑色二叉树”节点数为(2^h-1)但红黑树可以没有红色节点所以最少就是全黑满二叉树。最多节点数呢为了让节点尽可能多在保持黑高h的前提下每条路径可以插入红色节点但红节点不能连续。所以红黑相间相当于每两个黑节点之间最多夹一个红节点总高度最多(2h)。高度上限(2h)的满二叉树节点数为(2^{2h}-1)但首尾颜色有约束实际最密的情况是“黑-红交替”的满二叉树节点数介于(2^{2h}-1)和某个值之间。真题通常只问“最少”因为最少的推导干净利落最多的情况容易扯皮。备考时把最少结论记牢最多的极限理解成“不超过(2^{2h}-1)”即可。这里我要吐槽一个很多资料上的错误有人说红黑树最少节点数是(2h-1)这是不对的。(2h-1)对应的是一种“每层只含一个黑色节点、红节点穿插在中间”的路径式结构但这不是红黑树的节点数下限。用黑高为2举例最少节点数是3根黑左黑右黑构成一个根加两个孩子的全黑树。如果只有1个根节点再加1个黑孩子那另一条到NIL的路径黑高只有1违反性质5。所以“父子之间不能缺少黑节点”这个约束决定了最少时也必须形成完整的满二叉树形态。4. AVL与红黑树的正面交锋一张表看清所有区别我把408最常考的几个对比维度整理成一张表考前最后一天扫一眼就能回想起来对比维度平衡二叉树AVL红黑树RB-Tree平衡标准任意节点左右子树高度差≤1最长路径不超过最短路径2倍平衡实现成本高频繁旋转低旋转次数有限且可控插入最多旋转2次2次删除最多旋转(O(\log n))次可能要回溯到根3次教科书结论查找性能最严格(O(\log n))也是(O(\log n))常数略大空间开销只需存高度或平衡因子需额外存颜色位适用场景查多改少、内存中的字典改多查多、语言库底层实现408考法旋转模拟、高度/最少节点、ASL性质判断、插入模拟、黑高相关这张表里最有价值的两个点一个是删除旋转次数的对比。AVL删除的最坏情况要一路旋转到根红黑树删除最多3次旋转就能完成修正这是红黑树在工业界“能打”的关键。另一个是查找性能的实际差距。AVL树高严格贴近(\log_2 n)红黑树树高最多(2\log_2(n1))理论上AVL查找更快但在现代CPU的缓存和分支预测面前这点常数差异基本可以忽略反而是旋转开销更小的红黑树综合表现更好。考场上一旦出对比题你只要把这几个维度答全再补一句“AVL是严格平衡树红黑树是弱平衡树弱平衡以微弱的查找性能牺牲换来了更低的插入删除维护成本”这道简答题的分基本就稳了。5. 408真题实战三问三答把知识变成分数这里我用三个典型的408风格问题把上面所有知识点串起来。这些问题不是某一年原题但题型和套路完全一致值得认真做一遍。第一问一棵有n个节点的平衡二叉树n1000时树高最大可能是多少按AVL最少节点数递推高度8最少54个节点高度9最少(5433188)个节点高度10最少(88541143)个节点高度11最少(143881232)个节点高度12最少(2321431376)个节点高度13最少(3762321609)个节点高度14最少(6093761986)个节点高度15最少(98660911596)个节点。1000介于986和1596之间所以最大高度只能是14。这类题的本质就是倒着用(N_h)递推别去真的画图。第二问向一棵空的红黑树依次插入15, 5, 20, 3, 10画出最终的红黑树。先插入15变黑根。插入5红色父黑不动。插入20红色父黑不动。插入3红色父节点5是红色叔叔节点是20注意5的兄弟是2020是红还是黑此时20是红色节点所以属于第二种情况叔叔为红。把父节点5和叔叔节点20都染黑爷爷节点15染红。但15是根根必须是黑所以15保持黑色。调整后15黑根5黑、20黑3红是5的左孩子10还未插入。插入10红色父节点5是红色叔叔节点20是黑色刚被染黑。触发第三种情况。三个节点15、5、10构成“之”字形左-右折线先对5左旋10提上来再对15右旋10提为根。旋转后改色10变黑15和5变红。最终结构10是黑根5是红左孩子3是黑左孙15是红右孩子20是黑右孙。检查性质根黑红节点不相连黑高各路径均为2正确。这道题有两个坑第一个是插入3之后叔叔20本来是红的调整时把爷爷15染红但根节点不能是红色所以必须把15强行保持黑第二个是后续插入10时叔叔20的颜色已经被前面调整成黑色了很多同学还按红色去算直接做错。第三问一棵红黑树的黑高为3最少有多少个节点如果这棵树同时是一棵AVL树高度最高是多少红黑树黑高3最少节点数就是全黑满二叉树高度3的满二叉树有(2^3-17)个节点。AVL树问“高度最高”要反过来用最少节点数递推(N_00, N_11, N_22, N_34, N_47, N_512)。7个节点的AVL树最大高度是4因为高度4最少需要7个节点高度5最少需要12个7不够。所以答案是4。这道题的巧妙之处在于把两个数据结构的“最少节点数”放到一起考本质上都在考同一个递推思想。你如果只会背“平衡因子”和“红黑树五条性质”做不出这种跨章节的题但理解了“树高的约束来自节点数下限”这个本质就能举一反三。6. 易错点与考场提分笔记现在到了我最想跟你分享的部分。以下这些坑都是我当年复习时踩过、或者后来辅导别人时反复看到的全部列出来给你避雷。第一AVL旋转时忘记更新高度。模拟旋转过程中旋转涉及的节点的高度会变如果不重新计算高度下一步判断平衡因子时就会算出错误结果。做题时即使题目没要求写高度也要在草稿纸上手动标一遍尤其是旋转完成后别漏了原来子树中没参与旋转但高度受影响的节点。第二红黑树插入时把“叔叔”和“父亲”弄混。很多初学者以为父节点是红色就看爷爷节点的另一个孩子但有时候图中那个位置被省略了NIL导致判断成“没有叔叔”。记住NIL节点是黑色算叔叔存在该走第三种情况就走第三种情况。第三AVL的LR和RL旋转顺序写错。LR是先左旋后右旋RL是先右旋后左旋。我有个特别笨但特别有效的记忆方法**看字母L在前就先左旋R在前就先右旋第二个字母对应后转的方向。**LR里L在前先左后右搞定。第四408有几年喜欢考“左右调整后根节点是谁”。这类题不用把整棵树画完你只需要关注最小不平衡子树局部旋转完成后新的根节点一定是“原失衡节点的某个孩子或孙子”具体是哪一个由旋转类型决定。LL型旋转后原失衡节点的左孩子成为新根RR型后原右孩子成为新根LR型后原失衡节点的左孩子的右孩子成为新根RL型后原右孩子的左孩子成为新根。这个结论直接背下来能省很多时间。第五红黑树“根节点必黑”这个性质在插入调整里经常被忽略。当调整到根节点时如果根被染红了必须强制再染黑。而且这种强制染黑不会破坏性质5因为所有路径的黑高同时加了1相对关系不变。第六千万别混淆平衡二叉树和二叉排序树的删除。平衡二叉树首先是二叉排序树删除时替换节点的方式继承自二叉排序树规则但AVL多了一步“删除后要调整平衡”。有些题故意只给AVL树的删除过程删除节点本身按BST规则处理之后的平衡调整才按AVL规则来两步要分开做。第七时间复杂度的表述要准确。AVL的查找、插入、删除都是(O(\log n))但插入最多两次旋转单旋或双旋算一次删除是(O(\log n))次旋转。红黑树的查找是(O(\log n))插入最多两次旋转删除最多三次旋转。注意复杂度是(O(\log n))不等于旋转次数是(O(\log n))不要在一些对比简答里乱写。第八画红黑树时NIL叶子节点要不要画出来408如果你画对内部节点没画NIL一般不扣分。但涉及“性质5黑高相等”的判断时你心里必须把NIL算进去否则会错误地认为某些路径黑高不等。最后给你一个复习策略上的建议。平衡二叉树和红黑树在408里的分数占比通常不高一年最多一两道选择题或者在一道大题里占一个子问。所以复习的性价比排序是ATV旋转模拟 AVL最少节点/高度计算 红黑树性质辨析 红黑树插入过程 红黑树删除了解思想即可。别花整天时间死磕红黑树的删除那是浪费时间。把上面这些核心题型吃透这部分分数你就能稳稳拿到手。