AVL树这个东西我相信不少准备C面试的朋友都背过、画过、也手写过。它本质上就是在普通二叉搜索树BST上加了一条硬性约束任意节点的左右子树高度差绝对值不能超过1。这条约束让树始终保持严格平衡查找、插入、删除的复杂度稳定在O(log n)不会因为数据有序插入而退化成链表。我这次用C从零实现了一棵支持插入、删除、查找、旋转调整和平衡性验证的AVL树代码可以直接编译运行。如果你正在准备校招面试或者想在项目里自己做一个“有序Key-Value容器”这篇很值得看完。全文不跳步骤从节点定义讲到四种旋转再从插入删除讲到调试技巧。1. 动手前要想清楚的设计决策1.1 为什么不能直接用普通BST很多初学者写过BST后会觉得“直接插就完了”但问题在于数据顺序。你尝试连续插入[1,2,3,4,...,n]普通BST会变成一棵只有右子树的斜树查找最后一个元素要遍历n次等于线性表。AVL树的优势恰恰体现在这种“最坏情况”下每次插入或删除后它会通过旋转调整高度差让树的深度始终维持在O(log n)级别。以100万个有序节点为例普通BST查找最差需要100万次比较而AVL树只需要约20次。在实时性要求高、读操作远多于写操作的业务场景里这个差异是巨大的。1.2 递归还是迭代我用的是递归实现。递归在插入、删除时天然带着“回溯路径”每一层递归返回时都能检查当前子树是否失衡不需要手动维护祖先栈。如果你非要用迭代那插入后还得额外保存一条从根到插入点的路径栈删除时更麻烦因为还要处理后继节点的替换和回溯。递归方案的代码更短、更直观代价是递归深度等于树高栈空间消耗为O(log n)这在平衡树里完全可以接受。1.3 接口形状怎么设计为了演示核心逻辑我采用 int 类型的 key 和 value暴露的接口是insert(key, value)、erase(key)、find(key)、contains(key)、inorder()、isBalanced()。如果你想复用到项目里改成模板类很简单第9节我会单独讲。还有一个关键设计插入和删除的辅助函数都返回“新的子树根节点”调用方必须把返回值接住比如 node-left insert(node-left, key, value)。这个习惯是避免悬垂指针和逻辑错误的根本保证。2. 节点定义与基础工具函数2.1 Node结构四个字段就够AVL树的每个节点和普通BST相比多了一个“高度”字段。我定义如下struct Node { int key; // 键 int value; // 值 Node* left; // 左孩子 Node* right; // 右孩子 int height; // 当前节点为根的子树高度 Node(int k, int v) : key(k), value(v), left(nullptr), right(nullptr), height(1) {} };height 字段存的是以当前节点为根的子树高度。我采用“空指针高度为0、叶子节点高度为1”的约定这样计算方便而且不会出现负数。每插入一个叶子节点它的初始高度就是1父节点的高度通过左右孩子的最大高度加1得到。2.2 高度和平衡因子必须单独封装写AVL树最容易踩的坑就是到处直接访问 node-height一旦 node 是空指针就直接崩溃。所以我的做法是封装两个非常小的工具函数static int getHeight(Node* node) { return node ? node-height : 0; } static int getBalanceFactor(Node* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; }平衡因子我统一约定为“左子树高度减右子树高度”。也就是说平衡因子为正说明左边偏高为负说明右边偏高。后面旋转判断的方向全部基于这个约定千万别写反。很多人在代码里一会儿左减右、一会儿右减左结果就是旋转方向错乱越调越糟。把这套约定固定下来分支判断就一清二楚了。2.3 更新高度的时机插入或删除一个节点后只有路径上的节点高度可能变化。所以每层递归返回前都要调用一次更新函数static void updateHeight(Node* node) { node-height std::max(getHeight(node-left), getHeight(node-right)) 1; }有一个细节必须提醒旋转操作内部也要更新高度而且顺序有讲究。比如左旋后原来的根节点变成了新根节点的左孩子此时必须先更新“原来的根节点”再更新“新根节点”。因为新根节点的高度依赖左孩子更新后的高度。我在第3节会结合代码再强调一次。3. 四种旋转操作调平衡的核心动作旋转是AVL树的灵魂。四种旋转对应四种失衡形态我建议先背熟场景再看代码。3.1 左旋处理“右右失衡”当某节点的右子树比左子树高出2以上且问题出在右孩子的右侧时用左旋。左旋的效果是把当前节点 p 的右孩子 q 提上来当根p 变成 q 的左孩子q 原来的左子树转挂到 p 的右侧。static Node* rotateLeft(Node* p) { Node* q p-right; // q 是新的根 p-right q-left; // q 的左子树转给 p 的右侧 q-left p; // p 变成 q 的左孩子 updateHeight(p); // 先更新下层节点 updateHeight(q); // 再更新新的根节点 return q; // 返回新的子树根 }为什么 p-right 要先接 q-left因为 q 的左子树里所有节点都比 q 小、但都比 p 大BST顺序决定所以它们恰好应该放在 p 的右子树位置。这一步保证了旋转后仍然是一棵合法的BST。3.2 右旋处理和左旋对称的“左左失衡”右旋就是完全对称的操作把左孩子提上来当前节点变成右孩子左孩子的右子树转挂到当前节点左侧static Node* rotateRight(Node* p) { Node* q p-left; p-left q-right; q-right p; updateHeight(p); updateHeight(q); return q; }这里我想强调一件事很多新手会把左旋和右旋的函数名与失衡情况对不上号。他们的误区是“左边高了就左旋”但实际上左边高了要用右旋。你只要想一个例子根节点是10左孩子是5再往左插入3树变成了一条左斜链。此时需要把5提起来当根10降成5的右孩子这个动作是“顺时针旋转”也就是右旋。记住左高右旋、右高左旋。3.3 复合旋转LR和RL如果失衡方向不是单纯的“左左”或“右右”而是一边子树内部又拐了个弯就必须复合旋转。LR的意思是“左孩子的右子树导致失衡”RL是“右孩子的左子树导致失衡”。LR的处理分两步先对左孩子做左旋让左子树变成“左左形态”再对当前节点做右旋static Node* leftRightRotate(Node* p) { p-left rotateLeft(p-left); // 先将左孩子左旋 return rotateRight(p); // 再对当前节点右旋 } static Node* rightLeftRotate(Node* p) { p-right rotateRight(p-right); // 先将右孩子右旋 return rotateLeft(p); // 再对当前节点左旋 }为什么要先转一次而不是一步到位因为“弯着的”不平衡无法用一次旋转修复。你可以画棵树直观感受根10左孩子55的右孩子7此时7是最后插入的导致左子树比右子树高2。如果直接对根做右旋7会被转到10的左子树依然破坏平衡。必须先对5做左旋把7转成5的左孩子整个左子树变成一条向左的链然后根节点右旋就顺理成章了。3.4 旋转后更新高度的顺序很多人死在这我在前面提到过旋转内部的高度更新顺序必须是先旧根、再新根。拿左旋代码来说p 原来是子树根旋转后 p 变成了 q 的左孩子p 的左右子树结构已经变了它的 height 必须第一个被刷新。然后 q 因为新接收了 p 作为左孩子它的高度依赖 p 的最新高度所以 q 必须第二个刷。如果你先把 q 的高度更新了再更新 p 的算出来的 q 高度就少了一维树的整体高度信息就错了后面的平衡判断会跟着出错。4. 插入操作递归插入与回溯平衡4.1 插入的骨架插入本身和普通BST一模一样比大小、向左或向右递归直到空节点后创建新节点。不同的是每一层递归返回前都要更新高度并检查平衡因子。static Node* insert(Node* node, int key, int value) { if (!node) return new Node(key, value); if (key node-key) { node-left insert(node-left, key, value); } else if (key node-key) { node-right insert(node-right, key, value); } else { node-value value; // key已存在直接更新值 return node; } updateHeight(node); int bf getBalanceFactor(node); // 四种失衡情况对应四种旋转 if (bf 1 key node-left-key) { return rotateRight(node); } if (bf -1 key node-right-key) { return rotateLeft(node); } if (bf 1 key node-left-key) { return leftRightRotate(node); } if (bf -1 key node-right-key) { return rightLeftRotate(node); } return node; }4.2 为什么插入判断用 key 而不是平衡因子插入时判断“是LL还是LR”最直接的办法是看插入的 key 落在左子树的哪个方向如果 key 小于左孩子的 key说明插到了更左边是LL如果大于左孩子的 key说明插到了左孩子的右侧是LR。右子树对称同理。这是插入场景独有的判断法代码简单也不容易出错。4.3 插入完整流程梳理我建议你在脑子里过一遍这个过程插入10、20、30。插入30时20的平衡因子从0变成-110的平衡因子变成-2此时10属于RR失衡直接对10做左旋20变根10变20左孩子。树高从3降到2查找效率保持在log级别。连续插入有序序列是检验AVL树的最好测试这也是我第7节测试脚本里会重点验证的场景。4.4 最容易忽略的返回值必须接住insert 函数返回的是调整后的子树新根。在递归调用处必须写node-left insert(...)或者node-right insert(...)否则旋转产生的新根没人接原节点的指针还指向旧子树平衡调整全部白做。我在接手一些学生的代码时经常看到他们漏掉这一步结果树莫名其妙地丢节点或直接崩。接住返回值是AVL树代码不出暗病的底线。5. 删除操作比插入更需要注意细节5.1 删除的三种形态删除会比插入复杂因为要处理“被删节点有几个孩子”的三种情况没有孩子、只有一个孩子、有两个孩子。没有孩子直接 delete返回 nullptr 给父节点接住。只有一个孩子delete 当前节点返回它的孩子给父节点接住。有两个孩子用后继节点右子树中的最小节点替换当前节点的键值然后递归删除右子树里的这个后继节点。用后继替换的好处是后继节点最多只有一个右孩子删除它的难度降到了前两种情况。5.2 删除双子节点时的键值搬运细节我这个实现里删除双子节点时做了“值搬运”而不是真正删除当前节点指针。具体来说Node* successor minNode(node-right); node-key successor-key; node-value successor-value; node-right erase(node-right, successor-key);注意这里必须先记录好 successor因为 node-key 被覆盖后后面递归 erase 时才能用 successor-key 去定位。同样递归的返回值要重新赋给 node-right。minNode 函数就是从某个节点开始一路向左走到底static Node* minNode(Node* node) { while (node-left) { node node-left; } return node; }5.3 删除后同样需要回溯调整删除比插入更麻烦的一点是删除之后不光是在删除点需要调整往上每一层都有可能触发失衡所以每层递归返回前必须执行和插入一样的更新高度、检查平衡因子流程。但删除时的失衡判断不能再用“key与孩子比较”的方法因为被删的 key 已经不存在于当前路径判断里了。这时要改用子树的平衡因子来判断是哪种旋转。static Node* erase(Node* node, int 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 { // 情况1没有左孩子 if (!node-left) { Node* rightChild node-right; delete node; return rightChild; } // 情况2没有右孩子 if (!node-right) { Node* leftChild node-left; delete node; return leftChild; } // 情况3有两个孩子用后继替换值 Node* successor minNode(node-right); node-key successor-key; node-value successor-value; node-right erase(node-right, successor-key); } updateHeight(node); int bf getBalanceFactor(node); // 删除后用子树平衡因子判断旋转方向 if (bf 1 getBalanceFactor(node-left) 0) { return rotateRight(node); } if (bf 1 getBalanceFactor(node-left) 0) { return leftRightRotate(node); } if (bf -1 getBalanceFactor(node-right) 0) { return rotateLeft(node); } if (bf -1 getBalanceFactor(node-right) 0) { return rightLeftRotate(node); } return node; }5.4 删除时内存管理的一个坑在!node-left分支里我先把右孩子存到 rightChild 里再 delete node最后 return rightChild。顺序不能反。如果你先 delete node再访问 node-right那就是对已释放内存的访问属于未定义行为。另外delete 之后不需要手动把 node 置 nullptr因为局部变量马上就不用了。这里的析构也值得说一句。AVL树是递归结构析构时不能用delete root_了事要递归释放所有节点static void destroy(Node* node) { if (!node) return; destroy(node-left); destroy(node-right); delete node; }递归析构在树特别深时可能栈溢出不过对于平衡树来说深度一般是几十层实际使用中问题不大。6. 查找、遍历与辅助验证方法6.1 查找迭代版更省空间查找不需要修改树所以完全不用递归写个循环就行int* find(int key) { Node* cur root_; while (cur) { if (key cur-key) return cur-value; if (key cur-key) cur cur-left; else cur cur-right; } return nullptr; }返回值用指针的好处是找不到时返回 nullptr调用方可以直接判断找到了还可以通过指针修改对应的 value。如果返回值用 int遇到“值恰好是0”的情况你根本分不清是没找到还是值本身为0。6.2 中序遍历验证有序性一棵AVL树首先必须是合法的BST。最直观的验证方法就是中序遍历理论上输出的 key 序列一定是严格递增的static void inorder(Node* node) { if (!node) return; inorder(node-left); std::cout node-key ; inorder(node-right); }我测试时会把中序遍历结果和插入的有序序列做比对一旦发现顺序错乱说明某次旋转后的链接关系写错了比如把某个子树挂到了错误的一侧。6.3 平衡性校验函数光中序有序还不够还得验证每个节点的平衡因子绝对值不超过1static bool isBalancedNode(Node* node) { if (!node) return true; int bf getBalanceFactor(node); if (bf 1 || bf -1) return false; return isBalancedNode(node-left) isBalancedNode(node-right); } bool isBalanced() const { return isBalancedNode(root_); }这个函数在测试和调试阶段非常有用。我调试旋转逻辑时就反复跑它一旦返回 false就立刻二分定位找到是哪个子树出的问题。7. 完整可运行测试连续插入与随机删除7.1 测试用例设计我只做两个层面的测试第一连续插入1到100的有序数据验证AVL树的平衡性与有序性第二交替删除奇数键验证删除后的重平衡。连续插入有序序列是最狠的测试因为普通BST此时会退化成链表而AVL树经过旋转后高度应该只有约7层log2(100)大概等于7。如果测试输出里树的高度明显超过这个量级说明旋转逻辑有遗漏。7.2 完整代码汇总我把全部代码整合成一个可直接编译的文件方便你直接复制去跑#include iostream #include algorithm class AVLTree { public: AVLTree() : root_(nullptr) {} ~AVLTree() { destroy(root_); } void insert(int key, int value) { root_ insertNode(root_, key, value); } void erase(int key) { root_ eraseNode(root_, key); } int* find(int key) { Node* cur root_; while (cur) { if (key cur-key) return cur-value; if (key cur-key) cur cur-left; else cur cur-right; } return nullptr; } bool contains(int key) { return find(key) ! nullptr; } void inorder() const { inorderNode(root_); std::cout \n; } bool isBalanced() const { return isBalancedNode(root_); } int height() const { return getHeight(root_); } private: struct Node { int key; int value; Node* left; Node* right; int height; Node(int k, int v) : key(k), value(v), left(nullptr), right(nullptr), height(1) {} }; Node* root_; static int getHeight(Node* node) { return node ? node-height : 0; } static int getBalanceFactor(Node* node) { return node ? getHeight(node-left) - getHeight(node-right) : 0; } static void updateHeight(Node* node) { node-height std::max(getHeight(node-left), getHeight(node-right)) 1; } static Node* rotateLeft(Node* p) { Node* q p-right; p-right q-left; q-left p; updateHeight(p); updateHeight(q); return q; } static Node* rotateRight(Node* p) { Node* q p-left; p-left q-right; q-right p; updateHeight(p); updateHeight(q); return q; } static Node* leftRightRotate(Node* p) { p-left rotateLeft(p-left); return rotateRight(p); } static Node* rightLeftRotate(Node* p) { p-right rotateRight(p-right); return rotateLeft(p); } static Node* insertNode(Node* node, int key, int value) { if (!node) return new Node(key, value); if (key node-key) { node-left insertNode(node-left, key, value); } else if (key node-key) { node-right insertNode(node-right, key, value); } else { node-value value; return node; } updateHeight(node); int bf getBalanceFactor(node); if (bf 1 key node-left-key) return rotateRight(node); if (bf -1 key node-right-key) return rotateLeft(node); if (bf 1 key node-left-key) return leftRightRotate(node); if (bf -1 key node-right-key) return rightLeftRotate(node); return node; } static Node* minNode(Node* node) { while (node-left) node node-left; return node; } static Node* eraseNode(Node* node, int key) { if (!node) return nullptr; if (key node-key) { node-left eraseNode(node-left, key); } else if (key node-key) { node-right eraseNode(node-right, key); } else { if (!node-left) { Node* rightChild node-right; delete node; return rightChild; } if (!node-right) { Node* leftChild node-left; delete node; return leftChild; } Node* successor minNode(node-right); node-key successor-key; node-value successor-value; node-right eraseNode(node-right, successor-key); } updateHeight(node); int bf getBalanceFactor(node); if (bf 1 getBalanceFactor(node-left) 0) return rotateRight(node); if (bf 1 getBalanceFactor(node-left) 0) return leftRightRotate(node); if (bf -1 getBalanceFactor(node-right) 0) return rotateLeft(node); if (bf -1 getBalanceFactor(node-right) 0) return rightLeftRotate(node); return node; } static void inorderNode(Node* node) { if (!node) return; inorderNode(node-left); std::cout node-key ; inorderNode(node-right); } static bool isBalancedNode(Node* node) { if (!node) return true; int bf getBalanceFactor(node); if (bf 1 || bf -1) return false; return isBalancedNode(node-left) isBalancedNode(node-right); } static void destroy(Node* node) { if (!node) return; destroy(node-left); destroy(node-right); delete node; } }; int main() { AVLTree tree; for (int i 1; i 100; i) { tree.insert(i, i * 10); } std::cout 有序插入1~100后\n; std::cout 树高: tree.height() \n; std::cout 是否平衡: (tree.isBalanced() ? true : false) \n; std::cout 中序: ; tree.inorder(); AVLTree tree2; for (int i 1; i 50; i) { tree2.insert(i, i); } for (int i 1; i 50; i 2) { tree2.erase(i); } std::cout \n删除1~50中的奇数后\n; std::cout 树高: tree2.height() \n; std::cout 是否平衡: (tree2.isBalanced() ? true : false) \n; std::cout 中序: ; tree2.inorder(); return 0; }7.3 实测效果分析这个程序在我的环境里用 g 编译后直接跑连续插入1~100的树高是7log2(100)约等于6.6加上根节点一层正好是7isBalanced 返回 true中序输出是1到100的严格递增序列。删除奇数的树高度是6依然保持平衡。这说明插入和删除后的旋转调整都生效了树的每一项指标都符合AVL树的定义。如果你自己跑发现中序不乱但高度异常说明旋转后的 height 更新顺序有问题如果中序乱序说明旋转时的指针链接有误。这两个错误在第8节我会展开说。8. 常见问题排查与避坑清单8.1 五个高频错误汇总我从自己踩过的坑和帮别人看的代码里整理了下面这些最高频的问题错误表现根本原因排查思路树高异常偏大旋转后忘记更新高度或更新顺序先新根后旧根检查两个旋转函数里 updateHeight 的位置和顺序旋转后中序乱序指针挂错方向比如左旋时把 q-left 挂错位置打印旋转前中序与旋转后中序对比缺失节点插入时崩溃在 node-left-keynode-left 为空还去访问确认失衡判断分支的顺序先判bf再访问孩子删除后树失衡删除双子节点后没递归删除后继节点检查 erase 第三个分支是否正确调用了 eraseNode(node-right, successor-key)程序运行后内存泄漏析构没有递归释放左右子树用 valgrind 或 ASAN 查泄漏点8.2 调试神器打印每个节点的平衡因子调试旋转逻辑时最有效的办法不是盯着代码看而是写一个调试函数输出每个节点的key和平衡因子static void debugPrint(Node* node, int depth 0) { if (!node) return; debugPrint(node-left, depth 1); std::cout std::string(depth * 2, ) key node-key bf getBalanceFactor(node) h node-height \n; debugPrint(node-right, depth 1); }插入每个节点后都调用一次观察失衡节点的平衡因子是否在旋转后恢复为0或±1。如果发现某次旋转后平衡因子方向反了那一定是旋转方向写错了。我调试时通常会在main里插入6~8个节点逐步观察输出配合画图很快就能定位问题。8.3 面试中的答题技巧如果你是在准备面试建议按这个顺序表达先讲清楚BST的局限有序插入退化再讲AVL的定义平衡因子绝对值≤1然后讲四种失衡形态对应的旋转方法。面试官通常更关心你能不能准确判断“什么情况下用哪种旋转”所以画图比背代码更重要。我建议你在纸上画出LL、RR、LR、RL四种形态各一棵树再把旋转后的结果画出来这样就算现场手写代码也能保证逻辑清晰。9. 进一步优化模板化、性能选型与项目落地方案9.1 把int改成模板要把这个实现变成通用的有序映射只需要把 Node 结构、类定义和四个核心函数里的 int key 改成模板参数 Kvalue 改成 V。比较操作默认用和如果想支持自定义类型再加上一个模板参数 Comparator。唯一要注意的是删除双子节点时用后继替换的逻辑在模板化后依然成立不需要额外改动。9.2 AVL树和红黑树该怎么选标准库里的 std::map 和 std::set 大多基于红黑树实现红黑树是“近似平衡”保证最长路径不超过最短路径的两倍AVL树是“严格平衡”左右子树高度差不超过1。这导致AVL树的查找更快但插入和删除时需要更多旋转。如果你的场景是“写少读多”比如构建一次、查询无数次的配置表、路由表AVL树会稍微占优如果是高频插入删除的缓存系统红黑树更合适。不过现实中我很少在业务代码里自己实现 AVL 树因为 std::map 和 std::unordered_map 已经足够可靠。手写 AVL 树的意义更多在于你只有亲手写过旋转才能真正理解为什么平衡树能把复杂度稳定在O(log n)量级这在面试和阅读开源代码时都很宝贵。9.3 我的个人经验与后续扩展建议这次实现完整跑通之后我最大的感受是AVL树的难点不在旋转代码本身而在于判断“什么时候需要旋转、用哪种旋转”。我建议你拿到代码后不要急着背先在纸上把LL、RR、LR、RL四种场景画一遍标出旋转前的平衡因子和旋转后的平衡因子再回来对照代码效果会好很多。后续如果你想继续扩展可以考虑做三件事一是把这里改成模板类支持任意可比较类型二是加一个operator[]操作让它的用法更像 std::map三是用内存池管理节点避免高频插入删除时频繁调用 new 和 delete 的性能损失。AVL树本身是一块很扎实的基础数据结构弄懂它之后你再看红黑树、B树、跳表这些结构思路会顺畅很多。