【C++】深入解析AVL树：平衡搜索树的核心概念与实现

【C++】深入解析AVL树：平衡搜索树的核心概念与实现

• 摘要
• 目录
  • 一、AVL树的概念
  • 二、AVL树的模拟实现
    • 1. 节点结构体和树的类模板
    • 2. 平衡因子的概念和实现
    • 3. 插入
    • 4. 旋转操作
      • 4.1 右单旋
      • 4.2 左单旋
      • 4.3 左右双旋
      • 4.4 右左双旋
  • 三、AVL树的平衡检测
• 总结

摘要

本文深入解析了AVL树的核心概念与实现，包括节点结构设计、平衡因子定义及其更新机制、插入操作的自下而上平衡调整策略，以及四种旋转方式（左单旋、右单旋、左右双旋、右左双旋）对保持树平衡的重要作用。同时，提供了AVL树高度计算与平衡检测的实现方法，确保每个节点的平衡因子正确维护，从而保证树在插入操作后的高效性与稳定性。通过本文内容，读者可以系统掌握AVL树的原理、实现与调试技巧，为高性能二叉搜索树的应用打下坚实基础。

目录

一、AVL树的概念

1. AVL树，最早由前苏联科学家 G. M. Adelson-Velsky 和 E. M. Landis 在1962年提出，是一种自平衡的二叉搜索树。AVL树的定义如下：

它是一个空树，或者满足以下性质的二叉搜索树：每个节点的左右子树都是AVL树。每个节点的左右子树高度差（平衡因子）绝对值不超过1。

2. 每个节点都有一个平衡因子（Balance Factor，简称BF），它是该节点右子树高度与左子树高度的差值。具体来说：

BF = height(right_subtree) - height(left_subtree)平衡因子只能为**-1**、0或1，这意味着节点的左右子树的高度差不能超过1。

虽然AVL树的平衡因子并非必需，但它为我们提供了一种方便的方式来判断树是否平衡，就像一个“风向标”，帮助我们轻松判断是否需要进行旋转操作来恢复平衡。

3. 我们可能会好奇：为什么AVL树的高度差要求不超过1，而不是严格要求为0？看似“0”会提供更加完美的平衡。但实际上，高度差为0并非总能实现。例如，在某些情况下，树的节点数目较少（如2个或4个节点），无法做到完全平衡。实际上，保持平衡因子在-1到1之间，已经能确保树的操作效率接近最优。
4. AVL树的结构与完全二叉树相似，且由于它的高度差限制，它的高度在最坏情况下为O(log n)。这使得在AVL树上进行增、删、查、改等操作的时间复杂度都为O(log n)，比普通的二叉搜索树（BST）效率要高得多。

二、AVL树的模拟实现

1. 节点结构体和树的类模板

我们通过采用类模板的形式来实现VAL树，并且使用pair来储存键对值；所以我们需要引入头文件<utility>，并且展开命名空间std，以便于使用pair类型。

为了高效访问节点成员，我们使用struct来定义AVL树的节点结构体。每个节点包括以下成员：键对值（pair(K , V)）: 存储节点的数据。左右子节点指针（left,right）:指向左右子树的指针，用于我们构建二叉搜索树的结构。平衡因子（balanceFactor）:用于个衡量树的平衡性。当节点平衡因子为1 或0或-1的时候，树是平衡的，超过这个范围则需要通过旋转操作来恢复平衡。父节点指针（parent）:用于指向当前节点的父节点，帮助进行旋转操作时的节点链接。

这种设计使得节点的结构呈现出三叉链结构，即每个节点不仅有左右子树的指针，还有指向父亲节点的指针。这种结构方便我们在旋转操作的时候直接访问父节点，从而进行必要的树的结构调整。

// 节点结构体模板template<classK,classV>structAVLTreeNode{ pair<K, V> _data;// 存储节点的键值对 AVLTreeNode* _left;// 左子树指针 AVLTreeNode* _right;// 右子树指针 AVLTreeNode* _parent;// 父节点指针int _bf;// 平衡因子（Balance Factor）// 构造函数：初始化节点数据与指针AVLTreeNode(const pair<K, V>& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

在实现AVL树的类模板的时候，我们为AVLTreeNode类型定义了一个简化的别名Node，这样可以避免在代码中多次重复的使用长类型名称。接下来我们定义AVL的构造函数，根节点初始化为空。

• 根节点的特别之处在于，它没有父节点，因此parent指针默认为nullptr。为了防止外部访问根节点，我们将根节点设置成私有成员。

