C++：解构 AVL 树（平衡核心、旋转策略与高效实现技巧）

前言：

在二叉搜索树（BST）中，若插入顺序有序（如递增或递减），树会退化为链表，导致增删查效率从O(logN)骤降至O(N)。为解决这一问题，AVL 树（自平衡二叉搜索树）应运而生 —— 它通过控制左右子树的高度差（平衡因子），确保树始终保持 “高度平衡”，从而稳定维持O(logN)的高效操作。本文将从 AVL 树的核心概念切入，结合完整代码实现，详解插入逻辑、平衡因子更新与四种旋转操作，帮你彻底掌握这一经典数据结构。

一. AVL 树核心概念：什么是 “高度平衡”？

AVL 树是一种特殊的二叉搜索树，满足两个核心条件：

• 二叉搜索树特性：左子树所有节点值 < 根节点值 < 右子树所有节点值；
• 高度平衡特性：任意节点的左右子树高度差的绝对值 ≤ 1。

为了更直观判断平衡状态，引入了平衡因子（balance factor）：平衡因子 = 右子树高度 - 左子树高度AVL 树中，任意节点的平衡因子只能是-1、0、1；若平衡因子为 2 或 -2，说明树已失衡，需通过 “旋转” 恢复平衡。

思考：为什么不要求平衡因子为 0？
某些场景下（如 2 个节点、4 个节点），树无法做到左右子树高度完全相等（如根节点左子树高 1，右子树高 0），此时平衡因子为 1，仍满足 “高度差≤1” 的平衡要求。

二. AVL 树结构设计：节点与类定义

AVL 树的节点需存储键值对、左右孩子指针、父指针（用于更新平衡因子）和平衡因子。类定义如下：

#pragma once #include<iostream> #include<assert.h> using namespace std; // AVL树节点的结构 template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; // 存储键值对（Key-Value） AVLTreeNode<K, V>* _parent; // 父节点指针（后续更新平衡因子要用到） AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; int _bf; // 平衡因子：右子树高度 - 左子树高度 AVLTreeNode(const pair<K, V>& kv) : _kv(kv) , _parent(nullptr) , _left(nullptr) , _right(nullptr) , _bf(0) {} }; // AVL树类 template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: // 插入、旋转等核心接口（下文会详细解析） bool Insert(const pair<K, V>& kv); void RotateR(Node* parent); // 右单旋 void RotateL(Node* parent); // 左单旋 void RotateLR(Node* parent); // 左右双旋 void RotateRL(Node* parent); // 右左双旋 Node* Find(const K& key); // 查找(和二叉搜索树一样) private: Node* _root = nullptr; };

三. AVL 树插入：从 BST 插入到平衡维护

AVL树的插入流程分为两步：按 BST 规则插入节点→回溯更新平衡因子，失衡则旋转恢复。这是 AVL 树维持平衡的核心环节，需重点理解平衡因子的更新逻辑与停止条件。

3.1 插入完整代码（带详细注释）

