手撕AVL树：平衡因子与旋转的C++完整实现

面试官在白板上写下“手撕AVL树”几个字的时候会议室里安静了几秒。二叉搜索树的插入删除写起来顺手但一旦加上“左右子树高度差不超过1”这个约束旋转、双旋、平衡因子更新这些环节就会让人手心冒汗。我在准备C岗位面试、带新人做基础组件的时候都发现AVL树的模拟实现虽然被归为“数据结构基础”但它几乎覆盖了C里最容易被忽视的细节指针的所有权、父指针的回溯、边界条件的判断、递归深度的控制。这篇博文我就把从节点设计到插入、旋转、验证的完整过程走一遍顺手把删除操作的思路和面试会追问的点也理清楚。适合正在学数据结构、准备C八股突击的读者也适合想自己写一棵自平衡查找树的人。1. 二叉搜索树的退化困境平衡因子是怎么来的1.1 一组升序数据就能让BST变成单链表二叉搜索树的查找效率高度依赖树形。最理想的情况下每次比较都能排除一半的子树查找复杂度是O(log N)。但麻烦在于如果插入的数据恰好有序比如依次插入1、2、3、4、5每个新节点都会挂在已有最右节点的右孩子上整棵树退化成一条只有右指针的单链表。这种情况下查找5需要从头一路遍历到叶子复杂度退化成O(N)。工程里数据顺序常常不可控我们不能赌输入有序还是无序。AVL树就是在这个背景下提出的它强制每棵子树的左右高度差不超过1从数学上保证任何插入顺序下树高都维持在O(log N)级别。这里要补充一句AVL树并不是第一个自平衡二叉树方案但它比红黑树出现得更早而且它的平衡条件最直观作为学习数据结构和面试基础是最合适的切入点。理解了AVL再看红黑树会轻松很多。1.2 用“高度差”定义平衡而不是“节点数差”AVL树对平衡的定义是任意节点的左子树和右子树高度差绝对值不超过1。这里的高度指的是从当前节点到叶子节点的最长路径上的边数空树高度为0单个节点高度为1。我们用一个整型变量记录这个差值叫平衡因子balance factor简称bf。我习惯定义成bf 右子树高度 - 左子树高度所以平衡因子只可能取-1、0、1三种值。插入或删除后如果某个节点的平衡因子变成2或者-2说明它已经失衡必须通过旋转来修复。有人会问为什么不记录“左子树节点数减右子树节点数”因为AVL树要保证的是查找路径长度而路径长度由高度决定。节点数差哪怕很大只要树够扁平查找路径也可以很短。举例来说一棵高度为10的满二叉树可以承载1023个节点而一棵高度为100的退化树即使只有101个节点查找最坏也要走100步。所以高度才是决定查找效率的关键指标平衡因子定义为高度差是从问题本质出发的选择。1.3 失衡的四种形态与旋转方向的对应插入新节点后从插入位置向上回溯第一个失衡的节点记为parent它的孩子记为sub通过parent和sub的平衡因子符号可以判断失衡属于哪种形态失衡场景parent的bfsub的bf处理方法左左失衡-2-1右单旋右右失衡21左单旋左右失衡-21先左旋再右旋右左失衡2-1先右旋再左旋这里“左左”指的是新节点插入在较高左子树的左侧“左右”指的是插入在较高左子树的右侧。记住这个映射关系后插入代码的判断部分就是一组if-else面试时不需要临场推导。2. AVL树的节点结构与基础框架2.1 为什么节点要设计成三叉链结构普通二叉树的节点只有_left和_right两个指针遍历时可以通过递归或栈来回溯。但AVL树插入节点后需要从插入点一路向上更新每个祖先的平衡因子直到遇到失衡节点做旋转。如果节点没有_parent指针就必须在递归回溯时把路径上的节点堆到栈里或者重新从根节点往下搜这两种方式都很笨拙。所以我实现AVL树时使用三叉链每个节点除了左右孩子还保存父节点指针。这样插入完成后只需要沿着_parent链往上走就能逐层更新balance factor时间复杂度是O(log N)。这个设计和双链表优于单链表的道理一样多一个反向指针换来的是反向遍历从O(N)降到O(1)的访问速度。代价是每次修改指针关系时要多维护一个_parent的指向这也是很多初学实现容易漏掉的地方。2.2 节点结构体与pair键值对节点同时存储键和值所以模板参数我习惯设计成K、V两个类型内部用std::pairK, V保存数据这样既支持map语义也可以只关注K来实现set。完整结构体定义如下templateclass K, class V struct AVLNode { pairK, V _kv; AVLNodeK, V* _left; AVLNodeK, V* _right; AVLNodeK, V* _parent; int _bf; AVLNode(const pairK, V kv) : _kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} };平衡因子用int而不是short或char主要是因为后续代码里bf会参与加减运算int在绝大多数平台上运算效率最高也避免类型提升带来的warning。每个节点多几个字节的内存开销在学习和面试场景完全不是问题。2.3 AVL树类骨架与内存管理类的对外接口只需要够用即可构造、析构、插入、中序遍历、平衡校验。拷贝构造和赋值重载属于工程中必须补上的部分面试时能主动写出来是加分项。templateclass K, class V class AVLTree { typedef AVLNodeK, V Node; public: AVLTree() : _root(nullptr) {} ~AVLTree() { Destroy(_root); } AVLTree(const AVLTreeK, V t) : _root(nullptr) { _root Copy(t._root); } AVLTreeK, V operator(AVLTreeK, V t) { swap(_root, t._root); return *this; } bool Insert(const pairK, V kv); void InOrder(); bool IsBalance(); int Height(); private: void RotateL(Node* parent); void RotateR(Node* parent); void RotateLR(Node* parent); void RotateRL(Node* parent); Node* Copy(Node* root); void Destroy(Node* root); int _Height(Node* root); bool _IsBalance(Node* root); void _InOrder(Node* root); private: Node* _root; };析构用后序遍历递归释放拷贝构造用递归复制并维护_parent指针。这两个辅助函数简单但容易写错注意Copy函数内部创建好新节点后要立刻检查左右孩子是否为空不为空则设置它们的_parent指向当前新节点。工程上用VSCode配合g编译测试就够了把AVLTree.h、Test.cpp分开组织比在一个文件里写到底清晰得多。3. 四种旋转的C实现与细节排雷3.1 右单旋当左侧子树过高时新节点插入在某个节点的左子树的左侧导致parent的bf变成-2。此时需要以parent为轴做一次右旋转把subL提升为子树的根。右单旋的代码void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* pparent parent-_parent; subL-_right parent; parent-_parent subL; if (pparent nullptr) { _root subL; subL-_parent nullptr; } else { if (pparent-_left parent) pparent-_left subL; else pparent-_right subL; subL-_parent pparent; } parent-_bf 0; subL-_bf 0; }这里有三个非常容易踩的坑。第一个是subLR为空的情况parent-_left subLR前必须判断空指针否则访问空指针的_parent会崩溃。第二个是pparent可能为空也就是parent原本是根节点旋转后subL要直接成为新的根并且把_parent置空。第三个是旋转完成后必须把parent和subL的平衡因子都置0因为旋转后左右子树高度变成相等了。我还见过一种写法先判断pparent再设置parent的父节点顺序搞反后导致subL的_parent被覆盖半天查不出来。建议顺序固定为先处理parent的孩子指针再处理parent的父指针最后处理pparent的孩子指针。3.2 左单旋右侧子树过高的对称场景左单旋和右单旋完全对称代码如下void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* pparent parent-_parent; subR-_left parent; parent-_parent subR; if (pparent nullptr) { _root subR; subR-_parent nullptr; } else { if (pparent-_left parent) pparent-_left subR; else pparent-_right subR; subR-_parent pparent; } parent-_bf 0; subR-_bf 0; }单旋的代码写熟之后双旋的物理操作就变成组合拳了。但双旋的平衡因子更新并不只是调用两次单旋那么简单下一节专门讲。3.3 左右双旋子树的中间节点翻身当根如果新节点插在较高左子树的右侧也就是parent的bf为-2、subL的bf为1时直接右单旋无法恢复平衡。原因很直观右单旋要求整个失衡路径都偏向左而当前路径是“先左后右”直接右旋会把subLR推到左边旋转后subL仍然可能出现bf-2的失衡。正确做法是两次旋转先对subL做左单旋把子树形态转成纯粹的“左左”再对parent做右单旋。旋转的顺序千万不要写反。void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf; RotateL(subL); RotateR(parent); if (bf 1) { parent-_bf 0; subL-_bf -1; subLR-_bf 0; } else if (bf -1) { parent-_bf 1; subL-_bf 0; subLR-_bf 0; } else { parent-_bf 0; subL-_bf 0; subLR-_bf 0; } }关键就在最后这段为什么不能无条件把三个节点的bf都置0因为subLR原来的平衡因子不同说明新节点插入在subLR的左子树还是右子树旋转后各节点的高度变化不同。我画图推过很多次结论是这样记的如果bf 1说明新节点在subLR的右子树旋转后它跑到parent的右子树里所以parent的bf为0subL的bf为-1如果bf -1新节点在subLR的左子树旋转后它留在subL的左子树所以parent的bf为1subL的bf为0。这个细节面试官经常追问答不上来会显得只是背代码没有真懂旋转后的高度变化。3.4 右左双旋与平衡因子的三种更新分支右左双旋先对subR做右单旋再对parent做左单旋代码和左右双旋对称void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; RotateR(subR); RotateL(parent); if (bf 1) { parent-_bf -1; subR-_bf 0; subRL-_bf 0; } else if (bf -1) { parent-_bf 0; subR-_bf 1; subRL-_bf 0; } else { parent-_bf 0; subR-_bf 0; subRL-_bf 0; } }我建议双旋的三种情况不要死背而是自己画三个小图左插、右插、subRL本身就是新增节点。每一种都推导一遍最后谁变1谁变-1写几遍自然就记住了。这个环节能帮你真正理解旋转的本质而不只是抄代码。4. 插入的完整流程搜索、挂接、更新、旋转4.1 先按二叉搜索树规则插入新节点插入的第一步和普通BST一致从根节点开始比较键值小则往左大则往右遇到相等直接返回false表示插入失败。找到空位后new出新节点根据和父节点的大小关系挂在左侧或右侧同时设置新节点的_parent。bool Insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) parent-_right cur; else parent-_left cur; cur-_parent parent; // 后面继续更新平衡因子 }4.2 平衡因子向上更新的终止条件新节点插入后它的父节点平衡因子一定会变如果插入在父节点右侧父节点bf加1如果插入在左侧父节点bf减1。之后需要沿着_parent链向上检查分三种情况处理父节点bf变为0说明插入前是1或-1插入后矮的那一侧被补齐了整棵子树高度没有变化所有祖先的高度也不变直接break。父节点bf变为1或-1说明插入前是0现在子树高度增加了会影响祖先节点所以继续往上更新。父节点bf变为2或-2说明失衡需要旋转修复。旋转完成后子树高度恢复整棵祖先链上的bf都不再受影响break。前两种容易混淆我提供一个记忆方法bf变成0代表“补平了”高度没变所以可以停bf变成±1代表“长高了”必须继续往上通知祖先。代码实现while (parent) { if (cur parent-_right) parent-_bf; else parent-_bf--; if (parent-_bf 0) { break; } else if (parent-_bf 1 || parent-_bf -1) { cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2) { if (parent-_bf 2 parent-_right-_bf 1) RotateL(parent); else if (parent-_bf -2 parent-_left-_bf -1) RotateR(parent); else if (parent-_bf 2 parent-_right-_bf -1) RotateRL(parent); else if (parent-_bf -2 parent-_left-_bf 1) RotateLR(parent); break; } else { assert(false); } }这个分支判断是整个插入流程的核心。我在调试时见过balance factor跑到3的情况基本都是上面某一步漏了break导致重复更新。另外判断旋转类型时除了看parent的bf还要看孩子节点的bf这个条件不能省略。4.3 旋转后的收尾工作最容易被忽略的三件事旋转函数内部有三件事漏任何一件整棵树的_parent链都会乱掉。第一旋转中涉及的孩子节点如果非空必须更新它的_parent指向新父节点。比如右单旋里parent-_left subLR之后紧接着就要判断subLR不为空并设置subLR-_parent parent。第二parent原来的父节点pparent必须正确接住旋转后的新根。判断pparent为空说明parent原本是根需要把_root更新为subL或subR同时把新根的_parent置空否则需要判断parent是pparent的左孩子还是右孩子把对应指针指向新根。第三旋转共享子树的_parent。左单旋里subRL被放到了parent的右侧右单旋里subLR被放到了parent的左侧这些指针关系都要在旋转函数里完整维护。有一个细节值得单独提旋转后参与旋转的两个单旋中心节点bf都置0但双旋的bf更新不能用单旋后的结论直接套因为双旋中subLR或subRL作为“转折点”同时关联三个节点的高度变化。这也是我前文反复强调双旋平衡因子要分情况推导的原因。4.4 一个具体的插入序列演示用10、20、30、40、50依次插入来观察旋转触发。插入10和20时没有失衡。插入30后节点20的bf变成2且右孩子30的bf是1触发左单旋20被顶上来10变成20的左孩子。插入40后没有失衡。插入50后节点40的bf变成2触发左单旋40被顶上来30变成40的左孩子同时更新根节点。这个过程可以用调试器逐步看也可以在树类里临时写一个打印bf的函数。对初学者来说建议打印出每个节点的key和bf插入一次检查一次比单纯看内存快得多。5. 验证一棵AVL树中序、高度、平衡因子一致性5.1 中序遍历有序性的第一道关卡AVL树本身是二叉搜索树所以中序遍历结果必须严格升序。如果中序结果有序说明搜索树的基本结构没被旋转破坏如果乱序说明旋转时左右指针接错了。中序遍历代码很简单void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_kv.first ; _InOrder(root-_right); } void InOrder() { _InOrder(_root); cout endl; }这里有个常见的误区中序有序只能证明这是一棵合法的BST不能证明它是AVL树。因为即使树已经严重失衡只要左右指针关系正确中序依然有序。所以还必须做高度平衡校验。5.2 高度校验与平衡因子一致性检查验证AVL树是否真正平衡最直接的办法是递归计算每个节点的左右子树高度判断高度差绝对值是否小于2同时还要检查节点存储的bf是否等于右子树高度减左子树高度。第二个检查很关键因为如果旋转后忘记更新bf树可能实际上是平衡的但存储的bf还是错的后续插入会把错误的bf当成依据导致旋转判断混乱。int _Height(Node* root) { if (root nullptr) return 0; return max(_Height(root-_left), _Height(root-_right)) 1; } bool _IsBalance(Node* root) { if (root nullptr) return true; int leftH _Height(root-_left); int rightH _Height(root-_right); if (rightH - leftH ! root-_bf) { cout key: root-_kv.first bf: root-_bf 实际高度差: rightH - leftH endl; return false; } return abs(rightH - leftH) 2 _IsBalance(root-_left) _IsBalance(root-_right); } bool IsBalance() { return _IsBalance(_root); }这套校验的递归开销是O(N log N)级别因为每个节点都要计算一次整棵子树的高度。测试阶段够用工程上如果要频繁校验可以改成自底向上的后序遍历一次性返回高度避免重复计算遍历。但面试或学习阶段正确性优先不需要优化这一点。5.3 随机数据压测和有序序列测试我在自己实现时会写一段测试代码分别跑随机序列和有序序列vectorint keys; for (int i 0; i 100000; i) keys.push_back(rand()); AVLTreeint, int tree; for (int k : keys) tree.Insert(make_pair(k, k)); cout tree.IsBalance() endl; cout tree.Height() endl;一共要测三种数据完全随机、升序、降序。随机数据能覆盖大部分旋转分支升序和降序则强力触发左单旋和右单旋。实测一棵规模为10万的随机AVL树高度应该在23左右因为log2(100000)≈16.6AVL树允许一定高度余量但如果高度超过30几乎可以断定平衡逻辑有问题。100万数据也能跑插入速度非常快树高在30左右。压测常见的异常现象有这么几类程序崩溃多半是_parent指针悬空或空指针访问assert触发多半是bf更新越界IsBalance打印bf不一致多半是旋转函数没有正确更新三个节点的平衡因子。前两类问题用gdb看栈定很快第三类问题就把上面IsBalance里打印出来的key对应到插入序列定位是哪一次插入导致bf错了。6. 删除操作的思路与AVL树的面试进阶6.1 删除后平衡因子的更新方向为什么和插入相反删除节点后受影响的路径上子树高度可能降低平衡因子更新方向恰好和插入相反如果删除发生在右子树parent的bf减1如果删除发生在左子树parent的bf加1。终止条件也和插入不同。插入时bf变为0就可以停因为高度上没有增加删除时bf变为1或-1可以停因为删除前该节点高度是0删除后变成±1说明左右子树高度差仍然在允许范围内且整棵子树高度没变祖先不受影响。换句话说插入是“变0停”删除是“变±1停”。这个方向容易搞混面试时最好能当场画一棵树推出来不要只靠记忆。6.2 删除失衡时为什么需要继续向上检查删除后的旋转修复和插入有一个重要区别插入时旋转完成后局部子树高度恢复原状整棵祖先链直接break但删除时某次旋转虽然让当前局部恢复平衡子树高度却可能比删除前还矮了一层这会继续影响更上层的祖先。所以删除的代码结构通常是更新bf后如果遇到2或-2执行一次旋转旋转后不能立刻break而是要继续向上移动两个指针再检查。极端情况下删除操作可能触发沿路径多次旋转这也是AVL删除比插入难写的原因。工程实现上删除的完整代码量接近插入的两倍。我的建议是先把插入和四种旋转吃透删除的基本思路理解了就足够应对大多数面试。如果要写完整删除记得用后继节点替换被删节点再在后继的原位置向上更新平衡因子。6.3 面试高频对比AVL树与红黑树C标准库里map和set的底层用的是红黑树而不是AVL树。面试官常问为什么答案集中在三点第一红黑树的平衡条件更宽松它不要求左右子树高度差不超过1只要求从根到叶子的最长路径不超过最短路径的2倍。所以红黑树的插入删除旋转频率更低。AVL树删除时可能一路旋转到根红黑树通常旋转次数少得多。第二红黑树每个节点只需要一个颜色位而AVL树需要保存平衡因子。在缓存敏感的现代CPU上内存占用小意味着缓存命中率高红黑树的工程性能更好。第三对于读多写少的场景AVL树由于更严格平衡查找效率略高但对于写多读少的场景红黑树的插入删除代价更小。STL容器面向通用场景选红黑树是综合权衡的结果。我自己在实际手写AVL树时最大的体会是双旋的平衡因子更新是最容易出错的地方千万不要只背结论一定要画图推导三种情形。另一个经验是写代码前先准备好测试用例可以先跑随机数据再专门跑升序降序因为有序数据天然触发单旋能快速验证旋转变换有没有破坏BST性质。面试写代码时时间紧建议先把单旋写好并用注释标明旋转后的bf双旋直接复用两个单旋然后用分支条件更新三个关键节点的bf这样结构最清晰也最容易让面试官看懂思路。如果把AVL树当成一颗纯粹的“背诵题”来学代码写完很快就忘但如果把平衡因子和旋转推导当成一串可以推理的约束条件它会成为你理解很多自平衡结构的起点红黑树、B树、跳表在它面前都会显得亲切许多。