// AVL树模板类template<classK,classV>classAVLTree{private:using Node = AVLTreeNode<K, V>;// 使用别名简化节点类型书写 Node* _root;// 树的根节点指针public:// 构造函数：初始化根节点为空AVLTree():_root(nullptr){}// 析构函数（后续可实现）~AVLTree()=default;// 其他成员函数（插入、旋转、平衡调整等）后续实现};

2. 平衡因子的概念和实现

1. 平衡因子（Balance Factor，简称BF）本质上是一个int变量，用于判断AVL树中某个节点是否需要进行旋转以保持树的平衡。每当节点的插入或者删除时，平衡因子都会随之更新，用来实时反映当前节点的平衡状态。
   计算方法：平衡因子 = 右子树高度 - 左子树高度

2. 从理论上来讲，我们不使用平衡因子也可以通过递归计算左右子树的高度差来判断是否需要进行旋转。但是这种方法的效率太过于低下，每次判断都需要我们去重新遍历子树获取高度，造成大量的重复计算。

3. 引入平衡因子后，我们可以间接通过高度差来判断是否需要进行旋转，大幅度提升性能。它相当于一个“平衡信号灯”，能够快速标识节点的平衡状态，便于在插入或者删除节点的时候及时调整树的结构。它的取值范围(-1，0，1)：

BF = 0，左右子树的高度相等，树处于完全平衡状态
BF = 1，右子树比左子树高一层，轻微右倾斜
BF = -1，左子树比右子树高一层，轻微左倾斜注意： 一旦 某个节点的平衡因子的绝对值超过1（BF = 2 或BF = -2 ），就说明该节点已经失衡，不再满足AVL树的平衡条件，需要通过旋转操作去恢复平衡。

4. 当 AVL 树出现失衡时，需要通过旋转来调整结构，使平衡因子重新回到 [-1, 1] 区间。根据失衡的方向与位置不同，AVL 树有四种旋转方式： 左单旋（Right-Right 失衡）、 右单旋（Left-Left 失衡）、左右双旋（Left-Right 失衡）、右左双旋（Right-Left 失衡）。

5. 当在 AVL 树中插入新节点时，需要逐级向上更新其祖先节点的平衡因子：
   若新节点插入在父节点的右子树，则父节点的平衡因子 +1；
   若新节点插入在父节点的左子树，则父节点的平衡因子 −1。
   通过这种规律更新，可以有效追踪整棵树在插入操作后的平衡状态，并在必要时触发相应的旋转操作。

3. 插入

在AVL树的插入操作中，我们在插入新节点后需要从插入点开始，自下而上的更新各祖先节点的平衡因子。根据平衡因子的变化来决定树是否需要继续更新或者是否需要旋转。

①parent更新后平衡因子 = 0（BF = 0）的情况：

当更新的过程中，parent的平衡因子由 -1-> 或者1->0,parent的左右子树高度差为1，即一边高一边低；而新节点被插入在了较低的一边，使得两边重新到达了平衡。此时，parent所在的子树的整体高度并没有发生变化，，因此不会影响更高层父节点的平衡性。即更新到此结束，无需继续向上更新。

②parent更新后平衡因子 = 1 / -1（BF = 正负1）的情况：

当parent的平衡因子由0->1或0->-1，表示在插入前，左右子树高度相同；而插入新节点后，导致其中的一边高度增加1，parent变得一高一低。尽管此时parent子树任然保持平衡（平衡因子的绝对值小于等于1），但是该子树的高度整体增加了1，这样高度变化将传递给更高层的父节点。即需要继续向上更新祖先节点的平衡因子。

③parent更新后平衡因子 = 2 / -2（BF = 正负2）的情况：

当parent的平衡因子由1->2或**-1->-2**，表示插入节点出现在了左右子树高的一边，导致孩子更加失衡；此时AVL的平衡性被破坏，必须进行旋转操作来恢复平衡。让parent子树重新平衡（|BF| 小于等于1）；让子树高度恢复到插入前的高度，防止失衡继续向上传递。由于旋转后子树的高度恢复正常，因此旋转结束后无需再继续向上更新。即执行旋转并结束插入过程。

④ 更新到根节点的终止条件：
在不断向上更新的过程中，如果最终更新到了根节点，且根的平衡因子为 ±1，说明树依旧平衡，插入操作至此完成。若在更新过程中触发了旋转，则更早地已经结束更新。即当根平衡或局部旋转完成后，插入更新终止。

