如果你写过二叉搜索树八成遇到过这样的尴尬事往树里按顺序插入1、2、3、4、5一棵理想的折半查找结构就变成了一条链表查找复杂度从O(log n)直接跌到O(n)。解决这个问题的经典方案之一就是AVL树——最早被发明的自平衡二叉搜索树。它通过一个简单的平衡因子感知树是否歪斜再用四种旋转操作把树拉回正轨保证树高始终稳定在O(log n)级别。下面这些内容不打算只贴一份能跑的代码就完事。我会先把平衡这件事讲透为什么需要平衡、平衡因子怎么算、什么样的子树需要修然后把四种旋转逐个拆开讲清楚每种旋转解决什么场景、为什么这样转最后给出可以直接抄走的C模板实现并聊聊我写AVL树过程中踩过的坑。适合正在学数据结构的学生、准备算法面试的开发者也适合所有想把自平衡树基础打扎实的人。1. 平衡之道先从树为什么会歪说起1.1 数据一有序二叉搜索树就露馅二叉搜索树的查找、插入、删除都依赖树的高度。理想情况下每次比较都能排除一半数据复杂度是O(log n)。但BST本身没有机制约束形状如果按升序或降序插入数据每个节点都只有一个孩子树就退化成链表。我早年写过一个词条检索程序用了BST以为自己很快结果拿一组有序词条去测试构建完一查程序卡得像回到了拨号上网时代。后来算了一下10万条有序插入树高就是10万每次查询平均要扫描5万个节点不卡才怪。有人可能会说用随机化BST不是也能碰运气吗确实能但平均情况好不代表最坏情况可控。AVL树要的是最坏情况也可控无论插入顺序多恶劣树高都必须被限制在O(log n)以内。它靠的不是概率而是每次插入、删除后实打实的矫正逻辑。这也是理解AVL树的第一步它从根本上放弃了碰运气选择在每次结构变化后主动维护平衡。1.2 平衡因子一把衡量歪斜的尺子AVL树给每个节点定义了一个指标叫平衡因子Balance FactorBFBF(node) height(node-left) - height(node-right)也就是说左子树比右子树高几层。这里高度定义空树为0单个节点为1。AVL树要求任意节点的BF只能是-1、0、1这三个值之一。一旦某个节点BF等于2或-2就说明它已经歪过头必须立刻修正。为什么容忍±1而不要求左右子树完全等高因为完全等高太苛刻了——插入一个节点就可能波及一大片子树调整成本极高。把容差设为1既保证树高依然是O(log n)又让局部调整成为可能。我认为这是AVL树平衡之道里最精髓的地方它追求的不是绝对对称而是可控的倾斜度。顺便补一个数学背景高度为h的AVL树至少包含N(h) N(h-1) N(h-2) 1个节点这个递推和斐波那契数列同构。反向解出来就是n个节点的AVL树高度最多约为1.44log2(n2)。也就是说最坏情况下查找也只需要比较1.44log2(n)个节点。这个上界比红黑树的2log2(n)还紧这也是AVL树在查找密集型场景下依然能打的根本原因。1.3 最小不平衡子树只修需要修的地方插入或删除节点后受影响路径上多个祖先的平衡因子都可能变化。但请注意不是所有祖先都要处理。从插入点往上回溯遇到的第一个BF绝对值大于1的节点就是最小不平衡子树的根。这里有一个关键结论只要把这棵子树调整平衡整棵树就恢复平衡了不需要继续往上检查。为什么可以这么笃定因为在最小不平衡子树的内部所有孩子子树都已经满足AVL性质只是这个根节点自身高度差超限。旋转操作会把子树高度降低1让它回到失衡前的高度于是它的所有祖先的高度和BF都和操作前完全一致——局部修复完成全局自然平衡。这正是AVL树能局部调整、全局生效的数学基础。很多初学的人在删除时对要不要一路旋到根犹豫不决其实就是没吃透这个概念。插入时旋一次就够了删除时因为子树高度可能减1需要沿路径回溯检查多个节点这一点后面实现部分会详细讲。2. 四种旋转平衡的四种矫正手法2.1 旋转的本质是换根不换序旋转操作听起来玄本质只有一句话在不改变中序遍历序列的前提下通过更换子树的根节点来降低树高。中序遍历序列就是所有节点的有序排列只要中序序列不变这棵树就依然是一棵合法的BST。我常用一个生活类比帮助理解想象一个天平左边太重就往左歪你手动把支点往重的那侧挪一下——挪完之后左边有一部分物品划到右边天平重新水平。旋转做的就是这件事把向一边倾倒的子树换个根让两侧高度重新接近。整个过程里节点间的相对大小次序没有任何变化变的只是谁在上面谁在下面。2.2 LL型失衡单右旋场景新节点插入到失衡节点左孩子的左子树导致失衡节点的BF 2。把失衡节点记为AA的左孩子是B。B的左子树是导致失衡的高个B的右子树记为T2。修正方法是让A做一次右旋T2过继给A当左孩子。A变成B的右孩子。B成为子树的新根。代码Node* rotateRight(Node* A) { Node* B A-left; Node* T2 B-right; B-right A; A-left T2; updateHeight(A); updateHeight(B); return B; }为什么这样转完就平衡了因为右旋把B拎起来当根A降级成B的右孩子。B原本的右子树T2它里面的所有节点都大于B且小于A所以过继给A当左子树正好保持中序序列不变。旋转之后B的左右子树高度差自然回到±1以内。说句题外话这里updateHeight的顺序非常关键必须先更新A再更新B因为B的新高度依赖A更新后的值后面还会专门强调。2.3 RR型失衡单左旋RR是LL的镜像场景是新节点插入到失衡节点右孩子的右子树失衡节点的BF -2。修正方法是对失衡节点做一次左旋代码完全对称Node* rotateLeft(Node* A) { Node* B A-right; Node* T2 B-left; B-left A; A-right T2; updateHeight(A); updateHeight(B); return B; }理解了一个方向的单旋另一边就是照镜子不用死记。真正容易出问题的是下面的双旋因为你需要判断先旋哪个、再旋哪个。2.4 LR型失衡先左旋再右旋场景新节点插入到失衡节点左孩子的右子树。此时直接对失衡节点做右旋解决不了问题。原因在于失衡节点A的左孩子B现在是向右偏的B的右子树更高。直接右旋A把B拎上来当根B的右子树T2过继给A当左子树——但T2恰恰是让B失衡的高个子过继之后A可能继续失衡等于换了个方向歪。正确做法是两步走对A的左孩子B做一次左旋把B的右孩子C提上来。这一步做完后A的左孩子变成C而C的左孩子是B整体结构变成了标准的LL型失衡。对A做一次右旋恢复平衡。代码if (bf 1 val node-left-data) { node-left rotateLeft(node-left); return rotateRight(node); }一个直观的理解方式LR型失衡的肇事者在孙子辈。单旋只能把儿子拎上来孙子还在下面捣蛋。双旋的本质是把孙子直接拎到最上面当新根儿子和失衡节点分别成为它的左右孩子。2.5 RL型失衡先右旋再左旋RL是LR的镜像场景是新节点插入到失衡节点右孩子的左子树。操作顺序反过来对A的右孩子B做一次右旋。对A做一次左旋。代码if (bf -1 val node-right-data) { node-right rotateRight(node-right); return rotateLeft(node); }到这里四种旋转模式就齐了。LL和RR是单旋LR和RL是双旋而双旋本质上就是两次单旋的组合只是顺序不能搞反。我自己记的口诀是看失衡节点的孩子往哪个方向歪——同向单旋反向双旋。左孩子左子树歪了是LL单右旋左孩子右子树歪了是LR先左后右。反过来同理。2.6 双旋为什么不能直接旋一次为了让大家彻底死心我用数字拆一下这个迷惑点。假设A的BF -2A的右孩子B的BF -1B的左子树高度是h2B的右子树高度是h。如果对A直接左旋B的左子树T2会过继给A当右子树。假设A的左子树高度是h那么A的左高是h、右高变成h2BF又变成-2只是镜像了一下白转。只有先把B右旋让B的右孩子C提上来此时C的左子树是B、C的右子树是T2整体变成RR型再对A左旋把C拎成根才真正把高度差消化在中间层。这个过程用文字描述确实有点绕建议你在纸上画三层节点把具体高度标在边上跟着代码走一遍。这是当年我学AVL树时摸索出来的最有效的办法比盯着任何动图都管用。3. 动手写代码节点设计与基础工具函数3.1 为什么节点里存高度而不是平衡因子不少教材直接在节点里存平衡因子bf插入时bf或bf--。理论上没问题但实际写起来太容易出错一次旋转涉及多个节点的bf变更谁加谁减很容易记反。我的习惯是节点里只存height平衡因子需要时现算。旋转之后只需要统一调用updateHeight逻辑单一、不易错付出的代价只是多调用几次取高度的函数对现代CPU来说根本不是瓶颈。#include algorithm #include iostream template typename T class AVLTree { private: struct Node { T data; Node* left; Node* right; int height; explicit Node(const T val) : data(val), left(nullptr), right(nullptr), height(1) {} }; Node* root nullptr;height初始值设为1这一步很关键新节点是叶子节点左右子树都为空自身高度就是1。空节点的高度统一由getHeight函数按0处理反正不会让任何逻辑用到空指针的高度。3.2 三个高频工具函数接下来是贯穿全文的三个小函数短小但极其关键int getHeight(Node* node) const { return node ? node-height : 0; } int getBalanceFactor(Node* node) const { return node ? getHeight(node-left) - getHeight(node-right) : 0; } void updateHeight(Node* node) { if (!node) return; node-height 1 std::max(getHeight(node-left), getHeight(node-right)); }getHeight里对空指针返回0省去了在调用处到处判空。getBalanceFactor用左高减右高正数表示左倾负数表示右倾。updateHeight在每次结构变动后刷新节点高度它的调用顺序有讲究必须先更新被降级的旧根再更新被升上去的新根。因为新根的新高度依赖旧根更新后的值顺序反了高度就会越算越离谱。我以前在这个顺序问题上翻过车症状非常隐蔽——树看起来没错但插入几十个节点后突然出现不可能的失衡。3.3 旋转函数的封装思路旋转函数接收一个Node*返回旋转后的新根。调用方用返回值替换原来的子树位置。这种封装的精髓在于严格单向操作旋转函数内部只需要处理三个节点指针和两次高度更新完全不需要知道父节点是谁。父指针的修正任务交给递归返回赋值那一层去完成责任边界非常清晰。Node* rotateRight(Node* A) { Node* B A-left; Node* T2 B-right; B-right A; A-left T2; updateHeight(A); updateHeight(B); return B; } Node* rotateLeft(Node* A) { Node* B A-right; Node* T2 B-left; B-left A; A-right T2; updateHeight(A); updateHeight(B); return B; }我在多个项目里都采用了这种旋转函数只管局部、递归层负责接回的模式代码简洁且调试方便。如果让旋转函数自己去修改父节点的指针就需要额外传父指针或记录祖父节点逻辑复杂度立刻翻倍还容易在双旋里埋坑。4. 插入与删除完整实现与递归回溯4.1 插入BST常规操作加一步检查矫正插入的递归逻辑非常顺手先按BST规则往下走走到空指针就new一个节点回溯时层层更新高度、计算平衡因子发现失衡就旋转。因为失衡只可能发生在这条递归路径上而每一层都做了检查自然就完成了自底向上找最小不平衡子树的过程。Node* insert(Node* node, const T val) { if (!node) return new Node(val); if (val node-data) { node-left insert(node-left, val); } else if (val node-data) { node-right insert(node-right, val); } else { return node; // 重复值直接忽略保持集合语义 } updateHeight(node); int bf getBalanceFactor(node); // LL if (bf 1 val node-left-data) { return rotateRight(node); } // RR if (bf -1 val node-right-data) { return rotateLeft(node); } // LR if (bf 1 val node-left-data) { node-left rotateLeft(node-left); return rotateRight(node); } // RL if (bf -1 val node-right-data) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }注意这里的旋转判断完全不看平衡因子的具体数值而是比较val和node-left-data的大小关系。因为只要失衡发生插入值一定落在对应的方向上这种写法更直观也不容易记混。另一个重要知识点插入最多只需要一次旋转。原因在于旋转后子树高度恢复到插入前上面的祖先节点不会产生新的失衡。这一点和后面的删除形成鲜明对比。4.2 删除三种情况与多段矫正删除比插入麻烦的地方有两处一是要处理拥有两个孩子的节点二是删除可能让路径上的多个节点连续失衡需要一路回溯、一路修正不像插入那样单次旋转就能收工。先看删除主体。我习惯用中序后继右子树最左边的节点来顶替被删节点的值因为后继节点一定没有左孩子删除它必然走到简单的单孩子或叶子分支递归处理起来很干净。Node* minValueNode(Node* node) { Node* cur node; while (cur cur-left) cur cur-left; return cur; } Node* remove(Node* node, const T val) { if (!node) return node; if (val node-data) { node-left remove(node-left, val); } else if (val node-data) { node-right remove(node-right, val); } else if (node-left node-right) { // 两个孩子用中序后继的值覆盖然后去右子树删掉后继 Node* successor minValueNode(node-right); node-data successor-data; node-right remove(node-right, successor-data); } else { // 单孩子或叶子直接用孩子替换自己 Node* child node-left ? node-left : node-right; Node* old node; node child; delete old; } // 删除的是叶子场景下node会被替换成空指针必须先拦住 if (!node) return node; updateHeight(node); int bf getBalanceFactor(node); // 与插入不同的地方用孩子节点的平衡因子判断方向 if (bf 1 getBalanceFactor(node-left) 0) { return rotateRight(node); // LL含左右子树等高的情况 } if (bf 1 getBalanceFactor(node-left) 0) { node-left rotateLeft(node-left); return rotateRight(node); // LR } if (bf -1 getBalanceFactor(node-right) 0) { return rotateLeft(node); // RR含左右子树等高的情况 } if (bf -1 getBalanceFactor(node-right) 0) { node-right rotateRight(node-right); return rotateLeft(node); // RL } return node; }请重点比较这里和插入时旋转判断的差异。插入时用val去判断方向删除时却要看node-left或node-right的平衡因子。原因在于删除过程中没有新插入值这个概念只有一个已经删除后的残缺结构。比如bf1时如果左孩子的bf是0或1说明问题出在左孩子的左子树方向右旋即可只有左孩子的bf是-1时才说明高个子在左孩子的右子树需要先左旋再右旋。这里bf等于0的情况在删除时很常见如果照抄插入的写法树很容易歪掉。这一行判断条件的差别是我见过最多人栽跟头的地方。还有一点删除后可能不止一个节点失衡。因为某个子树的高度变矮之后其祖先的高度对比关系连锁变化所以递归返回路径上的每一层都必须重新检查。好在AVL树高是O(log n)这种多段矫正的总代价依然可控。4.3 查找与树信息接口基础功能当然不能少。查找就是标准的BST路径搜索中序遍历输出则可以用来做有序性验证bool contains(Node* node, const T val) const { if (!node) return false; if (val node-data) return contains(node-left, val); if (val node-data) return contains(node-right, val); return true; } void inOrder(Node* node) const { if (!node) return; inOrder(node-left); std::cout node-data ; inOrder(node-right); }对外层封装一个public接口就能方便调用。中序遍历的单调性是AVL树结构正确性的第一道验证关卡后面我会专门说怎么用。4.4 内存管理析构千万别忘作为手写指针的类析构函数必须递归释放所有节点。我见过太多只管插入、不管释放的Demo代码在检测工具下面内存泄漏红成一片。写一个简单的递归销毁方法void destroy(Node* node) { if (!node) return; destroy(node-left); destroy(node-right); delete node; } public: ~AVLTree() { destroy(root); }如果你不想手动管内存也可以给Node内部成员换成智能指针。但做数据结构学习用裸指针能让你更直观感受节点的生命周期。只要记住三点构造时new、销毁时delete、所有路径都返回新子树根基本不会漏。5. 验证怎么确认写出的树真的平衡5.1 自检一中序遍历单调递增AVL树再怎么旋转中序遍历必须是一个严格递增序列。这一项能过滤掉80%的指针接错、顺序写反之类的低级bug。步骤很简单插入一组乱序数据调用inOrder看输出是否单调。如果某个数突然跳回前面说明某个旋转里的子树过继接错了优先检查旋转函数的T2过继逻辑。5.2 自检二逐节点校验平衡因子光有序还不够还要检查每个节点的平衡因子绝对值不超过1。写一个递归校验函数随机插入删除之后反复调用它是AVL树正确性的最终防线bool isBalanced(Node* node) const { if (!node) return true; int bf getBalanceFactor(node); if (bf 1 || bf -1) return false; return isBalanced(node-left) isBalanced(node-right); }在实际测试时我会用循环做几千次随机插入和随机删除每次操作完都调用isBalanced和在序遍历校验。任何一次失败都说明代码里有bug这时候不要急着猜用断言配合打点定位第一处失败的操作序列比盲改高效得多。5.3 复杂度对比与实测结果操作普通BST最坏情况AVL树最坏情况说明查找O(n)O(log n)查找密集型场景AVL优势明显插入O(n)O(log n)需要发生一次旋转删除O(n)O(log n)可能沿路径多次旋转但不超O(log n)空间O(n)O(n)每个节点多一个int高度字段实际体感上插入10万个升序数据普通BST的高度就是10万AVL树构建完高度只有23左右。这个差距是数量级的。即使面对随机数据AVL树的构建也会有额外常数开销所以读多写少、要求最坏情况稳定的场景最适合它。我之前写过一个内存中的键值索引构建完成后几乎只做查询AVL树比红黑树有更好的平均查找深度整体性能表现非常理想。6. 我踩过的坑与若干设计取舍6.1 常见Bug旋转后忘了更新高度最经典的错误写完旋转函数但忘了更新高度或者更新顺序反了。症状很诡异——树看起来正常插入几十个节点后突然出现不可能的失衡。排查方法是先打印每个节点的高度和平衡因子一眼就能看出哪层的高度不对。修复就是严格遵循先旧根后新根的顺序。这个问题在双旋里尤其隐蔽因为单旋和双旋共用旋转函数一个函数漏了所有涉及该方向的操作都会中招。6.2 删除的旋转判定别照抄插入删除时bf1且左孩子bf为0的情况很多短期教程没讲清楚导致读者照着插入代码改删到一半树就歪了。具体场景是删除发生在左子树导致当前节点左高2但左孩子的两棵子树恰好等高。这种情况下直接右旋就行不需要双旋。只有左孩子右倾bf -1时才需要先左旋再右旋。虽然只是一行判断条件的差别但造成的调试痛苦可以说是天壤之别。建议大家把删除的四种判断单独整理成笔记不要图省事复用插入的if条件。6.3 递归实现的栈深度问题AVL树的递归深度等于树高在数据规模正常时通常只有几十层递归实现完全没问题。但如果你的树要跑在嵌入式环境或者栈空间极小的平台就得考虑改成迭代版本或者限制数据规模。另外要提醒一点递归插入/删除函数返回新树根指针的写法刚开始理解起来有点别扭但这是整个AVL树实现里最优雅的设计之一。一旦接受这种模式所有节点的接回工作都被递归层自然消化代码量会少很多。6.4 工程场景下的取舍建议AVL树的查找性能是最稳定的但插入删除时的旋转次数多于红黑树。实际工程里如果查询远多于写操作比如构建一次查很多次的内存索引AVL树是很值得的选择如果写操作频繁、对绝对平衡要求不那么高红黑树可能更合适。写业务代码时我会优先考虑标准库现成的容器只有需要定制化数据结构时才会手写AVL树写学习代码时则建议两种都实现一遍只有亲手写过旋转才能真正理解这些结论是从哪来的。另一个实用小技巧模板参数可以加一个比较器让AVL树支持自定义排序规则这样在真实项目里灵活得多。代码里所有data的比较都走比较器不过为了篇幅这里的示例用了默认的运算符你可以自己扩展。最后再分享一个对我帮助最大的学习方法。当初学AVL树时我自以为把四种旋转背得滚瓜烂熟结果一关编辑器手写一棵树还是漏洞百出。后来我拿了一沓纸把LL、RR、LR、RL四种形态各画了十几棵树在每个节点边上标好高度手动推一遍旋转前后的中序序列再回到代码里比对。画完那一沓纸之后这套结构才算真正长在了脑子里。如果你也卡在旋转这里别急着背代码先拿纸笔把高度标上手动推一遍双旋的过程。等你能闭着眼说出LR型为什么必须先左旋左孩子AVL树对你来说就不再是难题了。