引子老王的灵魂一问还记得上一篇里把旋转四式练得炉火纯青的老王吗LL用右旋、RR用左旋、LR先左后右、RL先右后左——他对着歪树一招一式掰得有模有样。可这天老王练着练着忽然停下手眉头一皱冒出一个直击灵魂的问题等等我掰正了下面这个’失衡点’可万一……这一掰把它的’祖宗’又给带歪了呢那我岂不是要一路往上、转个没完到底——掰一棵歪树一次旋转就够了还是得’噼里啪啦’转上好几回才能彻底太平老王这一问问到了平衡二叉树最精微、也最容易让人犯迷糊的一个点上。很多人学会了旋转四式却答不上来这个问题——修复一棵失衡的树到底是一锤定音还是层层连锁上一篇咱们练熟了’怎么转’老王搓搓手“这一篇就来彻底搞明白——到底要转几次这里头藏着插入和删除两种情况的’大不同’呢”搬好板凳咱们开聊。第一章先分清——一次旋转到底指什么要回答要不要转好几次得先把一次这个词掰扯清楚。因为这里有个极易混淆的陷阱。回想旋转四式它们用到的旋转次数其实不一样LL型 → 右旋 ×1 ← 转1个基本动作 RR型 → 左旋 ×1 ← 转1个基本动作 LR型 → 左旋 右旋 ×2 ← 转2个基本动作 RL型 → 右旋 左旋 ×2 ← 转2个基本动作咦LR和RL不是要转两次吗那不就是多次旋转了别急这里要区分两个概念“一次基本旋转” vs “一次再平衡操作”基本旋转指一个单独的左旋或右旋动作。再平衡操作指为了修复某一个失衡点所做的全套调整。LR型虽然用了左旋右旋两个基本旋转但它们都是为了修复同一个失衡点 G而做的合起来算一次再平衡操作就像你拧一颗松了的螺丝可能要先回半圈、再正着拧两个动作但本质上是拧紧这一颗螺丝这一件事。┌─────────────────────────────────────────────┐ │ LR / RL 的两次旋转—— │ │ 是为修复同一个失衡点的【一次】再平衡操作 │ │ 只是这次操作内部含两个基本旋转动作 │ └─────────────────────────────────────────────┘所以当老王问要不要转好几回真正的问题应该精确成“修复一棵失衡的树需不需要在【好几个不同的失衡点】上分别做再平衡操作”而这个问题的答案取决于你是在插入还是删除——这两种情况答案截然相反这正是本篇的核心。第二章插入的情况——好消息一次再平衡就够了我们先看最常见的插入操作。这里有个让人欣慰的好消息 黄金结论在AVL树中插入一个新节点后最多只需要对【一个】失衡点做一次再平衡操作整棵树就全部恢复平衡了这一次操作可能是单旋转LL/RR也可能是双旋转LR/RL但只此一处绝无连锁。2.1 看个案例老王的担心会发生吗老王怕的是掰正了下面又带歪了上面。我们用案例验证一下插入新节点前树是平衡的 (50) ╱ ╲ (30) (70) ╱ ╲ (20) (40) ╱ [此处插入新节点 (10)] 插入10后沿途高度变化节点30失衡了 (50) ╱ ╲ (30) ←失衡点G(因子2) (70) ╱ ╲ (20) (40) ╱ (10)老王找到最低的失衡点 30LL型对它做一次右旋对 (30) 右旋后 (50) ╱ ╲ (20) (70) ╱ ╲ (10) (30) ╲ (40)见证奇迹的时刻——老王再去检查祖宗节点 50节点50左子树高度3右子树高度2差1 ✅ 平衡 整棵树全部平衡不需要再转了老王担心的连锁反应并没有发生为什么2.2 为什么插入只需一次——精妙的身高复原原理这背后藏着一个极其精妙的原理搞懂它你就彻底通透了核心原理旋转修复后子树的高度复原了。想一想插入一个新节点会让某条路径长高1层这才导致了失衡。而当你对最低失衡点做完旋转后——这个被修复的子树的高度恰好变回了插入之前的高度既然这棵子树的高度复原成了插入前的样子那么它上面的所有祖宗看到的下属高度就和插入前一模一样——祖宗们压根感觉不到下面发生过’地震’自然全都还是平衡的插入前子树高度 H 插入后子树高度 H1 → 引发失衡 旋转后子树高度 H → 高度复原祖宗们毫无察觉全程平衡这就是插入一次定乾坤的秘密旋转就像一个高明的消音器——它不仅修复了局部的失衡还顺手把高度增加这个波动给彻底抹平了让震荡无法向上传递。一句话记住插入操作只需在最低失衡点做一次再平衡全树即安。无需向上连锁。第三章删除的情况——坏消息可能要层层连锁转好几次可是老王的担心并非空穴来风。在另一种操作——“删除”——里那个可怕的连锁反应真的会发生⚠️ 黄金结论在AVL树中删除一个节点后修复一个失衡点可能会引发更上层的失衡从而需要【沿着路径一路向上、做多次再平衡操作】最多可达 O(logn) 次。3.1 为什么删除会连锁——致命的身高缩水关键的差别又在高度上。我们对比一下插入后旋转子树高度复原变回原样→ 祖宗无感 → 不连锁。删除后旋转子树高度缩水比原来矮了1层→ 祖宗察觉到下属变矮了 →可能引发祖宗失衡→ 连锁删除一个节点 → 某条路径变矮1层 → 引发失衡 对失衡点旋转修复 → 但这棵子树旋转后【又矮了1层】 → 这个变矮的波动向上传给祖宗 → 祖宗一看哎呀我的一边怎么变矮了我也失衡了 → 继续向上修复…… 如此层层传递这就是删除的连锁陷阱旋转虽然修复了局部却带来了新的高度缩水这个缩水像多米诺骨牌一路向上推倒。3.2 看个连锁案例我们看一棵瘦长的AVL树删除一个节点引发连锁删除前这是一棵合法的AVL树 (50) ╱ ╲ (30) (70) ╱ ╲ ╲ (20) (40) (80) ╱ (10) 现在删除右下角的 (80) (50) ╱ ╲ (30) (70) ←70失衡了(左0右0…等下70左空右空) ╱ ╲ (20) (40) 70只剩自己但50这边…… ╱ (10)删除80后节点50失衡了左子树高3右子树高1差2LL型。老王对 50 做右旋对 (50) 右旋后 (30) ╱ ╲ (20) (50) ╱ ╱ ╲ (10) (40) (70)这次单棵树的例子修复后恰好平衡了。但关键在于如果这棵树是某棵更大的树的一部分那么旋转后整棵子树变矮了1层这个变矮会继续上传——节点30的某个祖宗就可能因此失衡老王就得继续往上再做一次旋转甚至再往上、再一次……极端情况下从被删节点一路到树根每一层都可能需要做一次再平衡——这就是多次旋转3.3 一张图看懂插入与删除的本质区别┌──────────┬─────────────────┬──────────────────┐ │ │ 插入(Insert) │ 删除(Delete) │ ├──────────┼─────────────────┼──────────────────┤ │ 旋转后高度 │ 复原(变回原样) │ 缩水(矮了1层) │ │ 是否连锁 │ ❌ 不连锁 │ ⚠️ 可能连锁 │ │ 再平衡次数 │ 最多 1 次 │ 最多 O(logn) 次 │ │ 一句话 │ 一次定乾坤 │ 可能层层向上修复 │ └──────────┴─────────────────┴──────────────────┘恍然大悟原来老王的担心分情况——做加法插入时旋转能把波动彻底抹平一次就够干净利落做减法删除时旋转却会留下高度缩水的余波可能一路荡漾到树根需要层层安抚。同样是掰正一棵树添与删的善后难度竟有天壤之别第四章那么效率还高吗——别担心依然很快听到删除可能要转好几次、最多O(logn)次老王有点慌“那岂不是很慢”别慌依然非常快我们来算笔账AVL树的高度始终维持在O(logn)这个量级这正是平衡的功劳所以从底层一路向上到树根最多也就O(logn)层每一层最多做一次再平衡一两个基本旋转都是 O(1) 的瞬间操作加起来删除时的旋转总开销最多也就 O(logn)插入找位置 O(logn) 最多1次旋转 O(logn) 删除找位置 O(logn) 最多O(logn)次旋转 O(logn) 结论无论插入还是删除总复杂度都稳稳是 O(logn)关键结论哪怕删除时要层层连锁旋转由于树本身又矮又平衡连锁的链条也很短最多logn节所以整体效率丝毫不打折依然是漂亮的 O(logn)。这正是平衡带来的底气——它从根上保证了无论你怎么折腾都不会有太长的连锁。第五章总结——三句话回答老王的灵魂一问老王把这一篇的精华浓缩成了三句话贴在墙上┌────────────────────────────────────────────┐ │ 问掰正一棵歪树要转几次 │ ├────────────────────────────────────────────┤ │ ① LR/RL的两次是修同一处的【一次】操作 │ │ 别被两个动作骗了。 │ │ │ │ ② 插入最多【一次】再平衡全树即安—— │ │ 因为旋转后高度复原波动被抹平。 │ │ │ │ ③ 删除可能要【多次】再平衡层层向上—— │ │ 因为旋转后高度缩水余波会上传。 │ │ 但因树矮总开销依旧是 O(logn)。 │ └────────────────────────────────────────────┘老王长舒一口气悟出了门道原来如此‘要不要多转几次’根子上不在’旋转’本身而在’旋转之后子树的身高是复原了还是缩水了’。身高复原波澜不惊一次了事身高缩水余波荡漾层层善后。看问题真得看到这一层’连锁的根源’上才算真懂了啊尾声连锁与复原的智慧亦是人生的智慧老王的灵魂一问从一次还是多次问起问出了插入与删除的天壤之别问到了高度复原 vs 高度缩水的连锁根源终于把这个最让人犯迷糊的问题彻底想透了。但当我们合上书会发现这一次还是多次的背后竟也藏着几分耐人寻味的人生哲理。第一添置易善后割舍需层层安抚。给树插入新节点旋转一次便波澜不惊可从树中删除一个节点却可能引发层层连锁、需要一路向上地修补。这何尝不是人生的隐喻我们获得、添置一样东西时往往代价清晰、影响可控可当我们要割舍、放下、告别某样东西时——一段关系、一个习惯、一份执念——那留下的’空缺’带来的余波却常常会一层层地荡漾开去需要我们耐心地、层层地去安抚和调适。懂得删除比添加更需要善后,我们在面对失去与告别时,才会多一份从容和准备。第二看问题要看到连锁的根源。老王最初只盯着旋转本身百思不得其解直到他看穿了真正的根源——“旋转后子树的高度是复原还是缩水”一切才豁然开朗。这是一种深刻的洞察力面对一个现象要不要连锁别停留在表面旋转动作而要追问那个真正的驱动因子高度变化。生活中许多看似复杂、捉摸不定的连锁反应一旦你找到了那个最底层的’根源变量’便会发现——原来万变皆有其宗。抓住根源繁杂自清。第三根基稳了再大的连锁也不可怕。删除时哪怕要层层旋转可因为树本身又矮又平衡连锁的链条永远很短效率依旧出色。这给了我们莫大的底气真正让你不惧连锁麻烦的不是祈祷麻烦别来而是平时就把根基打得又稳又扎实。一个内在足够平衡、根基足够牢固的人或系统纵然遭遇接二连三的连锁冲击也总能把震荡控制在很短的范围内迅速恢复如初。行稳方能致远根深自不怕风摇。下次当你从一个庞大的系统里删除一条数据、而它依然瞬间响应时请记得——在那看不见的深处正有一棵棵智慧树在高度缩水的余波里或一锤定音、或层层向上精准地做着一次次再平衡又快又稳地把自己重新站成挺拔。平衡二叉树的转几次就是这门关于分清连锁、看透根源、稳固根基的、精微而深刻的功夫。它告诉我们同样是修复添与删善后迥异而看透那复原与缩水的根源便能于纷繁连锁中了然于胸。它像一句朴素的箴言提醒着我们——添置一物往往一次即安割舍一物常需层层安抚而真正看透连锁根源、又把根基扎得够稳的人才能像那棵树一样——无论面对一次的修补还是层层的震荡总能不慌不忙迅速归于挺拔与从容。这就是藏在到底转几次背后的平衡二叉树最精微、也最通透的浪漫。