//插入boolInsert(const pair<K, V>& data){//如果根节点是空，直接new一个新的当作跟节点并返回正确if(_root ==nullptr){ _root =newNode(data);returntrue;}//如果根节点不是空，按照插入规则查找到需要插入节点的位置else{ Node* parent =nullptr; Node* cur = _root;while(cur !=nullptr){if(data.first > cur->_data.first)//插入的节点的key值大于当前节点的key值{ parent = cur; cur = cur->_right;}elseif(data.first < cur->_data.first)//插入的节点的key值小于当前节点的key值{ parent = cur; cur = cur->_left;}else{returnfalse;}//插入的节点的key值等于当前节点的key值，返回错误} cur =newNode(data);//找到需要插入新节点的位置，new出来 cur->_parent = parent;//三叉链的结构需要我们在创建新节点后重新链接父节点//判断新插入节点是在父节点的左边还是右边if(cur->_data.first > parent->_data.first){ parent->_right = cur;}else{ parent->_left = cur;}//更新平衡因子while(parent !=nullptr){if(cur == parent->_right){ parent->_bf++;}else{ parent->_bf--;}// 如果 parent->_bf == 0，说明当前子树重新恢复平衡，高度未变化，停止更新if(parent->_bf ==0){break;}elseif(parent->_bf ==1|| parent->_bf ==-1){ cur = parent; parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){//失衡节点右子树高且它的右孩子的右子树高，只需要进行左单旋if(parent->_bf ==2&& cur->_bf ==1){RotateL(parent);}//失衡节点左子树高且它的左孩子的左子树高，只需要进行右单旋elseif(parent->_bf ==-2&& cur->_bf ==-1){RotateR(parent);}//失衡节点右子树高且它的右孩子的左子树高，需要进行右左单旋elseif(parent->_bf ==2&& cur->_bf ==-1){RotateRL(parent);}//失衡节点左子树高且它的左孩子的右子树高，需要进行左右单旋elseif(parent->_bf ==-2&& cur->_bf ==1){RotateLR(parent);}//如果cur的平衡因子不符合为1或-1的情况，说明在插入前树已经不是AVL树直接断言错误即可else{assert(false);}break;}//如果parent的平衡因子不符合为0，1或-1，2或-2的情况说明在插入前树已经不是AVL树了，直接断言错误即可else{assert(false);}}returntrue;}}

4. 旋转操作

4.1 右单旋

• 如图，这颗以10为根节点的树，左右分别挂接了三棵抽象子树a，b，c。其中三者的高度均为h（h大于等于0），并且都满足AVL的平衡特性。这里的a，b，c是一种高度抽象的表示方式，用于概括所有可能触发右单旋的场景。实际上，不同节点的插入位置会形成多种具体结果，但是核心原理一致。
• 核心思想：因为a<5<b<10，我们可以选取中间节点5来充当新的平衡中枢：

在这种结构下，当在a的子树中插入一个新节点时，a的高度会从h增加到h+1.插入后在回溯更新平衡因子的过程中，根节点的平衡因子从-1变成了-2，此时该节点的左子树高度过高，导致AVL平衡性被破坏。我们需要执行右单旋操作，即将树向右旋转，使左右子树重新恢复平衡。

将5提升为新的根节点原根节点10变为5的右子树，b变为10的左子树

经过右单旋后，整棵树依然符合二叉搜索树的有序性规则，同时恢复了AVL的平衡性。此前该局部子树的高度重新与之前保持一致。

//右单旋,此时的parent是失衡节点voidRotateR(Node* parent){ Node* ppNode = parent->_parent; Node* cur = parent->_left; Node* curR = cur->_right; parent->_left = curR;if(curR){ curR->_parent = parent;} cur->_right = parent; parent->_parent = cur;//旋转后parent是根节点if(ppNode ==nullptr){ _root = cur; cur->_parent =nullptr;}else//旋转后parent不是根节点{if(ppNode->_left == parent){ ppNode->_left = cur; cur->_parent = ppNode;}else{ ppNode->_right = cur; cur->_parent = ppNode;}} parent->_bf = cur->_bf =0;}

4.2 左单旋

• 如图，这颗以10为根节点的树，左右分别挂接了三棵抽象子树c，b，a。其中三者的高度均为h（h大于等于0），并且都满足AVL的平衡特性。这里的a，b，c是一种高度抽象的表示方式，用于概括所有可能触发右单旋的场景。实际上，不同节点的插入位置会形成多种具体结果，但是核心原理一致。
• 核心思想：因为a>15>b>c，我们可以选取中间节点15来充当新的平衡中枢：

