C++ 实现 AVL 树:原理、旋转与代码实战
AVL 树是最早发明的自平衡二叉查找树。它是一棵空树,或者满足以下性质的二叉搜索树:左右子树都是 AVL 树,且左右子树的高度差的绝对值不超过 1。

AVL 树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis,他们在 1962 年的论文中发表了这一结构。为了实现高度平衡,我们引入**平衡因子(Balance Factor)**的概念。每个节点都有一个平衡因子,等于右子树高度减去左子树高度。在 AVL 树中,任何节点的平衡因子只能是 -1、0 或 1。
虽然理论上不强制存储平衡因子也能实现,但有了它我们可以更直观地观察和控制树的平衡状态,类似于一个风向标。最终目的依然是控制高度差。
初识 AVL 树
AVL 树要求高度差不超过 1,为什么不是 0?因为有些情况下无法做到高度差为 0。例如只有 2 个或 4 个节点时,高度差最好就是 1,强行追求 0 会导致结构过于复杂甚至无法构建。AVL 树整体结点数量和分布与完全二叉树类似,高度控制在 logN,因此增删查改的效率稳定在 O(logN),相比普通二叉搜索树有了本质提升。

AVL 树要点解析
平衡因子逻辑
平衡因子的计算公式很简单:
平衡因子 = 右子树高度 - 左子树高度
只有当子树高度发生变化时,才会影响当前节点的平衡因子。插入新节点会增加高度,如果新增节点在父节点的右子树,父节点的平衡因子加 1;反之减 1。父节点所在子树的高度是否变化,决定了是否需要继续向上更新。
插入过程
插入一个值的过程遵循以下步骤:
- 按规则插入:首先按照二叉搜索树的规则找到位置并插入新节点。
- 更新平衡因子:新增节点只会影响其祖先节点的高度。我们需要从新增节点向上遍历到根节点,更新路径上所有节点的平衡因子。最坏情况需要更新到根,有时更新到中间某层即可停止。
- 判断平衡:如果在更新过程中发现某个节点的平衡因子变为 2 或 -2,说明该子树失衡,需要进行旋转操作。
- 旋转恢复:旋转后子树高度降低,不再影响上一层,插入结束。
更新原则与停止条件
- 更新原则:插入导致高度增加,平衡因子相应增减。
- 停止条件:
- 若更新后平衡因子变为 0,说明该子树一边高一边低,插入后变平,高度未变,不影响父节点,停止更新。
- 若更新后平衡因子变为 1 或 -1(原为 0),说明该子树由平变斜,高度增加 1,需继续向上传播。
- 若更新后平衡因子变为 2 或 -2,说明失衡,需立即旋转处理。

示例演示
以插入 10 为例,若平衡因子变为 2,说明左侧过高,需要旋转。如果更新到中间节点使平衡因子归零,则无需再向上更新。最坏情况下需一直更新到根节点。







