写平衡树这件事绕不开 AVL 树也绕不开它那四种旋转。我在刚接触数据结构那阵子能背出“LL 右旋、RR 左旋、LR 先左后右、RL 先右后左”这句口诀但真正上手写代码时指针一挪就出错不是把孩子节点弄丢就是高度算反编译能过、跑起来直接结果错乱。后来带过几届同学做课程设计发现大家卡住的地方高度一致不是不理解旋转“是什么”而是不清楚“为什么只有这四种”“每一步指针为什么要按那个顺序改”“改完之后高度该先更新谁”。这篇就围绕 AVL 树的四种数据旋转方法把我自己踩过的坑、验证过的写法和排查思路完整摊开讲。内容覆盖旋转的分类逻辑、平衡因子与树高的量化、四种旋转的逐行实现、嵌进插入流程后的落地验证以及一批只有真写过才会遇到的坑。不管你是刚学完二叉搜索树想往下走一步还是已经能抄出一份能跑的代码但心里没底下面的内容都能直接拿去对照。1. 四种旋转的分类逻辑与设计思路1.1 AVL 树到底在修补二叉搜索树的什么毛病普通的二叉搜索树有个致命弱点它的形状完全取决于插入顺序。你按 10、20、30、40、50 这样递增地插得到的就是一条向右倒的链子查找退化成遍历复杂度从 O(log n) 掉到 O(n)。这个退化不是理论上的极端情况实际业务里按时间戳、按自增 ID 顺序写入的数据到处都是随手一插就是最坏形态。AVL 树的思路很直接给每个节点记一个“左右子树高度差”只要这个差值超过 1就立刻动手把树“掰”回来让整棵树始终保持近似平衡从而把查找、插入、删除都稳在 O(log n)。这里有个关键设计选择值得说清楚。修补平衡的手段不止一种有人会想“大不了把整棵树重建一遍”代价是 O(n)插入频繁时完全不可接受。AVL 选的是局部手术只动失衡点附近几个指针代价是常数级而且不破坏二叉搜索树的中序有序性。这个“只动局部”的约束直接决定了旋转必须满足两个条件——第一改完之后仍是合法的二叉搜索树第二改完之后子树高度确实降低了。四种旋转的全部细节都是从这两条推出来的。1.2 旋转为什么能降高度一次指针重接的账拿最典型的右旋举例。设失衡节点为 y它的左孩子是 xx 的右子树记作 T2。右旋做的事是把 x 提上来当新的子树根y 降下去成为 x 的右孩子而 T2 原本挂在 x 的右边因为 x 上升、y 下降T2 的所有键都大于 x 小于 y正好可以整块挪过去当 y 的左子树。整个过程只改了三个指针T2 内部一个节点都没动。为什么这样能降高度原来这棵子树的高度是 1 max(h(x), h(y右))而 x 那边偏高才导致失衡。旋转之后y 的左子树从 x 变成了 T2高度更小的那棵x 的右子树变成 y。算下来整棵子树的高度从“偏高的那条腿”变成了“两条腿更均衡的分配”高度回落。这也是为什么单次旋转在插入场景下总是够用的根本原因失衡往往就是一条腿长了 2把它挪一节到另一条腿上就平衡了。1.3 为什么只有四种从失衡方向枚举出来的结果很多人以为四种旋转是“规定”其实它是枚举出来的必然结果。失衡节点的平衡因子只可能是 2 或 -2 两种超过 2 说明更早的地方就该被修了。当平衡因子为 2说明左子树高问题出在左边此时造成左子树变高的那个新节点要么落在左孩子的左子树LL要么落在左孩子的右子树LR。同理平衡因子为 -2 时新节点要么在右孩子的右边RR要么在右孩子的左边RL。四种情况一一对应四种修法。LL 和 RR 是“直线型”一次单旋就能把高的那条腿折回来LR 和 RL 是“折线型”新节点插在了内侧一次单旋只会把它从内侧甩到外侧还是失衡所以必须先把它转成直线型再做一次单旋。理解了这个分类来源就不会再出现“我到底该用哪种”的犹豫——先看平衡因子定左右再看新节点落在孩子的哪一侧定单双两步就够。2. 动手前必须钉死的三个前置概念2.1 树高与平衡因子把“歪了”变成可计算的数旋转的触发条件必须是可量化的AVL 用的是两个量。第一个是树高通常约定空树高度为 0叶子节点高度为 1任意节点高度等于左右子树高度的最大值加一。第二个是平衡因子定义为“左子树高度减去右子树高度”。平衡因子取值为 -1、0、1 时视为平衡取 ±2 就说明必须动手了。这里有两个容易埋雷的地方。其一高度定义必须全篇统一。我见过有人在节点里存“深度”而不是“高度”初始化写成 0 和写成 1 混着来结果平衡因子整体偏移一位判断条件全部失效但代码看着一点问题没有查起来极其痛苦。其二不要图省事每次都递归算高度。递归算高度是 O(n)插入一次就退化到 O(n log n)平衡树白写了。正确做法是把高度作为节点的一个字段缓存起来只在指针结构变动后局部更新。这个缓存的代价很小收益是把每次高度查询压到 O(1)。2.2 失衡类型判定看新节点落在哪而不是只看符号判定 LLRRLRRL 的标准做法是找到失衡节点后比较插入键与它的孩子、孙子的大小关系。如果失衡节点平衡因子大于 1且插入键小于它左孩子的键就是 LL如果插入键大于左孩子的键就是 LR。镜像过来平衡因子小于 -1 时插入键大于右孩子键是 RR小于则是 RL。这个“比较键值”的判定方式在插入场景下是安全可靠的因为新节点一定在失衡点下方。但我要提前打个预防针同样的判定逻辑照搬到删除操作里会翻车。删除时你没有一个“新插入的键”可以比较必须改成直接看孩子的平衡因子——左孩子的平衡因子大于等于 0 用单旋LL小于 0 用双旋LR。这个差异在后面第 5 节会展开现在先记住插入看键值删除看孩子平衡因子。2.3 最小失衡子树的定位为什么修最下面的那个就够插入导致失衡时从插入点往根回溯遇到的第一个平衡因子变成 ±2 的节点就是要修的目标。为什么不修更靠上的那个因为插入只会让某条路径上的高度增加 1一旦你在最下面的失衡点做完旋转这棵子树的高度会回到插入之前的值也就是说它对上层的“贡献”没变上层根本不会因为这次插入而失衡。这条性质非常实用它保证了插入操作每次最多做一次旋转单旋或双旋算一次修复动作代价是常数级。相比之下删除就麻烦得多删掉一个节点后子树高度是真的降低了可能引发上层连锁失衡最坏要一路修到根旋转次数是 O(log n)。把这条性质记住你在写代码时就能确信插入路径上层层回溯时只要修好第一个失衡点后面的平衡因子检查天然会通过不用做额外处理。3. 四种旋转的逐一手写实现3.1 右旋LL 型的标准动作与指针顺序右旋处理的是左子树过高的直线型失衡。先给节点定义我习惯用最朴素的结构键值和高度都存下来struct Node { int key; int height; Node* left; Node* right; Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {} }; int h(Node* p) { return p ? p-height : 0; } void update(Node* p) { if (p) p-height 1 std::max(h(p-left), h(p-right)); }右旋的实现关键在于先把“要转移的子树”保存下来再动指针Node* rotateRight(Node* y) { Node* x y-left; Node* T2 x-right; // 必须先保存否则下面一改就丢了 x-right y; y-left T2; update(y); // 先更新降下去的 y update(x); // 再更新升上来的 x return x; // 返回新的子树根 }三处细节必须钉住。第一T2一定要在第一行指针改动之前存下来否则x-right y执行完T2 就再也找不到了这是新手最容易写出的悬挂问题。第二update的顺序是先 y 后 x因为 x 的高度依赖 y 的新高度反过来算会用到旧值得到的高度偏大平衡因子后面全乱。第三函数返回新的子树根调用方必须把这个返回值接住并挂回父节点直接调用而不管返回值等于什么都没做。举个具体的例子树根 30左孩子 1010 的右孩子 20。此时 30 的平衡因子是左高 2 减右高 0 等于 2插入键 20 大于 10属于 LR用右旋处理不了得先转成 LL。而如果左孩子 10 还有个左孩子 5插入后 30 平衡因子为 2、插入键 5 小于 10这才是标准 LL右旋一次10 上位30 变成 10 的右孩子中序遍历永远是 5、10、30顺序一点没变。3.2 左旋把右旋镜像过来别另起炉灶左旋处理右子树过高的直线型失衡代码是右旋的完全镜像Node* rotateLeft(Node* x) { Node* y x-right; Node* T2 y-left; y-left x; x-right T2; update(x); // 同样先更新降下去的 update(y); // 再更新升上来的 return y; }我建议你写的时候就把两个函数上下摆在一起逐行对照着看确保对称。很多人右旋写熟了左旋凭感觉默写结果漏掉update或者把 T2 挂错边。T2 在左旋里是y-left挪过去要挂到x-right因为 T2 的键介于 x 和 y 之间x 上升是不可能的x 是降下去的那个所以 T2 只能挂在 x 的右边。这个推理过程比死记“左旋挂右边”靠谱得多。左旋的经典触发场景是递增插入依次插 10、20、30插入 30 时根节点 10 平衡因子变成 -2插入键 30 大于右孩子 20属于 RR左旋一次20 成为新根左孩子 10、右孩子 30。如果你在纸上画一遍指针挪动会发现整棵树从一条右斜链变成了一个漂亮的三角形高度从 3 降到 2。3.3 左右双旋LR 型为什么必须转两次LR 型是折线型失衡节点 z 平衡因子为 2问题在左孩子 y 上但新节点插在了 y 的右子树里。这时候如果直接对 z 右旋y 上位可 y 的右子树那个刚插了新节点的、偏高的家伙会整体挂到 z 的左边失衡只是从左边换到了更深处压根没解决。正确的做法是两步先对 y 做一次左旋把折线掰成直线再对 z 做一次右旋用标准的 LL 处理。Node* rotateLeftRight(Node* z) { z-left rotateLeft(z-left); // 第一步把左孩子那侧掰直 return rotateRight(z); // 第二步按 LL 处理 }理解双旋有个特别好用的直觉LR 旋转结束后成为新子树根的一定是那个“键值居中”的节点也就是新插入路径上位于中间的那个孙子节点。比如 z 是 30、y 是 10、新插入的是 20旋转完 20 就是子树的根左边挂 10、右边挂 30。你写完双旋可以直接用这个直觉验收——如果转完根不是中间那个键指针肯定挂错了。还有一个等价理解方式LR 双旋本质上就等于把那个中间节点直接“提”上来做根原来的一老一小两个节点自动变成它的左右孩子。理解了这点你甚至可以先把这个中间节点的左右子树临时保存起来手工重新拼装结果和双旋完全一致。我在教别人的时候更愿意用这种方式讲因为它不依赖“先左后右”的死记而是从目标形状倒推。3.4 右左双旋RL 型的镜像写法RL 型是 LR 的镜像失衡节点 z 平衡因子为 -2问题在右孩子 y 上但新节点插在了 y 的左子树里。处理方式是先对 y 做右旋把折线掰直成 RR再对 z 做左旋。Node* rotateRightLeft(Node* z) { z-right rotateRight(z-right); // 第一步把右孩子那侧掰直 return rotateLeft(z); // 第二步按 RR 处理 }这里要注意第一步的返回值必须赋给z-right。我见过最隐蔽的一种写法是rotateRight(z-right);单独一行看起来调用了函数实际返回值被丢弃树的内部结构其实已经改好了——因为指针是在原节点上改的——但新根没有被正确挂回父节点于是整棵树从这一层往下断链。这种问题编译不报、运行不崩只是某个分支的数据凭空消失排查起来非常费劲。同样用直觉验收RL 旋转结束后新根是那个键值居中的孙子节点。比如 z 是 10、y 是 30、新插入的是 20转完 20 上位左挂 10、右挂 30。四类旋转的最终形状其实高度统一单旋是“老的让位给高的那个孩子”双旋是“老的让位给居中的那个孙子”。3.5 旋转后的收尾一张必须核对的自检清单四种旋转写完别急着往下跑主程序先用下面这张表过一遍能省掉后面大半夜的排查时间。检查项正确做法常见错误转移子树的保存改指针前先存到临时变量直接改导致子树整块丢失高度更新顺序先更新降下去的节点再更新升上来的顺序反了高度偏大返回值处理调用方必须接住新根并挂回父节点丢弃返回值断链空节点保护h()用三目运算兼容 nullptr直接解引用空指针双旋第一步的赋值z-left rotateLeft(z-left)只调用不赋值中序不变性旋转前后中序遍历结果完全一致从不验证错了也不知道这张表我建议你打印出来贴在屏幕边上写一次对一次。尤其是“中序不变性”这一条它是最便宜、最有效的自检手段随机插几十个数每次旋转后打一遍中序只要顺序不对立刻停下查指针。相比于盯着代码看半天跑一次输出对不上问题定位快十倍。4. 把旋转嵌进插入流程的完整落地4.1 递归插入框架回溯时顺手完成修复旋转本身不难难的是把它放进正确的时机。我用得最顺的是递归插入向下按二叉搜索树规则找位置插完在回溯的路上更新高度、算平衡因子、该转就转。这样写的好处是把“修复”和“结构变动”天然绑定在一起每个节点回溯时都保证自己的子树是平衡的逻辑非常干净。Node* insert(Node* node, int key) { if (!node) return new Node(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; // 重复键直接忽略 update(node); int bf h(node-left) - h(node-right); if (bf 1 key node-left-key) return rotateRight(node); if (bf 1 key node-left-key) return rotateLeftRight(node); if (bf -1 key node-right-key) return rotateLeft(node); if (bf -1 key node-right-key) return rotateRightLeft(node); return node; }四个条件分支的排列顺序我习惯按“左高单旋、左高双旋、右高单旋、右高双旋”来写和分类逻辑一一对应读代码时不容易错位。判定里用的是插入键而不是孩子的平衡因子这一点在插入场景是成立的因为新节点必然在失衡点下方。返回值的处理是全篇最关键的一环每个分支都必须把旋转后的新根return出去让上一层用node-left insert(...)这种形式接住。少一个 return链就断在这一层。4.2 一个覆盖四种旋转的完整推演光看代码没感觉拿一组能触发全部四种情况的序列走一遍更实在。依次插入 30、10、20、40、50、5、25、45、22我按关键节点列出触发点插入值触发情况失衡节点处理动作处理后的根30、10、20LR30对 10 左旋再对 30 右旋2040无需旋转无平衡因子均未越界2050RR20对 20 左旋305LL20对 20 右旋1025、45无需旋转无平衡因子均未越界3022RL20对 25 右旋再对 20 左旋22这个序列的价值在于它把四种情况都覆盖了一遍而且每一步都能在纸上画出来对照。做完之后整棵树大概是根 30左子树以 10 为根左 5、右 2222 下挂 20 和 25右子树以 40 为根右 45。总高度 3七个以上的节点高度 3 是相当紧凑的。如果你是第一次写强烈建议别用随机数据直接测就用这九个数字一步步打印中序和高度。每插入一个就检查两件事中序是否严格递增、每个节点的平衡因子绝对值是否都不超过 1。两条都过旋转基本就是对的有一条不过问题一定在刚做的那次旋转里范围极小。4.3 三重校验怎么确认自己写的是对的自己写的东西自己看着总觉得对所以验证逻辑必须比实现逻辑更严。我固定用三层校验成本很低但抓错很准。第一层是中序校验。写个中序遍历把结果存进数组检查是否严格递增。旋转只改结构不改键值中序一旦乱了说明指针挂错了子树T2 挂到不该挂的位置去了。这个检查能抓住绝大部分结构性错误。第二层是高度与平衡因子校验。递归遍历整棵树对每个节点同时返回“该子树高度”和“是否平衡”一遍扫完。如果某个节点平衡因子越界打印它的键值就能直接定位到位置。第三层是规模压测。手工构造 200 个递增数插进去看最终树高是不是在 log2(200) 附近大约是 8 上下。如果高度跑到了几十说明旋转压根没生效如果高度卡在 7 以下说明可能有节点被重复创建或者丢了。递增序列是最狠的测试用例因为它是二叉搜索树退化的最坏输入能扛住递增序列基本就稳了。4.4 参数与代价的口径别把复杂度算错了写完之后总得说清楚它的代价。一次旋转只改三个指针、更新两个高度是严格的 O(1)。插入时沿路径下降是 O(log n)回溯时每个节点做一次常数级的判断所以总代价是 O(log n)。空间上每个节点多存一个高度字段相比只存键值的实现多了 4 字节换来的是高度查询的 O(1)。还有个常被忽略的收益点插入场景下每次插入最多只需要一次修复动作。这个结论在 2.3 里推过实践中它的价值是让你敢于在代码里“修完就收手”不用在回溯路径上反复检查。如果你照搬删除的逻辑去做插入每次都从头修到根虽然结果也对但白白多花了常数倍的时间而且代码复杂了一截。5. 踩坑实录与排查速查表5.1 指针类的三类经典错误第一类是转移子树丢失。y-left T2这一句里T2 必须在改指针之前存好。我见过写成先y-left x-right再接x-right y的这样看着也能跑但语义完全反了——前一句执行时x-right还是原值等于把 T2 直接挂回去了后面的操作全乱。这类错误不会崩只会让某些节点从此不可达。第二类是返回值丢弃。旋转函数返回新根调用方必须接住。回到第 3.3 那个例子rotateLeft(z-left)单独一行内部指针改了、新根没挂回去结果是这棵子树的父节点还指着老的 z-left而老的那个节点已经变成别人的孩子形成环或者丢链。表现形式通常是程序跑着跑着某次遍历栈溢出或者输出少了一批数据。第三类是空指针解引用。h()函数里如果写return p-height;而不判空叶子节点的孩子一查就崩。我建议所有涉及子节点的表达式都统一走h()这个封装不要到处写node-left-height省得某个分支漏判。5.2 高度更新的时序坑update的顺序错是最难查的一类因为它不崩不丢数据只是数值悄悄偏大。正确顺序是先更新降下去的那个节点再更新升上来的那个因为后者依赖前者的新高度。反过来写x 会用 y 的旧高度来算自己得到的高度比真实值大 1于是平衡因子偏之后所有判断都是错的。这个问题最阴的地方在于小数据量测试时可能完全正常因为偏差没有累积到触发条件一旦数据量上去某次本该旋转的地方没转树形慢慢歪掉。排查办法很简单写个独立的recalcHeight(node)递归重算真实高度和缓存值逐个对比找第一个不一致的节点它的祖先链上必然有一次 update 顺序写反了。5.3 插入判定照搬到删除场景的坑前面提过插入用“比较键值”判定类型是安全的但删除不能这么写。删除一个节点后你不知道“新节点”在哪只能看平衡因子节点平衡因子大于 1左高如果左孩子的平衡因子大于等于 0说明是 LL单旋如果小于 0说明是 LR双旋。右侧镜像同理。这个差异背后有实际原因插入导致失衡时失衡点左孩子的平衡因子一定不会出现“左侧反而更低”的情况但删除会导致这种形态也就是左子树整体偏高、但左孩子自己的右子树更高。这种情况必须走双旋用键值比较根本判不出来因为压根没有插入键。这个坑我在第一次写删除的时候踩得结结实实明明旋转函数是对的删完就是不平衡最后逐行打印才发现判定分支走错了。5.4 常见问题速查表现象最可能原因排查动作中序输出非递增转移子树挂错边T2 位置不对打印每次旋转前后的中序对比节点数量变少返回值被丢弃或子树丢失插一个统计节点总数的函数对比预期树高明显大于 log nupdate 顺序错或旋转分支没命中递归重算高度与缓存值逐节点对比程序偶发崩溃在高度计算空节点未保护统一走h()封装检查所有裸取 height递增序列插入后成一条链平衡因子判断写反或用错符号打印每个节点平衡因子确认符号方向删除后仍不平衡沿用了插入的键值判定改为看左/右孩子的平衡因子判断单双旋双旋后结构正确但高度不对两步旋转中只 update 了一次检查每个 rotate 函数内部是否各自 update重复键插入后树形异常未处理相等分支相等时直接返回原节点不做任何旋转这张表我贴过很多次实际使用中命中率最高的是第一行和第四行。前者说明结构错了后者说明崩溃两类问题占了绝大多数。至于“树高偏大”这一类往往不是旋转写错而是高度缓存维护出了偏差值得单独拿一个打印函数出来对照。6. 一些取舍与延伸的实际体会6.1 什么时候该用 AVL什么时候别硬上AVL 的特点是严格平衡任何节点平衡因子绝对值不超过 1这让它的查找性能非常稳定。但严格是有代价的插入和删除时更容易触发旋转尤其是删除最坏要一路修到根。如果你的场景是“读多写少”比如做静态索引、内存里的有序字典AVL 的严格平衡很划算查找路径短且稳定。反过来如果写入极其频繁、删除也密集很多工程实现会选红黑树——它放宽到“最长路径不超过最短路径两倍”旋转次数更少写性能更好。我在模拟项目里做过简单对比十万次随机插入两者的耗时差距不大但如果换成大量插入后紧接大量删除AVL 的旋转次数明显更多。所以选择的关键不是“哪棵树更高级”而是读写比例。这个判断我认为比背复杂度表有用得多。6.2 删除操作里旋转的额外难点删除的难点集中在两处。第一处是“删除有两个孩子的节点”通常的做法是用右子树的最小节点或者左子树的最大节点替换掉被删节点然后转去删那个替身节点。替换完成之后整条路径上的高度都可能变化回溯时每个节点都要重新检查平衡不能像插入那样修一次就收手。第二处就是前面说的判定方式差异。写完插入的四类判定之后很多人会本能地把判定条件复制到删除里结果就是时对时错。我的做法是把平衡判断单独抽成一个函数rebalance(node)内部只看平衡因子和孩子平衡因子插入和删除都调它。这样两处逻辑统一少了一份复制粘贴也就少了一处出错的地方。6.3 手写手感是怎么练出来的最后说点实在的。四种旋转这种东西看十遍不如写一遍写一遍不如画一遍。我自己的练习方式是拿一张 A4 纸画三个小格子每次只写一个旋转写完立刻在纸上画出指针改动的效果然后用三五个节点手工推演中序。四张纸写完手感基本就有了。另外推荐一个自检习惯任何一次旋转之后立刻问自己三个问题——中序变了吗、高度算对了吗、新根挂回去了吗。这三问对应了前面三类最常见的错误养成条件反射之后很多 bug 在写的时候就自己消失了。我后来带同学做练习让他们每写一个函数就在注释里写清这三条出错率肉眼可见地下降。真要说有什么捷径大概就是把验证做得比实现更勤快。
/YOLO自动驾驶行人车辆检测)
