【C++】AVL树：入门到精通全图解

普通二叉搜索树有时会越插越“歪”，最后像链表一样，查找就变慢了。AVL树就是为了解决这个问题：它会在插入后顺着父结点往上检查，一旦发现左右高度差太大，就通过旋转把树“掰回去”，让高度一直保持在O(logN)。本文用C++模板代码把平衡因子怎么更新、什么时候该停、四种旋转怎么写讲清楚，并给出校验方法方便自测。

一、AVL的概念

1.1 AVL树是什么

AVL树是一种“自平衡”的二叉搜索树。它要么是空树，要么满足：

• 左右子树都是AVL树；
• 左右子树的高度差（绝对值）不超过1。

它的核心目的很直白：通过控制高度差，避免树退化成链表，让增删查改的效率更稳定。

1.2 平衡因子(balance factor)是什么，有什么用

实现AVL树时通常会给每个结点维护一个平衡因子（balance factor）：

• 平衡因子 = 右子树高度 - 左子树高度
• 因为AVL要求高度差不超过1，所以平衡因子只能是：-1 / 0 / 1

平衡因子不是“必须存在”的信息，但有了它，就能更直观地判断结点是否失衡（类似“风向标”）：
一旦出现2或-2，立刻知道哪里失衡、该旋转了。

1.3 为什么要求高度差≤1，而不是必须等于0

直觉上“高度差=0”更完美，但并不是所有结点数都能做到完全左右等高。

举个最小的例子：只有2个结点时，结构只能是：

此时根的高度差必然是1，没法做到0。类似地，4个结点等情况也会出现“最好只能差1”的结构。
所以AVL的规则是：尽可能平衡，但允许差1。

另外，AVL整体结点分布接近完全二叉树，高度可以控制在logN，因此增删查改效率也能控制在O(logN)。

二、AVL树的实现

2.1 AVL树的结构

实现里每个结点至少需要：

• _kv：用pair<K,V>存键值对（key在first，value在second）
• _left/_right：左右孩子
• _parent：父结点指针（后面更新平衡因子会更顺手）
• _bf：平衡因子

template<classK,classV>structAVLTreeNode{//需要parent指针，后续更新平衡因子可以看到pair<K,V>_kv;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;//balance factorAVLTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

2.2 AVL树类的基本框架

这里只展示最关键的结构：根指针_root。

template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public://...private:Node*_root=nullptr;};

三、AVL树的插入

3.1 插入一个值的大概过程

总体可分为：

1. 按二叉搜索树规则插入新结点；
2. 新增结点只会影响它到根路径上的祖先高度，所以沿路径向上更新平衡因子；
3. 如果更新过程中一直合法（平衡因子仍在-1/0/1），插入结束；
4. 如果更新过程中出现失衡（±2），对失衡子树做旋转：旋转一边“调平衡”，一边“降高度”，因此不再影响更上一层，插入结束。

3.2 平衡因子更新原则

重点：

• 平衡因子 = 右子树高度 - 左子树高度

• 插入会导致某一侧高度+1

  • 新结点插到parent的右子树：parent->_bf++
  • 新结点插到parent的左子树：parent->_bf--

3.3 更新停止条件

下面这张表把停止条件说清楚（这是插入能否继续往上更新的关键）：

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

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

最坏更新到根停止

3.4 插入结点及更新平衡因子的代码实现

代码分为两部分：

• 前半段：按BST规则找插入位置；
• 后半段：从插入点向上更新平衡因子，遇到0/±1/±2分别处理。

boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first<kv.first){parent->_right=cur;}else{parent->_left=cur;}cur->_parent=parent;//更新平衡因子while(parent){//更新平衡因子：看cur是挂在parent的哪一边if(cur==parent->_left)parent->_bf--;elseparent->_bf++;if(parent->_bf==0){//更新结束break;}elseif(parent->_bf==1||parent->_bf==-1){//继续往上更新cur=parent;parent=parent->_parent;}elseif(parent->_bf==2||parent->_bf==-2){//不平衡了，旋转处理break;}else{assert(false);}}returntrue;}

重点：

• parent->_bf == 0：说明“补低边”，高度不变，直接停；
• parent->_bf == ±1：说明高度+1，会影响上一层，继续往上；
• parent->_bf == ±2：说明已经失衡，下一步应进入旋转

四、旋转

4.1 旋转的原则

旋转要同时满足两个目标：

1. 保持二叉搜索树的大小关系（中序仍然有序）
2. 让失衡子树恢复平衡，并且尽量降低它的高度（这样不会继续影响更上一层）

旋转一共四种：

• 右单旋（LL）
• 左单旋（RR）
• 左右双旋（LR）
• 右左双旋（RL）

4.2 右单旋

右单旋通常对应“左边太高”的失衡：
在某个结点（比如10）左子树里插入结点，导致10的平衡因子从-1变成-2，需要把“左高”往右转一转。

可以理解为：

• a/b/c是三棵满足AVL的子树（高度为h）
• 在a里插入导致a高度从h变成h+1
• 10的左边变更高 → 需要右单旋

4.3 右单旋代码实现

右单旋的“指针改动”要同时处理：

• 孩子指针（left/right）
• 父指针（parent）
• parent是否是整棵树的根（要不要更新_root）

voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;//需要注意除了要修改孩子指针指向，还是修改父亲parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*parentParent=parent->_parent;subL->_right=parent;parent->_parent=subL;//parent有可能是整棵树的根，也可能是局部的子树//如果是整棵树的根，要修改_root//如果是局部的指针要跟上一层链接if(parentParent==nullptr){_root=subL;subL->_parent=nullptr;}else{if(parent==parentParent->_left){parentParent->_left=subL;}else{parentParent->_right=subL;}subL->_parent=parentParent;}parent->_bf=subL->_bf=0;}

这里最后一句把parent和subL的平衡因子置0，是右单旋最常见的“插入修复”场景。

4.4 左单旋

左单旋对应“右边太高”：
在某个结点（比如10）右子树里插入，导致平衡因子从1变成2，需要往左旋转恢复平衡。

4.5 左单旋代码实现

voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*parentParent=parent->_parent;subR->_left=parent;parent->_parent=subR;if(parentParent==nullptr){_root=subR;subR->_parent=nullptr;}else{if(parent==parentParent->_left){parentParent->_left=subR;}else{parentParent->_right=subR;}subR->_parent=parentParent;}parent->_bf=subR->_bf=0;}

4.6 左右双旋

“左边高”并不总能用右单旋解决。
如果插入位置不是在更“外侧”的a里，而是在“内侧”的b里，会出现这种情况：

• 对10来说：左边高（需要往右转）
• 但对5来说：右边高（需要先把5的右高修正）

所以要做两次旋转：

1. 以5为旋转点做一次左单旋；
2. 再以10为旋转点做一次右单旋。

左右双旋里，关键看中间结点（示例里的8）的平衡因子不同，会导致旋转后平衡因子修正不同，常见分三类：

• 新结点插在“e侧”→ 中间结点bf为-1
• 新结点插在“f侧”→ 中间结点bf为1
• h==0时中间结点bf为0
  

4.7 左右双旋代码实现

重点：

• 先记录subLR->_bf，因为旋转后结构变了，但我们需要它来决定平衡因子怎么修正
• 旋转顺序固定：RotateL(parent->_left)再RotateR(parent)

voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf==0){subL->_bf=0;subLR->_bf=0;parent->_bf=0;}elseif(bf==-1){subL->_bf=0;subLR->_bf=0;parent->_bf=1;}elseif(bf==1){subL->_bf=-1;subLR->_bf=0;parent->_bf=0;}else{assert(false);}}

4.8 右左双旋

右左双旋和左右双旋是对称关系：

• “右边高”但插在“内侧”位置

• 单次左旋不够，需要：

  1. 先对右孩子做右单旋
  2. 再对当前结点做左单旋

同样地，中间结点（示例里的12）平衡因子不同，会分三种场景讨论。

4.9 右左双旋代码实现

voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf==0){subR->_bf=0;subRL->_bf=0;parent->_bf=0;}elseif(bf==1){subR->_bf=0;subRL->_bf=0;parent->_bf=-1;}elseif(bf==-1){subR->_bf=1;subRL->_bf=0;parent->_bf=0;}else{assert(false);}}

五、AVL树的查找

5.1 查找思路

查找完全沿用二叉搜索树逻辑：

• 目标key小于当前结点key → 去左子树
• 大于 → 去右子树
• 等于 → 找到

因为AVL高度是logN级别，所以查找效率是O(logN)。

二叉搜索树详情可见：https://blog.csdn.net/weixin_65182626/article/details/157104096?fromshare=blogdetail&sharetype=blogdetail&sharerId=157104096&sharerefer=PC&sharesource=weixin_65182626&sharefrom=from_link

5.2 查找代码

Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_kv.first<key){cur=cur->_right;}elseif(cur->_kv.first>key){cur=cur->_left;}else{returncur;}}returnnullptr;}

如果存的是pair<K,V>，找到结点后就能直接用node->_kv.second读写value（比如做词频统计、字典映射等）。

六、AVL树平衡检测

实现完AVL树后，最好验证两件事：

1. 每个结点左右子树高度差是否在[-1,1]范围内；
2. 结点里保存的_bf是否和“真实高度差”一致（防止更新逻辑写错）。

6.1 求高度

int_Height(Node*root){if(root==nullptr)return0;intleftHeight=_Height(root->_left);intrightHeight=_Height(root->_right);returnleftHeight>rightHeight?leftHeight+1:rightHeight+1;}

6.2 检查是否平衡

bool_IsBalanceTree(Node*root){//空树也是AVL树if(nullptr==root)returntrue;//计算root结点的平衡因子：即root左右子树的高度差intleftHeight=_Height(root->_left);intrightHeight=_Height(root->_right);intdiff=rightHeight-leftHeight;//如果计算出的平衡因子与root的平衡因子不相等，或者//root平衡因子的绝对值超过1，则一定不是AVL树if(abs(diff)>=2){cout<<root->_kv.first<<"高度差异常"<<endl;returnfalse;}if(root->_bf!=diff){cout<<root->_kv.first<<"平衡因子异常"<<endl;returnfalse;}//root的左和右如果都是AVL树，则该树一定是AVL树return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}

完