在这种结构下，当在a的子树中插入一个新节点时，a的高度会从h增加到h+1.插入后在回溯更新平衡因子的过程中，根节点的平衡因子从1变成了2，此时该节点的右子树高度过高，导致AVL平衡性被破坏。我们需要执行左单旋操作，即将树向左旋转，使左右子树重新恢复平衡。

将15提升为新的根节点原根节点10变为15的左子树，b变为10的右子树

经过右单旋后，整棵树依然符合二叉搜索树的有序性规则，同时恢复了AVL的平衡性。此前该局部子树的高度重新与之前保持一致。

voidRotateL(Node* parent){ Node* ppNode = parent->_parent; Node* cur = parent->_right; Node* curL = cur->_left; parent->_right = curL;if(curL){ curL->_parent = parent;} cur->_left = parent; parent->_parent = cur;if(ppNode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{if(ppNode->_left == parent){ ppNode->_left = cur; cur->_parent = ppNode;}else{ ppNode->_right = cur; cur->_parent = ppNode;}} parent->_bf = cur->_bf =0;}

4.3 左右双旋

• 通过下面两张图片可以看到，当树的左侧较高时，如果新节点插入的位置不是在 a 子树，而是在 b 子树中，就会出现一种特殊的失衡情况。此时，b 子树的高度从 h 增加到 h + 1，引发以 10 为根节点的子树失衡。由于插入位置在左子树的右侧，这种情况仅靠一次右单旋无法恢复平衡。

右单旋能解决的是“纯粹的左高”问题，也就是插入节点位于左子树的左侧（LL型）。而当前这种情况中，对于节点 10 来说，它的左子树确实更高；但对于它的左孩子 5 来说，右子树更高。也就是说，这是一种“左边高，但左子树内部又右边高”的复合型失衡，右单旋后树仍然无法平衡。

1. 第一次旋转（局部修正）：
   以节点 5 为旋转点，进行一次左单旋，让 b 子树 上升，修复左子树内部的右高问题。

第二次旋转（整体平衡）：
再以节点 10 为旋转点，进行一次右单旋，从全局上恢复树的平衡。

//左右双旋是失衡节点的左子树过高，但是它的左孩子cur的右子树过高voidRotateLR(Node* parent){ Node* cur = parent->_left; Node* curR = cur->_right;int bf = curR->_bf;RotateL(cur);RotateR(parent);//此时插入的节点就是curRif(bf ==0){ parent->_bf =0; cur->_bf =0; curR->_bf =0;}elseif(bf ==-1)//此时插入的节点是在curR的左子树里{ parent->_bf =1; cur->_bf =0; curR->_bf =0;}elseif(bf ==1)//此时说明插入的节点是在curR的右子树里{ parent->_bf =0; cur->_bf =-1; curR->_bf =0;}else{assert(false);}}

4.4 右左双旋

右左双旋（RL型）发生在节点的右子树过高，但其右孩子的左子树高度增加时产生的复合型失衡。以节点 10 为例，当新节点插入到其右子树的左侧（即 b 子树）时，虽然 10 的右子树整体更高，但其右孩子 15 的左子树比右子树高，这种情况下仅靠左或右单旋都无法恢复整棵树的平衡。

解决方法分为两个步骤：

1. 第一次旋转（局部调整）：
   以节点 15 为旋转点，对其左子树（b 子树）进行一次右单旋，将新插入节点上升，修复右子树内部的左高问题。
2. 第二次旋转（整体平衡）：
   再以节点 10 为旋转点进行一次左单旋，从全局上恢复整棵树的平衡，使左右子树高度差恢复到 ±1。

为了更精确地分析平衡因子变化，可将 b 子树进一步拆解为高度为 h-1 的 e 和 f 子树，以及新插入节点 12。根据新增节点的位置不同，平衡因子的更新也不同，可分为三种场景：

• 场景1：新节点插入 e 子树
  e 子树高度从 h-1 增加到 h，引起平衡因子更新自下而上（12 → 15 → 10）。此时 12 的平衡因子为 -1，旋转后 10 和 12 的平衡因子均为 0，而 15 的平衡因子为 1。
• 场景2：新节点插入 f 子树
  f 子树高度从 h-1 增加到 h，平衡因子更新同样自下而上（12 → 15 → 10），此时 12 的平衡因子为 1，旋转后 12 和 15 的平衡因子为 0，而 10 的平衡因子为 -1。
• 场景3：b 子树为空（h = 0）
  a、b、c 子树均为空，b 本身就是新增节点。平衡因子更新自下而上（15 → 10 → 根），旋转后 10、12 和 15 的平衡因子均为 0。

通过以上步骤，右左双旋能够有效解决右子树左高导致的复合型失衡，保证 AVL 树在插入节点后仍然保持平衡。

//右左双旋是失衡节点的右子树过高，但是它的右孩子cur的左子树过高voidRotateRL(Node* parent){ Node* cur = parent->_right; Node* curL = cur->_left;int bf = curL->_bf;RotateR(cur);RotateL(parent);//此时插入的节点就是curLif(bf ==0){ parent->_bf =0; cur->_bf =0; curL->_bf =0;}elseif(bf ==-1)//此时插入的节点是在curL的左子树里{ parent->_bf =0; cur->_bf =1; curL->_bf =0;}elseif(bf ==1)//此时说明插入的节点是在curL的右子树里{ parent->_bf =-1; cur->_bf =0; curL->_bf =0;}else{assert(false);}}

三、AVL树的平衡检测

public:intHeight(){returnHeight(_root);}

• 这是一个公有接口函数，用于获取整个 AVL 树的高度。
• 它调用了私有递归函数 Height(Node* root)，传入根节点 _root 作为参数。

private:intHeight(Node* root){if(root ==nullptr){return0;}int heightL =Height(root->_left);int heightR =Height(root->_right);return heightL > heightR ? heightL +1: heightR +1;}

1. 基准情况（递归结束条件）

if(root ==nullptr){return0;}

• 如果当前节点为空，则高度为 0。
• 这是递归的终止条件。

2. 递归求左右子树高度

int heightL =Height(root->_left);int heightR =Height(root->_right);

• 分别计算左子树和右子树的高度。

3. 返回当前节点高度

return heightL > heightR ? heightL +1: heightR +1;

• 节点高度 = 左右子树中较大的高度 + 1（加上当前节点自己）。
• 这是标准的二叉树高度计算公式。

public:boolIsbalance(){returnIsbalance(_root);}

• 公有接口函数，用于检查整棵 AVL 树是否平衡。
• 调用递归私有函数 Isbalance(Node* root)，从根节点开始。

private:boolIsbalance(Node* root){if(root ==nullptr){returntrue;} Node* left = root->_left; Node* right = root->_right;int heightL =Height(left);int heightR =Height(right);int bf = heightR - heightL;if(bf != root->_bf){ cout <<"平衡因子异常"<< root->_data.first <<':'<< root->_bf << endl;returnfalse;}returnabs(bf)<=1&&Isbalance(left)&&Isbalance(right);}

1. 基准情况

if(root ==nullptr){returntrue;}

• 空树或空节点被认为是平衡的。

2. 获取左右子树指针

Node* left = root->_left; Node* right = root->_right;

• 为了方便后续计算高度和递归检查。

3. 计算左右子树高度

int heightL =Height(left);int heightR =Height(right);int bf = heightR - heightL;

• AVL 树平衡因子定义为：右子树高度 - 左子树高度。
• bf 是当前节点的实际平衡因子。

4. 检查平衡因子与节点存储的值是否一致

if(bf != root->_bf){ cout <<"平衡因子异常"<< root->_data.first <<':'<< root->_bf << endl;returnfalse;}

• 如果计算得到的 bf 与节点 _bf 成员值不一致，则说明树的平衡因子维护出错。
• 会打印出异常节点，方便调试。

5. 判断节点是否平衡并递归检查左右子树

returnabs(bf)<=1&&Isbalance(left)&&Isbalance(right);

• AVL树平衡条件：平衡因子绝对值 ≤ 1。
• 并且左右子树也必须平衡，所以递归调用检查。

总结

AVL树通过限制节点左右子树高度差并引入平衡因子，实现了自平衡二叉搜索树。在插入节点时，平衡因子自下而上更新，并在必要时通过旋转操作恢复平衡，从而确保树的高度始终为O(log n)，保证增、删、查等操作效率高。本文通过结构化代码示例和旋转原理解析，使读者不仅理解AVL树的理论基础，更能掌握实际实现与调试方法，为构建高效的数据结构提供完整指导。

✨ 坚持用清晰易懂的图解+代码语言， 让每个知识点都简单直观！
🚀 个人主页 ：不呆头 · ZEEKLOG
🌱 代码仓库 ：不呆头 · Gitee
📌 专栏系列 ：📖 《C语言》🧩 《数据结构》💡 《C++》🐧 《Linux》💬 座右铭 ：“不患无位，患所以立。”