public: bool Insert(const pair<K,V>& kv) { // 情况1：树为空，直接创建根节点 if (_root == nullptr) { _root = new Node(kv); return true; } // 情况2：树非空，遍历找插入位置 Node* parent = nullptr;// 记录cur的父节点（用于后续链接新节点） 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;// 值已存在，不支持插入，返回false } // 创建新节点，并链接到parent的左/右孩子 cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur;// 插入值比parent大，作为右孩子 } else { parent->_left = cur; // 插入值比parent小，作为左孩子 } cur->_parent = parent; // 更新平衡因子（从新节点的父节点开始向上） while (parent) { // 更新当前父节点的平衡因子 if (cur == parent->_left) { // 新节点在父节点的左子树 → 左子树高度+1 → 平衡因子-1 parent->_bf--; } else { // 新节点在父节点的右子树 → 右子树高度+1 → 平衡因子+1 parent->_bf++; } // 根据平衡因子判断是否继续更新或旋转 if (parent->_bf == 0) { // parent所在的子树高度不变，不会再影响上一层，更新结束 // 平衡因子变为0 → 父节点子树高度不变（插入前左 / 右高1，插入后平衡） break; } else if (parent->_bf == 1 || parent->_bf == -1) { // parent 所在的子树高度变了，会再影响上一层，继续往上面更新 // 平衡因子变为1 / -1 → 父节点子树高度 + 1（插入前平衡，插入后单侧高1） cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { // parent 所在的子树已经不平衡了，需要旋转处理 // 平衡因子变为2 / -1 → 父节点子树失衡，需旋转恢复平衡 if (parent->_bf == -2 && cur->_bf == -1) { // 父节点BF=-2（左子树高），当前节点BF=-1（左子树高）→ 右单旋 RotateR(parent); } else if (parent->_bf == 2 && cur->_bf == 1) { // 父节点BF=2（右子树高），当前节点BF=1（右子树高）→ 左单旋 RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { // 父节点BF=-2（左子树高），当前节点BF=1（右子树高）→ 左右双旋 RotateLR(parent); } else { // 父节点BF=2（右子树高），当前节点BF=-1（左子树高）→ 右左双旋 RotateRL(parent); } // 旋转后，失衡子树高度恢复到插入前，不会影响上层，更新结束 break; } else { // 异常情况：平衡因子为其他值（如3、-3) assert(false); } } return true; }

3.2 平衡因子更新关键逻辑

更新平衡因子时，核心是判断“当前子树高度是否变化”，进而决定是否继续向上更新：

• BF=0：插入前父节点子树 “有一侧高 1”（如 BF=1 或 - 1），插入后两侧平衡，高度不变 → 停止更新；
• BF=1/-1：插入前父节点子树 “平衡”（BF=0），插入后 “有一侧高 1”，高度 + 1 → 继续更新；
• BF=2/-2：插入前父节点子树 “有一侧高 1”，插入后 “有一侧高 2”，失衡 → 旋转后停止更新。
• 更新到根，根的平衡因子是1或-1也停止。

我们来看看下面几个情况图示：

更新到 10 结点，平衡因子为2，10所在的子树已经不平衡，需要旋转处理

更新到中间结点，3为根的子树高度不变，不会影响上一层，更新结束。

最坏情况：更新到根为止

四. AVL 树旋转：失衡恢复的四种方式

当节点平衡因子为2或- 2时，需通过 “旋转” 恢复平衡。旋转的核心目标有两个：维持二叉搜索树特性 + 降低失衡子树高度。根据失衡形态，分为四种旋转方式：

4.1 右单旋（RotateR）：左子树过高（父 BF=-2，子 BF=-1）

• 下图中展现的是10为根的树，有a/b/c抽象为三颗高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整颗树的根。这里a/b/c是高度为h的子树，是一种概括抽象的表示，他代表了所有右单旋的场景，但实际右单旋的场景很多，大家可以看看后面的实际场景图。

• 在 a 子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树的左边太高了，需要往右边旋转，控制两颗树的平衡。

旋转核心步骤：

1. 记录父节点（parent）的左子树（subL）和 subL 的右子树（subLR）；
2. 将 subLR 作为 parent 的左子树（若 subLR 非空，更新其 parent 指针）；
3. 将 parent 作为 subL 的右子树，更新 parent 的 parent 指针(提前存一下祖父结点，再更新)；
4. 链接 subL 与祖父节点（若 parent 是根节点，更新_root）；
5. 重置 parent 和 subL 的平衡因子为 0。

实际场景图：

代码实现（注意看注释）：

public: void RotateR(Node* parent) { Node* subL = parent->_left; // parent的左子树（即将成为新根） Node* subLR = subL->_right; // subL的右子树（需转移给parent） // 步骤1：将subLR作为parent的左子树 parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* grandparent = parent->_parent; // parent的父节点（祖父节点） // 步骤2：将parent作为subL的右子树 subL->_right = parent; parent->_parent = subL; // 步骤3：链接subL与祖父节点（或更新根节点） if (parent == _root) { // parent是根节点，则subL成为新根 _root = subL; subL->_parent = nullptr; } else { // parent是祖父节点的左/右孩子，对应链接subL if (grandparent->_left == parent) grandparent->_left = subL; else grandparent->_right = subL; subL->_parent = grandparent; } // 步骤4：重置平衡因子（旋转后子树平衡，BF均为0） parent->_bf = subL->_bf = 0; }

4.2 左单旋（RotateL）：右子树过高（父 BF=2，子 BF=1）

• 下图中展示的是10为根的树，有a/b/c抽象为三颗高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整颗树的根，也可能是一整颗树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表所有左单旋的场景，实际左单旋场景有很多，具体跟上面的右旋类似。

• 在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了。需要往左边旋转，控制两颗树的平衡。

旋转核心步骤：

• 记录父节点（parent）的右子树（subR）和 subR 的左子树（subRL）；
• 将 subRL 作为 parent 的右子树（若 subRL 非空，更新其 parent 指针）；
• 将 parent 作为 subR 的左子树，更新 parent 的 parent 指针(提前存一下祖父结点，再更新)；
• 链接 subR 与祖父节点（或更新_root）；
• 重置 parent 和 subR 的平衡因子为 0。

代码实现（注意看注释）：

public: void RotateL(Node* parent) { Node* subR = parent->_right; // parent的右子树（即将成为新根） Node* subRL = subR->_left; // subR的左子树（需转移给parent） // 步骤1：将subRL作为parent的右子树 parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* grandparent = parent->_parent; // parent的父节点 // 步骤2：将parent作为subR的左子树 subR->_left = parent; parent->_parent = subR; // 步骤3：链接subR与祖父节点（或更新根节点） if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (grandparent->_left == parent) grandparent->_left = subR; else grandparent->_right = subR; subR->_parent = grandparent; } // 步骤4：重置平衡因子 parent->_bf = subR->_bf = 0; }

4.3 左右双旋（RotateLR）：左子树的右子树过高（父 BF=-2，子 BF=1）

• 我们通过下面这两种场景图，可以看出，左边高时，如果插入位置不是在a子树，而是插入到b子树，b子树高度从h变成h+1,引发了旋转，右单旋无法解决问题，右单旋过后，我们的树依旧不平衡。右单旋解决的纯粹的左边高，但是插入到b子树中，10为根的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，需要用两次旋转才能解决，以5为旋转点进行一个左单旋，以10为旋转点进行一个右单旋，这颗树就平衡了。

• 上面两个图片分别为左右双旋中 h==0 和 h==1的具体场景分析，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树，因为我们要对b的父亲5为旋转点进行左单旋，左单旋需要动b树中的左子树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察8的平衡因子不同，这里我们要分三个场景讨论。

旋转核心步骤：

• 对父节点的左子树（subL）执行左单旋（将 subL 的右子树 subLR 提升为 subL 的父节点）；
• 对父节点（parent）执行右单旋（将修正后的 subL 提升为 parent 的父节点）；
• 根据 subLR 的原始平衡因子，重置三个节点（parent、subL、subLR）的平衡因子，三种场景。

• 场景1：h>=1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新subLR->subL->parent平衡因子，引发旋转，其中subLR的平衡因子为 -1，旋转后subLR和subL平衡因子为0，parent的平衡因子为1。
• 场景2：h>=1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新subLR->subL->parent平衡因子，引发旋转，其中subLR的平衡因子为1，旋转后subLR和parent的平衡因子为0，subL的平衡因子为-1。
• 场景3：h==0时，a/b/c都是空树，b自己就是一个新增结点，不断更新subL->parent平衡因子，引发旋转，其中subLR的平衡因子为0，旋转后subLR,subL和parent的平衡因子都为0。

代码实现（注意看注释）：

void RotateLR(Node* parent) { Node* subL = parent->_left; // parent的左子树 Node* subLR = subL->_right; // subL的右子树（关键节点，决定平衡因子重置） int bf = subLR->_bf; // 记录subLR的原始BF（用于后续重置） // 步骤1：先对subL执行左单旋（修正左子树的失衡） RotateL(parent->_left); // 步骤2：再对parent执行右单旋（修正父节点的失衡） RotateR(parent); // 步骤3：根据subLR的原始BF，重置三个节点的平衡因子 if (bf == 0) { // 场景3：subLR是新插入节点（BF=0）→ 旋转后三者BF均为0 parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) { // 场景2：subLR的右子树高（BF=1）→ parent的左子树高，subL的右子树高 parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if(bf==-1) { // 场景1：subLR的左子树高（BF=-1）→ parent的右子树高，subL的左子树高 parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } }

4.4 右左双旋（RotateRL）：右子树的左子树过高（父 BF=2，子 BF=-1）

• 跟左右双旋类似，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树，因为我们要对b的父亲15为旋转点进行右单旋，右单旋需要动b树中的右子树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察12的平衡因子不同不同，这里我们要分三个场景讨论。

旋转核心步骤：

• 对父节点的右子树（subR）执行右单旋；
• 对父节点（parent）执行左单旋；
• 根据 subRL 的原始平衡因子，重置三个节点的平衡因子。

• 场景1：h>=1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新subRL->subR->parent平衡因子，引发旋转，其中subRL的平衡因子为-1，旋转后parent和subRL平衡因子为0，subR平衡因子为1。
• 场景2：h>=1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新subRL->subR->parent平衡因子,引发旋转，其中subRL的平衡因子为1，旋转后subR和subRL的平衡因子为0，parent的平衡因子为-1。
• 场景3：h==0时，a/b/c都是空树，b自己就是一个新增结点，不断更新**subR->parent** 平衡因子，引发旋转，其中subRL的平衡因子为0，旋转后三者的平衡因子都是0。

代码实现（注意看注释）：

void RotateRL(Node* parent) { Node* subR = parent->_right; // parent的右子树 Node* subRL = subR->_left; // subR的左子树（关键节点） int bf = subRL->_bf; // 记录subRL的原始BF // 步骤1：先对subR执行右单旋（修正右子树的失衡） RotateR(parent->_right); // 步骤2：再对parent执行左单旋（修正父节点的失衡） RotateL(parent); // 步骤3：根据subRL的原始BF，重置三个节点的平衡因子 if (bf == 0) { // 场景3：subRL是新插入节点 → 三者BF均为0 subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else if (bf == 1) { // 场景2：subRL的右子树高（BF=1）→ parent的左子树高，subR的左子树高 subR->_bf = 0; subRL->_bf = 0; parent->_bf = -1; } else if (bf == -1) { // 场景1：subRL的左子树高（BF=-1）→ parent的右子树高，subR的右子树高 subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else { // 异常情况 assert(false); } }

五. AVL树的查找和平衡检查：验证树的正确性

5.1 AVL树的查找：(与二叉搜索树一致,O(logN))

Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return nullptr; }

5.2 AVL 树验证：如何判断实现正确？

为确保 AVL 树实现无误，需验证两个核心条件：二叉搜索树特性 + 高度平衡特性。可添加以下辅助接口（类内补充）：

public: // 对外接口：验证AVL树 bool IsBalanceTree() { return _IsBalance(_root); } // 对外接口：中序遍历（验证二叉搜索树特性：中序递增） void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); }

测试代码示例：

#define _CRT_SECURE_NO_WARNINGS 1 #include"AVLTree.h" // 测试AVL树插入与平衡性 void TestAVL() { // 测试用例1：包含双旋场景（如4,2,6,1,3,5,15,7,16,14） int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; AVLTree<int, int> t; for (auto e : a) { t.Insert({ e, e }); } // 验证1：中序遍历（应递增） cout << "中序遍历结果："; t.InOrder(); // 输出：1 2 3 4 5 6 7 14 15 16 // 验证2：平衡性（应返回true） if (t.IsBalanceTree()) { cout << "AVL树平衡验证通过！" << endl; } else { cout << "AVL树平衡验证失败！" << endl; } } int main() { TestAVL(); return 0; }