AVL树的实现是C数据结构路上绕不开的一道坎。不管你是准备面试、想自己写个高性能缓存还是纯粹想把平衡二叉树从背概念变成写代码手写一棵AVL树都能获得实实在在的体感你会真正理解什么叫递归回溯、为什么高度信息必须维护、四种旋转到底在旋转什么。这篇博文给出一份完整的C模板实现把节点设计、插入删除全流程、平衡修复、正确性验证逐个拆开讲最后聊聊我在实际调试中踩过的坑。代码不依赖任何第三方库g或Visual Studio都能直接编译无论你是刚入门的数据结构学习者还是已经工作多年想把基础再夯实的工程师这篇文章应该都能帮你把这部分知识从看懂变成写得出。1. 从有序插入的退化说起BST为什么需要平衡这味药1.1 有序数据让BST退化成链表先说一个我自己刚学数据结构时忽视的问题。二叉搜索树BST的规则很简单左子树节点 根节点 右子树节点。查找时一步步往下走本来期望的是O(log n)。但这个结论建立在树的形状比较均匀的前提下如果树的形状出了问题复杂度会立刻崩坏。假设你按顺序插入 1, 2, 3, 4, 51 \ 2 \ 3 \ 4 \ 5每一个新节点都跑到当前最右节点的右边整棵树变成一条斜链。这时候查找5要从根一路数下去查找一个元素是O(n)如果插入n个元素总代价就是O(n²)的噩梦。这不是理论家编出来的极端情况——日志序列号、自增主键、时间戳这些现实数据天生就是有序的裸BST在这种场景下会直接退化。我当年第一次意识到这个问题是拿一个简单的单词统计程序往BST里灌数据结果几万个词跑了好几秒一查根因就是插入顺序基本有序。从那之后我心里就有个原则凡是数据量会变大、且对查找性能有要求的场合绝不裸用BST。说到这有人会问那C里直接用std::map不行吗行而且绝大多数项目就该直接用它。但理解AVL树的价值不在替代std::map而在于你知道std::map那棵红黑树为什么能稳定地O(log n)也在于当你遇到标准库容器满足不了的场景时有能力亲手搓一棵平衡树出来。所以AVL树这个知识点既不冷门也不过时它是理解所有平衡树家族的基石。1.2 平衡因子与高度两个必须统一的定义AVL树Adelson-Velsky和Landis在1962年提出给BST加了一条硬约束对每一个节点左子树高度与右子树高度之差的绝对值不超过1。这个差就叫平衡因子公式是balanceFactor height(left) - height(right)合法值是-1、0、1。一旦某个节点的平衡因子小于-1或大于1就认为这个节点失衡需要通过旋转把它拉回合法范围。整棵AVL树就是靠每个节点局部满足这个约束来保证全局高度不会失控的。这里有一个细节必须先说清楚——高度到底怎么算。我采用的约定是空节点(nullptr)高度为0叶子节点高度为1一个节点的高度 max(左子树高度, 右子树高度) 1。也有教科书约定叶子高度为0两种都可以但代码里必须从头到尾只用一种否则平衡因子一算就全错。这是我见过新手最先翻车的地方insert的时候用约定A写delete的时候又按约定B来结果怎么调都不对。所以在你动手写之前先把这个定义钉死后面所有代码都以它为准。这条约束带来的直观结果是树的高度被严格压住。可以证明包含n个节点的AVL树最大高度约为1.44×log2(n)推导过程会用到斐波那契数列这里不展开。和完美平衡二叉树的log2(n)相比虽然多了个常数系数但量级没变所以查找仍然是O(log n)。这也是AVL树能在工程里站住脚的核心原因它不用像完全二叉树那样要求每一层都填满只要每个节点局部满足平衡约束全局高度就能被控制住而且这个约束在插入删除后通过旋转就能维护代价很小。2. 节点与类框架为什么height字段值得焊在每个节点上2.1 节点定义与代码骨架要写AVL树第一个设计决策就是节点里放什么。AVL树的节点和普通BST的节点相比只多了一个height字段template typename T struct AVLNode { T key; AVLNode* left; AVLNode* right; int height; explicit AVLNode(const T k) : key(k), left(nullptr), right(nullptr), height(1) {} };新节点一出生就是叶子高度自然是1。注意构造函数里我把key写成const T引用——如果你的键类型是std::string这种带拷贝开销的类型这个细节能省掉插入时的多余拷贝。如果你的键是int这类平凡类型编译器也会自动处理好不会有额外成本。接着是树类的骨架template typename T class AVLTree { public: AVLTree() : root_(nullptr) {} ~AVLTree() { destroy(root_); } // 禁止拷贝避免浅拷贝导致的双重释放 AVLTree(const AVLTree) delete; AVLTree operator(const AVLTree) delete; void insert(const T key) { root_ insert(root_, key); } void erase(const T key) { root_ erase(root_, key); } bool contains(const T key) const; int height() const { return getHeight(root_); } bool isBalanced() const; std::vectorT inorder() const; private: AVLNodeT* root_; void destroy(AVLNodeT* node) { if (!node) return; destroy(node-left); destroy(node-right); delete node; } // 其余辅助函数见下文各节 };这里有个工程细节想提醒你节点用的是裸指针如果不管拷贝构造编译器生成的默认拷贝构造会做浅拷贝两个对象共享同一棵树的节点析构时double free。学习代码里最稳妥的做法是直接把拷贝构造和拷贝赋值delete掉。如果你确实需要树可拷贝就得自己写深拷贝或者把成员换成std::unique_ptr——但那会让递归插入的函数签名变得麻烦涉及所有权转移作为教学代码不划算所以我选择了禁止拷贝这条路。2.2 存储height的回报O(1)的平衡因子有人会问为什么不每次现算一棵子树的高度因为一个节点的高度等于它自己子树的最大深度你要现算就得递归遍历整个子树复杂度是O(子树大小)。在平衡因子的计算里每到一个节点就要求左右子树高度要是现算光判断一次平衡就要付出O(n)的代价那整棵树的高效就全毁了AVL树存在的意义也没了。把height存在节点里代价只是4字节一个int换来的是三个实打实的好处getHeight(node)和getBalanceFactor(node)都是O(1)平衡判断不依赖子树规模插入/删除只会让从改动点到根这一条路径上的节点高度发生变化递归回溯时顺手update一下就够不用全树扫描旋转操作虽然改变父子关系但新的子树根的高度完全可以用它两个孩子现成的高度推导出来不需要重新遍历。所以height字段不是冗余数据它是AVL树的状态缓存。整棵树的正确性一半系在这个字段有没有在正确的地方被更新上。我后面讲旋转和删除的时候会反复强调这一点原因就出在这里。顺带说一句有些实现用balance factor字段代替height两者本质等价但height更通用——旋转后你需要用孩子的height重建父亲的height而如果只存bf旋转后新的bf不太好从旧的bf推出来。所以实践上存height更顺手。2.3 接口设计取舍接口上我刻意保持最小化public只有insert、erase、contains、height、isBalanced、inorder。递归的辅助函数全部放private对外暴露操作但不暴露节点结构。这里有两个取舍说明一下。第一inorder返回的是std::vector 而不是打印到屏幕。这样设计是为了方便测试——你可以拿返回结果和std::set的中序遍历直接比对而不是对着控制台肉眼判断。测试驱动才是正经路子后面第六节的对拍测试就依赖这个接口设计。第二contains可以用循环写不需要递归因为查找不改变树的结构没必要依赖递归栈template typename T bool contains(const T key) const { AVLNodeT* cur root_; while (cur) { if (key cur-key) cur cur-left; else if (key cur-key) cur cur-right; else return true; } return false; }这个循环版本比递归版本省栈空间性能也略好。std::set的find走的就是类似逻辑只不过它是红黑树比AVL多一些颜色约束和统计优化。3. 旋转操作的四种模式LL、RR、LR、RL3.1 左旋与右旋两个原子操作旋转是整个AVL树的机械部分。先把两个最基本的单旋练到手剩下的双旋只是它们的组合。先说右旋它处理的是某个节点左子树过深的情况template typename T AVLNodeT* rotateRight(AVLNodeT* y) { AVLNodeT* x y-left; AVLNodeT* t2 x-right; x-right y; y-left t2; updateHeight(y); updateHeight(x); return x; }用文本图看更清楚旋转前y / \ x T3 / \ T1 T2旋转后x / \ T1 y / \ T2 T3关键指针动作就三步x的右孩子T2过继给y当左孩子y变成x的右孩子最后把x作为新的子树根返回。注意T2这棵中间子树它是旋转里最容易丢的一棵——因为它的键值介于x和y之间旋转后挂在y的左边正好符合BST顺序。丢了T2树的有序性就崩了后面的查找全错。左旋rotateLeft完全是对称的把图左右翻过来就是代码我不重复写了。你只需要记住一个方向性的原则左旋是针对右孩子太重的情况右旋是针对左孩子太重的情况。旋的方向和重的方向是反的这一点别搞混。3.2 判断条件与记忆方法四种失衡模式的判定如果只记旋转名字很容易混。我的方法是用一张表把它固化下来每次写代码之前先对一遍失衡模式当前节点bf孩子bf处理方式LL左-左 1left孩子bf 0右旋当前节点LR左-右 1left孩子bf 0先左旋左孩子再右旋当前节点RR右-右 -1right孩子bf 0左旋当前节点RL右-左 -1right孩子bf 0先右旋右孩子再左旋当前节点名字怎么来的名字描述的是过重的路径。LL表示失衡节点的左孩子的左子树过深两次偏重都在左侧LR表示左孩子的右子树过深路径先左后右。处理方向刚好相反纯LL向左侧偏重就向右旋把重量拉回中间。RR同理。判断时的孩子bf条件别混。以LL和LR为例两者都是bf(node) 1说明左边整体偏重接下来要看node-left的bf如果它0说明偏重点还在左孩子的左侧是纯LL如果它0说明偏重点其实在左孩子的右侧表面LL实为LR。这组判断是互斥的用0和0作为分界正好把所有情况覆盖干净。3.3 双旋只是两次单旋的组合LR和RL不需要写新函数直接组合两个单旋// LR先对左孩子左旋再对当前节点右旋 node-left rotateLeft(node-left); return rotateRight(node);一开始我搞不明白为什么要先左旋左孩子。后来想通了一个类比你有一根歪向右侧的柱子直接往左掰会折得先把它底下那一截往左扶正让整根柱子的歪斜方向变成同一个方向然后再整体往右扶正。LR本质上就是先把里侧重转化成外侧重然后一次右旋彻底解决。RL完全对称先右旋右孩子再左旋当前节点。写代码的时候一定要把第一步的返回值重新赋给node-left或node-right。第一次旋转会换掉孩子子树的根你不接手这个新指针第二步旋转就作用在错误的节点上整棵树会拧成麻花。这类递归/旋转返回值必须层层接手的习惯贯穿整棵AVL树的所有操作。4. 插入流程递归插入与回溯平衡4.1 三行递归插入逻辑AVL树的插入核心逻辑其实只有三行template typename T AVLNodeT* insert(AVLNodeT* node, const T key) { if (!node) return new AVLNodeT(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; // 重复键什么都不做 return balance(node); }我见过很多人在这一步就卡住最大的疑问是为什么递归调用的返回值要重新赋给node-left / node-right原因很简单旋转会换掉子树的根。在递归深入的过程中如果下层某个节点触发了旋转那个节点会把新子树根返回给上一层上一层的代码必须立刻把这个新根接手否则手里还攥着旧指针树的结构就断裂了。这一行赋值是递归版本里保证旋转结果被父节点正确接管的关键。所有递归写树的教科书都会强调这一点但只有自己debug时看到指针变成野值才知道这行赋值是真的不能省。重复键的处理我也说一句我选择直接忽略。实际项目里如果键要唯一这是最省事的行为如果键底下还要挂value且需要更新可以改成覆盖value的写法逻辑上只是多一个赋值。4.2 统一balance函数的判定逻辑插入返回前调用的balance函数是整个AVL实现最核心的部分它把更新高度、算平衡因子、执行旋转三件事打包成一件事template typename T AVLNodeT* balance(AVLNodeT* node) { if (!node) return nullptr; updateHeight(node); int bf getBalanceFactor(node); if (bf 1 getBalanceFactor(node-left) 0) return rotateRight(node); if (bf 1 getBalanceFactor(node-left) 0) { node-left rotateLeft(node-left); return rotateRight(node); } if (bf -1 getBalanceFactor(node-right) 0) return rotateLeft(node); if (bf -1 getBalanceFactor(node-right) 0) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }配套的三个O(1)辅助函数也很关键template typename T int getHeight(AVLNodeT* node) { return node ? node-height : 0; } template typename T int getBalanceFactor(AVLNodeT* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; } template typename T void updateHeight(AVLNodeT* node) { if (node) node-height 1 std::max(getHeight(node-left), getHeight(node-right)); }特别提醒一个最容易忽略的点getHeight必须先判断node是否为空空节点返回0这是整个高度体系的地基。有人图省事直接写node-height一旦遇到空指针就崩而且这种崩溃往往出现在深层递归里调用栈一坨查半天也想不到问题出在这。4.3 插入为什么最多只需一次旋转教科书上说AVL树插入后最多做一次单或双旋转就能恢复平衡。刚开始我很疑惑插入路径上那么多祖先节点万一上一层的祖先也失衡了呢为什么代码里只在每个递归层次依次balance却不会出现需要连续旋转多次的情况原因在于插入只会让某棵子树的高度最多增加1。假设从插入点往上找第一个失衡的节点是A那么在A这里做一次旋转之后A这棵子树的高度会恢复到插入之前的值。A的祖先们看到的局面是自己某棵子树的高度和插入前一样平衡因子自然恢复合法不需要再转。所以代码虽然递归地检查了所有祖先但一路上只会真正触发一次旋转。不过这里要强调这个性质是插入特有的删除并不具备。删除会让子树高度减1旋转后不一定能恢复到删除前的高度所以可能要一路修到根。这是下一节的核心内容。5. 删除流程最容易翻车的环节5.1 三种情况的处理删除一个节点按孩子的数量分成三种情况叶子节点直接删掉返回空指针给父节点只有一个孩子用这个孩子顶替被删节点两个孩子标准的做法是找右子树里的最小节点中序后继把它的键复制到当前节点然后递归删除那个后继。为什么用中序后继因为它刚好是大于当前键的最小值用它顶上来BST的有序性不会被破坏。也可以找左子树的最大节点前驱效果等价选哪个都行但要保持一致。代码是这一段template typename T AVLNodeT* erase(AVLNodeT* node, const T key) { if (!node) return nullptr; if (key node-key) { node-left erase(node-left, key); } else if (key node-key) { node-right erase(node-right, key); } else { // 找到待删节点 if (node-left node-right) { // 两个孩子用中序后继替换 AVLNodeT* succ findMin(node-right); node-key succ-key; node-right erase(node-right, succ-key); } else { // 零个或一个孩子 AVLNodeT* child node-left ? node-left : node-right; AVLNodeT* old node; node child; delete old; } } return balance(node); }findMin就是一路往左走到头template typename T AVLNodeT* findMin(AVLNodeT* node) { while (node node-left) node node-left; return node; }注意每个递归返回层都会调一次balance也就是说从被删节点一路向上每一层都重新算高度、查平衡、转该转的旋转。这就是删除比插入重的地方也是很多实现翻车的根源。5.2 删除后为什么可能一路修到根刚才说过删除会让某棵子树的高度减1就算你在当前节点转了一次旋转把局部平衡恢复了这次旋转本身可能让这棵子树的总高度比删除前还少1——那就意味着它的父节点也面临新的失衡得继续处理。如此一路向上最坏情况下会一路旋到根节点共O(log n)次。这里我不再手动构造那个复杂的例子了你只要记住一个画面删除是在一棵树里抠走一块空缺会引发连环的尺寸调整像抽掉积木塔底部的一块上面的每一层都得重新评估重心。插入则是多出一块局部压一次弹簧就能稳住。这个区别直接决定了插入的balance放在递归返回的路上没问题删除的balance也必须放在递归返回的路上而且每一步都不能漏。我见过的一个经典bug就是作者只在找到节点的分支里写了balance删除路径上的祖先全部没有更新高度平衡因子全乱查出来的树又矮又歪症状还时好时坏特别难定位。所以请记住return balance(node)这行必须放在erase函数每个递归返回都会经过的位置而不是放在某个分支内部。5.3 删除单孩子节点时的一个指针细节单孩子或叶子的分支里我用了node child然后delete old的写法。这实际上是在说让当前指针指向孩子然后释放旧节点。调用它的父节点会收到这个新指针也就是孩子整个结构就无缝衔接了。这里有个初看很绕的地方如果node是叶子child是nullptr那delete old删掉叶子后返回的是nullptr父节点对应侧的指针就变成空了逻辑正确。如果node有一个孩子就返回给孩子父节点指向孩子的子树被删节点就被摘掉了。整个过程不需要parent指针纯靠递归返回值层层传递新位置这也是递归写法在树结构里的优势。另一个细节在两个孩子分支里把后继的键拷贝给node之后node-right erase(node-right, succ-key)会去右子树里删掉那个后继。那个后继必然是右子树里最左的节点它最多只有一个孩子只可能有右孩子不可能有左孩子所以递归会正确收敛不会无限套娃。这个性质是找最小节点的天然保障写的时候不用额外加判断。6. 测试与验证如何确定这棵树真的没写错6.1 有序性与平衡性分开验证写完AVL树最忌讳的是拿一两个用例跑一下就宣告成功。树这东西的bug往往藏在特定插入顺序、特定删除组合里。我的做法是把正确性拆成两个互相独立的条件来验证有序性和平衡性。第一有序性。任何一棵二叉搜索树无论怎么插入删除中序遍历的结果必须是升序。这是BST的基础性质AVL只是额外加了平衡约束不能破坏有序性。验证方法很简单std::vectorT result tree.inorder(); bool sorted std::is_sorted(result.begin(), result.end());第二平衡性。每个节点的平衡因子绝对值不超过1。注意只验证平衡因子还不够还要验证存的高度和真实子树高度一致——否则可能是假平衡节点说自己平衡但高度记录本身已经错乱。一个更严格的验证函数要同时做三件事递归验证左右子树检查node-height是否等于max(左高, 右高)1检查左右高度差绝对值是否1。template typename T bool verify(AVLNodeT* node, int height) { if (!node) { height 0; return true; } int hl 0, hr 0; if (!verify(node-left, hl)) return false; if (!verify(node-right, hr)) return false; if (node-height ! 1 std::max(hl, hr)) return false; // 高度记录错误 if (std::abs(hl - hr) 1) return false; // 平衡被破坏 height node-height; return true; }这个verify比单纯的isBalanced更强它能直接暴露忘记updateHeight这类的隐藏bug。这类bug往往要跑很多随机用例才会偶然浮出水面但用verify一查就是当场现形。6.2 用std::set当参照物的随机对拍比手写测试用例更狠的招数是对拍。思路很简单std::set也是有序平衡树红黑树虽然内部结构不同但同一组键的中序遍历结果必定完全一致。那我们就可以拿它当标准答案对我们的AVL树执行同样的一串操作每步做完比对一下inorder结果#include random #include set #include vector std::mt19937 rng(42); AVLTreeint tree; std::setint ref; for (int i 0; i 10000; i) { int key static_castint(rng() % 100000); if (rng() % 2 0) { tree.insert(key); ref.insert(key); } else { tree.erase(key); ref.erase(key); } if (i % 100 0) { auto a tree.inorder(); std::vectorint b(ref.begin(), ref.end()); if (a ! b) { // 打印出错的key和操作序号人工介入 break; } } }这段代码里我加了一个if (i % 100 0)的采样检查避免每一步都对拍导致整体太慢。一旦发现不一致立刻终止并打印出错的键、操作序号再配合调试器一步步回放。这个方法的妙处在于你不需要人工构造正确输出。红黑树和AVL树在中序遍历上是同一回事排序结果不会因为内部结构不同而不同。哪怕你的AVL代码内部旋转全错了只要中序结果和std::set一致至少有序性没坏再配合前面的verify平衡性也有了保障。两个条件合起来正确性基本就锁死了。6.3 必测的边界场景除了随机对拍下面这些边界场景我建议手写用例单独跑一遍它们往往是bug的密集区空树insert、erase、inorder都不崩单节点删除它之后树要恢复为空连续有序插入1..N这是BST最疼的场景对AVL反而是家常便饭连续逆序插入N..1检验对称的RR/RL路径重复键确认被安全忽略不产生额外节点也不破坏高度删除只有右孩子的节点、只有左孩子的节点分别覆盖单孩子替换的两侧分支删除根节点且根节点有两个孩子覆盖后继替换加递归删除后继的组合交叉操作插入几个删一个再插再删制造多轮旋转。我一般把这些写在一个test.cpp里配合上面的verify和std::set对拍一起跑。一百万个随机操作下来如果全绿这棵树就能放心拿去用了。7. 调试经验与性能实测手记7.1 三个最容易踩的坑写AVL树的实现我从零到完全跑通遇到过三个反复踩的坑放在这里算是给大家扫雷。第一个坑旋转后忘了更新高度或者更新顺序搞反。右旋里必须先updateHeight(y)再updateHeight(x)因为旋转后y成了x的孩子x的高度要依赖y的新高度。顺序反了x用的就是y的旧高度算出来的结果差1到2不等且只在特定树形下出错特别隐蔽。我的检查习惯是写完旋转函数先手动跑一遍3个节点的LL场景逐步打印每个节点旋转前后的height确认无误再做下一步。第二个坑双旋时直接对当前节点做反向单旋。LR场景里有人看到bf(node) 1就顺手rotateRight(node)结果树从一边歪变成另一边歪怎么调都差一口气。正确做法是先左旋node-left让失衡路径变成同向再右旋node。牢记那根歪柱子的类比双旋就先扶正里侧再处理外侧。第三个坑删除场景里把balance写在错误的路径上。前面说过删除后每个递归返回层都要balance不能只在找到节点的分支里处理。这个坑的典型症状是删除一个节点后某段时间树看起来正常但高度记录已经乱掉随后插入几次突然出现奇怪的不平衡查bug查到怀疑人生。排查这类问题我强烈建议用AddressSanitizer或Valgrind。一个很常见的隐性bug是删除时的内存释放顺序错乱导致use-after-free——这种bug光靠肉眼和printf根本不可能发现ASan一跑就直接给你定位到出错行。7.2 实测数据AVL vs 裸BST vs std::map为了对AVL树的性能有直观手感我用同一组数据对比过几种实现。测试环境很普通单线程Release编译插入10万个有序整数。裸BST在有序插入下总比较次数约50亿次实测耗时数十秒基本不可用AVL树本文实现总比较次数约170万次耗时在毫秒到几十毫秒级别树高稳定在17左右std::map红黑树性能量级和AVL接近插入略快一点点但高度控制不如AVL紧。数字会随编译器和机器波动但量级差异是稳的。这个实验我建议你自己跑一遍体会会更深——尤其是有序插入那个场景裸BST从开始的毫秒级到最后越来越慢那种肉眼可见的退化非常震撼。而AVL树全程保持稳定每次插入路径长度都差不多这就是平衡的价值。顺带验证一下第3节的结论AVL树高大约1.44×log2(n)10万个节点算下来18左右和实测17完全对上。7.3 选型建议再多说几句工程层面的实话。现代C项目里绝大多数场景直接用std::map或std::unordered_map就好没必要手写AVL树。真正需要AVL的场景通常是读多写少、且很在意树高AVL比红黑树更矮查找更稳定需要自定义分配器或对节点布局有特殊要求标准库容器满足不了面试或教学场需要展示你对递归和旋转的理解。我自己在实际项目里手写AVL树是因为一个工具没法依赖标准库的高层容器只能把关键数据结构自己带进来。那次经历让我明白手写AVL真正的价值不在于替代std::map而在于当你要和底层数据布局打交道时你有能力在半小时内搓出一棵能跑的平衡树并且清楚地知道它的边界在哪里。这种能力是刷再多八股文也给不了的。 
长河君 · 2026/10/10 5:33:02 · 阅读 1.2k C++手写AVL树：旋转、插入删除与验证调试全解析
AVL树的实现是C数据结构路上绕不开的一道坎。不管你是准备面试、想自己写个高性能缓存还是纯粹想把平衡二叉树从背概念变成写代码手写一棵AVL树都能获得实实在在的体感你会真正理解什么叫递归回溯、为什么高度信息必须维护、四种旋转到底在旋转什么。这篇博文给出一份完整的C模板实现把节点设计、插入删除全流程、平衡修复、正确性验证逐个拆开讲最后聊聊我在实际调试中踩过的坑。代码不依赖任何第三方库g或Visual Studio都能直接编译无论你是刚入门的数据结构学习者还是已经工作多年想把基础再夯实的工程师这篇文章应该都能帮你把这部分知识从看懂变成写得出。1. 从有序插入的退化说起BST为什么需要平衡这味药1.1 有序数据让BST退化成链表先说一个我自己刚学数据结构时忽视的问题。二叉搜索树BST的规则很简单左子树节点 根节点 右子树节点。查找时一步步往下走本来期望的是O(log n)。但这个结论建立在树的形状比较均匀的前提下如果树的形状出了问题复杂度会立刻崩坏。假设你按顺序插入 1, 2, 3, 4, 51 \ 2 \ 3 \ 4 \ 5每一个新节点都跑到当前最右节点的右边整棵树变成一条斜链。这时候查找5要从根一路数下去查找一个元素是O(n)如果插入n个元素总代价就是O(n²)的噩梦。这不是理论家编出来的极端情况——日志序列号、自增主键、时间戳这些现实数据天生就是有序的裸BST在这种场景下会直接退化。我当年第一次意识到这个问题是拿一个简单的单词统计程序往BST里灌数据结果几万个词跑了好几秒一查根因就是插入顺序基本有序。从那之后我心里就有个原则凡是数据量会变大、且对查找性能有要求的场合绝不裸用BST。说到这有人会问那C里直接用std::map不行吗行而且绝大多数项目就该直接用它。但理解AVL树的价值不在替代std::map而在于你知道std::map那棵红黑树为什么能稳定地O(log n)也在于当你遇到标准库容器满足不了的场景时有能力亲手搓一棵平衡树出来。所以AVL树这个知识点既不冷门也不过时它是理解所有平衡树家族的基石。1.2 平衡因子与高度两个必须统一的定义AVL树Adelson-Velsky和Landis在1962年提出给BST加了一条硬约束对每一个节点左子树高度与右子树高度之差的绝对值不超过1。这个差就叫平衡因子公式是balanceFactor height(left) - height(right)合法值是-1、0、1。一旦某个节点的平衡因子小于-1或大于1就认为这个节点失衡需要通过旋转把它拉回合法范围。整棵AVL树就是靠每个节点局部满足这个约束来保证全局高度不会失控的。这里有一个细节必须先说清楚——高度到底怎么算。我采用的约定是空节点(nullptr)高度为0叶子节点高度为1一个节点的高度 max(左子树高度, 右子树高度) 1。也有教科书约定叶子高度为0两种都可以但代码里必须从头到尾只用一种否则平衡因子一算就全错。这是我见过新手最先翻车的地方insert的时候用约定A写delete的时候又按约定B来结果怎么调都不对。所以在你动手写之前先把这个定义钉死后面所有代码都以它为准。这条约束带来的直观结果是树的高度被严格压住。可以证明包含n个节点的AVL树最大高度约为1.44×log2(n)推导过程会用到斐波那契数列这里不展开。和完美平衡二叉树的log2(n)相比虽然多了个常数系数但量级没变所以查找仍然是O(log n)。这也是AVL树能在工程里站住脚的核心原因它不用像完全二叉树那样要求每一层都填满只要每个节点局部满足平衡约束全局高度就能被控制住而且这个约束在插入删除后通过旋转就能维护代价很小。2. 节点与类框架为什么height字段值得焊在每个节点上2.1 节点定义与代码骨架要写AVL树第一个设计决策就是节点里放什么。AVL树的节点和普通BST的节点相比只多了一个height字段template typename T struct AVLNode { T key; AVLNode* left; AVLNode* right; int height; explicit AVLNode(const T k) : key(k), left(nullptr), right(nullptr), height(1) {} };新节点一出生就是叶子高度自然是1。注意构造函数里我把key写成const T引用——如果你的键类型是std::string这种带拷贝开销的类型这个细节能省掉插入时的多余拷贝。如果你的键是int这类平凡类型编译器也会自动处理好不会有额外成本。接着是树类的骨架template typename T class AVLTree { public: AVLTree() : root_(nullptr) {} ~AVLTree() { destroy(root_); } // 禁止拷贝避免浅拷贝导致的双重释放 AVLTree(const AVLTree) delete; AVLTree operator(const AVLTree) delete; void insert(const T key) { root_ insert(root_, key); } void erase(const T key) { root_ erase(root_, key); } bool contains(const T key) const; int height() const { return getHeight(root_); } bool isBalanced() const; std::vectorT inorder() const; private: AVLNodeT* root_; void destroy(AVLNodeT* node) { if (!node) return; destroy(node-left); destroy(node-right); delete node; } // 其余辅助函数见下文各节 };这里有个工程细节想提醒你节点用的是裸指针如果不管拷贝构造编译器生成的默认拷贝构造会做浅拷贝两个对象共享同一棵树的节点析构时double free。学习代码里最稳妥的做法是直接把拷贝构造和拷贝赋值delete掉。如果你确实需要树可拷贝就得自己写深拷贝或者把成员换成std::unique_ptr——但那会让递归插入的函数签名变得麻烦涉及所有权转移作为教学代码不划算所以我选择了禁止拷贝这条路。2.2 存储height的回报O(1)的平衡因子有人会问为什么不每次现算一棵子树的高度因为一个节点的高度等于它自己子树的最大深度你要现算就得递归遍历整个子树复杂度是O(子树大小)。在平衡因子的计算里每到一个节点就要求左右子树高度要是现算光判断一次平衡就要付出O(n)的代价那整棵树的高效就全毁了AVL树存在的意义也没了。把height存在节点里代价只是4字节一个int换来的是三个实打实的好处getHeight(node)和getBalanceFactor(node)都是O(1)平衡判断不依赖子树规模插入/删除只会让从改动点到根这一条路径上的节点高度发生变化递归回溯时顺手update一下就够不用全树扫描旋转操作虽然改变父子关系但新的子树根的高度完全可以用它两个孩子现成的高度推导出来不需要重新遍历。所以height字段不是冗余数据它是AVL树的状态缓存。整棵树的正确性一半系在这个字段有没有在正确的地方被更新上。我后面讲旋转和删除的时候会反复强调这一点原因就出在这里。顺带说一句有些实现用balance factor字段代替height两者本质等价但height更通用——旋转后你需要用孩子的height重建父亲的height而如果只存bf旋转后新的bf不太好从旧的bf推出来。所以实践上存height更顺手。2.3 接口设计取舍接口上我刻意保持最小化public只有insert、erase、contains、height、isBalanced、inorder。递归的辅助函数全部放private对外暴露操作但不暴露节点结构。这里有两个取舍说明一下。第一inorder返回的是std::vector 而不是打印到屏幕。这样设计是为了方便测试——你可以拿返回结果和std::set的中序遍历直接比对而不是对着控制台肉眼判断。测试驱动才是正经路子后面第六节的对拍测试就依赖这个接口设计。第二contains可以用循环写不需要递归因为查找不改变树的结构没必要依赖递归栈template typename T bool contains(const T key) const { AVLNodeT* cur root_; while (cur) { if (key cur-key) cur cur-left; else if (key cur-key) cur cur-right; else return true; } return false; }这个循环版本比递归版本省栈空间性能也略好。std::set的find走的就是类似逻辑只不过它是红黑树比AVL多一些颜色约束和统计优化。3. 旋转操作的四种模式LL、RR、LR、RL3.1 左旋与右旋两个原子操作旋转是整个AVL树的机械部分。先把两个最基本的单旋练到手剩下的双旋只是它们的组合。先说右旋它处理的是某个节点左子树过深的情况template typename T AVLNodeT* rotateRight(AVLNodeT* y) { AVLNodeT* x y-left; AVLNodeT* t2 x-right; x-right y; y-left t2; updateHeight(y); updateHeight(x); return x; }用文本图看更清楚旋转前y / \ x T3 / \ T1 T2旋转后x / \ T1 y / \ T2 T3关键指针动作就三步x的右孩子T2过继给y当左孩子y变成x的右孩子最后把x作为新的子树根返回。注意T2这棵中间子树它是旋转里最容易丢的一棵——因为它的键值介于x和y之间旋转后挂在y的左边正好符合BST顺序。丢了T2树的有序性就崩了后面的查找全错。左旋rotateLeft完全是对称的把图左右翻过来就是代码我不重复写了。你只需要记住一个方向性的原则左旋是针对右孩子太重的情况右旋是针对左孩子太重的情况。旋的方向和重的方向是反的这一点别搞混。3.2 判断条件与记忆方法四种失衡模式的判定如果只记旋转名字很容易混。我的方法是用一张表把它固化下来每次写代码之前先对一遍失衡模式当前节点bf孩子bf处理方式LL左-左 1left孩子bf 0右旋当前节点LR左-右 1left孩子bf 0先左旋左孩子再右旋当前节点RR右-右 -1right孩子bf 0左旋当前节点RL右-左 -1right孩子bf 0先右旋右孩子再左旋当前节点名字怎么来的名字描述的是过重的路径。LL表示失衡节点的左孩子的左子树过深两次偏重都在左侧LR表示左孩子的右子树过深路径先左后右。处理方向刚好相反纯LL向左侧偏重就向右旋把重量拉回中间。RR同理。判断时的孩子bf条件别混。以LL和LR为例两者都是bf(node) 1说明左边整体偏重接下来要看node-left的bf如果它0说明偏重点还在左孩子的左侧是纯LL如果它0说明偏重点其实在左孩子的右侧表面LL实为LR。这组判断是互斥的用0和0作为分界正好把所有情况覆盖干净。3.3 双旋只是两次单旋的组合LR和RL不需要写新函数直接组合两个单旋// LR先对左孩子左旋再对当前节点右旋 node-left rotateLeft(node-left); return rotateRight(node);一开始我搞不明白为什么要先左旋左孩子。后来想通了一个类比你有一根歪向右侧的柱子直接往左掰会折得先把它底下那一截往左扶正让整根柱子的歪斜方向变成同一个方向然后再整体往右扶正。LR本质上就是先把里侧重转化成外侧重然后一次右旋彻底解决。RL完全对称先右旋右孩子再左旋当前节点。写代码的时候一定要把第一步的返回值重新赋给node-left或node-right。第一次旋转会换掉孩子子树的根你不接手这个新指针第二步旋转就作用在错误的节点上整棵树会拧成麻花。这类递归/旋转返回值必须层层接手的习惯贯穿整棵AVL树的所有操作。4. 插入流程递归插入与回溯平衡4.1 三行递归插入逻辑AVL树的插入核心逻辑其实只有三行template typename T AVLNodeT* insert(AVLNodeT* node, const T key) { if (!node) return new AVLNodeT(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; // 重复键什么都不做 return balance(node); }我见过很多人在这一步就卡住最大的疑问是为什么递归调用的返回值要重新赋给node-left / node-right原因很简单旋转会换掉子树的根。在递归深入的过程中如果下层某个节点触发了旋转那个节点会把新子树根返回给上一层上一层的代码必须立刻把这个新根接手否则手里还攥着旧指针树的结构就断裂了。这一行赋值是递归版本里保证旋转结果被父节点正确接管的关键。所有递归写树的教科书都会强调这一点但只有自己debug时看到指针变成野值才知道这行赋值是真的不能省。重复键的处理我也说一句我选择直接忽略。实际项目里如果键要唯一这是最省事的行为如果键底下还要挂value且需要更新可以改成覆盖value的写法逻辑上只是多一个赋值。4.2 统一balance函数的判定逻辑插入返回前调用的balance函数是整个AVL实现最核心的部分它把更新高度、算平衡因子、执行旋转三件事打包成一件事template typename T AVLNodeT* balance(AVLNodeT* node) { if (!node) return nullptr; updateHeight(node); int bf getBalanceFactor(node); if (bf 1 getBalanceFactor(node-left) 0) return rotateRight(node); if (bf 1 getBalanceFactor(node-left) 0) { node-left rotateLeft(node-left); return rotateRight(node); } if (bf -1 getBalanceFactor(node-right) 0) return rotateLeft(node); if (bf -1 getBalanceFactor(node-right) 0) { node-right rotateRight(node-right); return rotateLeft(node); } return node; }配套的三个O(1)辅助函数也很关键template typename T int getHeight(AVLNodeT* node) { return node ? node-height : 0; } template typename T int getBalanceFactor(AVLNodeT* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; } template typename T void updateHeight(AVLNodeT* node) { if (node) node-height 1 std::max(getHeight(node-left), getHeight(node-right)); }特别提醒一个最容易忽略的点getHeight必须先判断node是否为空空节点返回0这是整个高度体系的地基。有人图省事直接写node-height一旦遇到空指针就崩而且这种崩溃往往出现在深层递归里调用栈一坨查半天也想不到问题出在这。4.3 插入为什么最多只需一次旋转教科书上说AVL树插入后最多做一次单或双旋转就能恢复平衡。刚开始我很疑惑插入路径上那么多祖先节点万一上一层的祖先也失衡了呢为什么代码里只在每个递归层次依次balance却不会出现需要连续旋转多次的情况原因在于插入只会让某棵子树的高度最多增加1。假设从插入点往上找第一个失衡的节点是A那么在A这里做一次旋转之后A这棵子树的高度会恢复到插入之前的值。A的祖先们看到的局面是自己某棵子树的高度和插入前一样平衡因子自然恢复合法不需要再转。所以代码虽然递归地检查了所有祖先但一路上只会真正触发一次旋转。不过这里要强调这个性质是插入特有的删除并不具备。删除会让子树高度减1旋转后不一定能恢复到删除前的高度所以可能要一路修到根。这是下一节的核心内容。5. 删除流程最容易翻车的环节5.1 三种情况的处理删除一个节点按孩子的数量分成三种情况叶子节点直接删掉返回空指针给父节点只有一个孩子用这个孩子顶替被删节点两个孩子标准的做法是找右子树里的最小节点中序后继把它的键复制到当前节点然后递归删除那个后继。为什么用中序后继因为它刚好是大于当前键的最小值用它顶上来BST的有序性不会被破坏。也可以找左子树的最大节点前驱效果等价选哪个都行但要保持一致。代码是这一段template typename T AVLNodeT* erase(AVLNodeT* node, const T key) { if (!node) return nullptr; if (key node-key) { node-left erase(node-left, key); } else if (key node-key) { node-right erase(node-right, key); } else { // 找到待删节点 if (node-left node-right) { // 两个孩子用中序后继替换 AVLNodeT* succ findMin(node-right); node-key succ-key; node-right erase(node-right, succ-key); } else { // 零个或一个孩子 AVLNodeT* child node-left ? node-left : node-right; AVLNodeT* old node; node child; delete old; } } return balance(node); }findMin就是一路往左走到头template typename T AVLNodeT* findMin(AVLNodeT* node) { while (node node-left) node node-left; return node; }注意每个递归返回层都会调一次balance也就是说从被删节点一路向上每一层都重新算高度、查平衡、转该转的旋转。这就是删除比插入重的地方也是很多实现翻车的根源。5.2 删除后为什么可能一路修到根刚才说过删除会让某棵子树的高度减1就算你在当前节点转了一次旋转把局部平衡恢复了这次旋转本身可能让这棵子树的总高度比删除前还少1——那就意味着它的父节点也面临新的失衡得继续处理。如此一路向上最坏情况下会一路旋到根节点共O(log n)次。这里我不再手动构造那个复杂的例子了你只要记住一个画面删除是在一棵树里抠走一块空缺会引发连环的尺寸调整像抽掉积木塔底部的一块上面的每一层都得重新评估重心。插入则是多出一块局部压一次弹簧就能稳住。这个区别直接决定了插入的balance放在递归返回的路上没问题删除的balance也必须放在递归返回的路上而且每一步都不能漏。我见过的一个经典bug就是作者只在找到节点的分支里写了balance删除路径上的祖先全部没有更新高度平衡因子全乱查出来的树又矮又歪症状还时好时坏特别难定位。所以请记住return balance(node)这行必须放在erase函数每个递归返回都会经过的位置而不是放在某个分支内部。5.3 删除单孩子节点时的一个指针细节单孩子或叶子的分支里我用了node child然后delete old的写法。这实际上是在说让当前指针指向孩子然后释放旧节点。调用它的父节点会收到这个新指针也就是孩子整个结构就无缝衔接了。这里有个初看很绕的地方如果node是叶子child是nullptr那delete old删掉叶子后返回的是nullptr父节点对应侧的指针就变成空了逻辑正确。如果node有一个孩子就返回给孩子父节点指向孩子的子树被删节点就被摘掉了。整个过程不需要parent指针纯靠递归返回值层层传递新位置这也是递归写法在树结构里的优势。另一个细节在两个孩子分支里把后继的键拷贝给node之后node-right erase(node-right, succ-key)会去右子树里删掉那个后继。那个后继必然是右子树里最左的节点它最多只有一个孩子只可能有右孩子不可能有左孩子所以递归会正确收敛不会无限套娃。这个性质是找最小节点的天然保障写的时候不用额外加判断。6. 测试与验证如何确定这棵树真的没写错6.1 有序性与平衡性分开验证写完AVL树最忌讳的是拿一两个用例跑一下就宣告成功。树这东西的bug往往藏在特定插入顺序、特定删除组合里。我的做法是把正确性拆成两个互相独立的条件来验证有序性和平衡性。第一有序性。任何一棵二叉搜索树无论怎么插入删除中序遍历的结果必须是升序。这是BST的基础性质AVL只是额外加了平衡约束不能破坏有序性。验证方法很简单std::vectorT result tree.inorder(); bool sorted std::is_sorted(result.begin(), result.end());第二平衡性。每个节点的平衡因子绝对值不超过1。注意只验证平衡因子还不够还要验证存的高度和真实子树高度一致——否则可能是假平衡节点说自己平衡但高度记录本身已经错乱。一个更严格的验证函数要同时做三件事递归验证左右子树检查node-height是否等于max(左高, 右高)1检查左右高度差绝对值是否1。template typename T bool verify(AVLNodeT* node, int height) { if (!node) { height 0; return true; } int hl 0, hr 0; if (!verify(node-left, hl)) return false; if (!verify(node-right, hr)) return false; if (node-height ! 1 std::max(hl, hr)) return false; // 高度记录错误 if (std::abs(hl - hr) 1) return false; // 平衡被破坏 height node-height; return true; }这个verify比单纯的isBalanced更强它能直接暴露忘记updateHeight这类的隐藏bug。这类bug往往要跑很多随机用例才会偶然浮出水面但用verify一查就是当场现形。6.2 用std::set当参照物的随机对拍比手写测试用例更狠的招数是对拍。思路很简单std::set也是有序平衡树红黑树虽然内部结构不同但同一组键的中序遍历结果必定完全一致。那我们就可以拿它当标准答案对我们的AVL树执行同样的一串操作每步做完比对一下inorder结果#include random #include set #include vector std::mt19937 rng(42); AVLTreeint tree; std::setint ref; for (int i 0; i 10000; i) { int key static_castint(rng() % 100000); if (rng() % 2 0) { tree.insert(key); ref.insert(key); } else { tree.erase(key); ref.erase(key); } if (i % 100 0) { auto a tree.inorder(); std::vectorint b(ref.begin(), ref.end()); if (a ! b) { // 打印出错的key和操作序号人工介入 break; } } }这段代码里我加了一个if (i % 100 0)的采样检查避免每一步都对拍导致整体太慢。一旦发现不一致立刻终止并打印出错的键、操作序号再配合调试器一步步回放。这个方法的妙处在于你不需要人工构造正确输出。红黑树和AVL树在中序遍历上是同一回事排序结果不会因为内部结构不同而不同。哪怕你的AVL代码内部旋转全错了只要中序结果和std::set一致至少有序性没坏再配合前面的verify平衡性也有了保障。两个条件合起来正确性基本就锁死了。6.3 必测的边界场景除了随机对拍下面这些边界场景我建议手写用例单独跑一遍它们往往是bug的密集区空树insert、erase、inorder都不崩单节点删除它之后树要恢复为空连续有序插入1..N这是BST最疼的场景对AVL反而是家常便饭连续逆序插入N..1检验对称的RR/RL路径重复键确认被安全忽略不产生额外节点也不破坏高度删除只有右孩子的节点、只有左孩子的节点分别覆盖单孩子替换的两侧分支删除根节点且根节点有两个孩子覆盖后继替换加递归删除后继的组合交叉操作插入几个删一个再插再删制造多轮旋转。我一般把这些写在一个test.cpp里配合上面的verify和std::set对拍一起跑。一百万个随机操作下来如果全绿这棵树就能放心拿去用了。7. 调试经验与性能实测手记7.1 三个最容易踩的坑写AVL树的实现我从零到完全跑通遇到过三个反复踩的坑放在这里算是给大家扫雷。第一个坑旋转后忘了更新高度或者更新顺序搞反。右旋里必须先updateHeight(y)再updateHeight(x)因为旋转后y成了x的孩子x的高度要依赖y的新高度。顺序反了x用的就是y的旧高度算出来的结果差1到2不等且只在特定树形下出错特别隐蔽。我的检查习惯是写完旋转函数先手动跑一遍3个节点的LL场景逐步打印每个节点旋转前后的height确认无误再做下一步。第二个坑双旋时直接对当前节点做反向单旋。LR场景里有人看到bf(node) 1就顺手rotateRight(node)结果树从一边歪变成另一边歪怎么调都差一口气。正确做法是先左旋node-left让失衡路径变成同向再右旋node。牢记那根歪柱子的类比双旋就先扶正里侧再处理外侧。第三个坑删除场景里把balance写在错误的路径上。前面说过删除后每个递归返回层都要balance不能只在找到节点的分支里处理。这个坑的典型症状是删除一个节点后某段时间树看起来正常但高度记录已经乱掉随后插入几次突然出现奇怪的不平衡查bug查到怀疑人生。排查这类问题我强烈建议用AddressSanitizer或Valgrind。一个很常见的隐性bug是删除时的内存释放顺序错乱导致use-after-free——这种bug光靠肉眼和printf根本不可能发现ASan一跑就直接给你定位到出错行。7.2 实测数据AVL vs 裸BST vs std::map为了对AVL树的性能有直观手感我用同一组数据对比过几种实现。测试环境很普通单线程Release编译插入10万个有序整数。裸BST在有序插入下总比较次数约50亿次实测耗时数十秒基本不可用AVL树本文实现总比较次数约170万次耗时在毫秒到几十毫秒级别树高稳定在17左右std::map红黑树性能量级和AVL接近插入略快一点点但高度控制不如AVL紧。数字会随编译器和机器波动但量级差异是稳的。这个实验我建议你自己跑一遍体会会更深——尤其是有序插入那个场景裸BST从开始的毫秒级到最后越来越慢那种肉眼可见的退化非常震撼。而AVL树全程保持稳定每次插入路径长度都差不多这就是平衡的价值。顺带验证一下第3节的结论AVL树高大约1.44×log2(n)10万个节点算下来18左右和实测17完全对上。7.3 选型建议再多说几句工程层面的实话。现代C项目里绝大多数场景直接用std::map或std::unordered_map就好没必要手写AVL树。真正需要AVL的场景通常是读多写少、且很在意树高AVL比红黑树更矮查找更稳定需要自定义分配器或对节点布局有特殊要求标准库容器满足不了面试或教学场需要展示你对递归和旋转的理解。我自己在实际项目里手写AVL树是因为一个工具没法依赖标准库的高层容器只能把关键数据结构自己带进来。那次经历让我明白手写AVL真正的价值不在于替代std::map而在于当你要和底层数据布局打交道时你有能力在半小时内搓出一棵能跑的平衡树并且清楚地知道它的边界在哪里。这种能力是刷再多八股文也给不了的。