本文介绍 C++ 中 AVL 树（自平衡二叉搜索树）的原理与实现。AVL 树通过平衡因子控制左右子树高度差不超过 1，保证查找效率为 O(log n)。文章涵盖 AVL 树的基本性质、查找、插入及删除操作概述，重点讲解四种旋转平衡操作（左单旋、右单旋、左右双旋、右左双旋）。最后提供完整的 C++ 模板类代码实现，包括节点结构定义、插入时的平衡维护逻辑及旋转函数细节，帮助读者深入理解平衡二叉搜索树的核心机制。
AVL 树（Adelson-Velsky and Landis Tree）是一种自平衡二叉搜索树。它由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出。AVL 树是在普通二叉搜索树的基础上增加了平衡条件，确保树始终保持近似平衡状态。 AVL 树要么是空树，要么是满足以下性质的二叉搜索树：其左、右子树也都是 AVL 树，并且左、右子树的高度差的绝对值不超过 1。
从平衡的理想状态看，高度差为 0 确实更平衡，但实际情况中，部分树的结构无法满足这一要求。当树的节点数为 2、4……等特定数量时，最优的高度差只能是 1，无法强制达到 0。这说明 AVL 树的平衡条件是在'绝对平衡'和'实现可行性'之间的权衡设计。
每个节点都有一个平衡因子，其值等于该节点右子树的高度减去左子树的高度。因此，任何节点的平衡因子只能是 0、1 或 -1。平衡因子如同一个'风向标'，能帮助我们直观观察树的平衡状态并高效控制树的平衡维护过程——通过判断平衡因子是否超出 [-1, 1] 范围可快速定位需要调整的节点，进而通过旋转操作恢复树的平衡。
定义进行遍历节点的指针，使用 while 循环查找对应节点：
curr 指向根节点 _root。curr->_kv.first 与要查找的键 key 进行比较：
curr->_kv.first < key，这意味着要查找的节点在当前节点的右子树中，所以将 curr 更新为 curr->_right，继续在右子树中查找。curr->_kv.first > key，说明要查找的节点在当前节点的左子树中，将 curr 更新为 curr->_left，继续在左子树中查找。curr->_kv.first == key，表示找到了要查找的节点，直接返回当前节点的指针 curr。curr 变为 nullptr，这表明在整个 AVL 树中没有找到键为 key 的节点，此时返回 nullptr。AVL 树的插入操作是在二叉搜索树插入逻辑基础上，增加了平衡维护的关键步骤，核心要解决'插入新节点可能破坏树的平衡，导致查询效率下降'的问题。
AVL 树插入 = 二叉搜索树插入（找位置、挂节点） + 平衡修复（更新平衡因子 + 旋转调整）。 流程分 5 步：
parent，确定挂左还是挂右。parent 的左 / 右子树，并维护 parent 指针。_bf），反映子树高度变化。while (parent)
{
// 第一步：更新新插入节点的父节点的平衡因子
// 位置 1：新插入节点是左子节点 —> 父节点的平衡因子 -1
if(current == parent->_left){ parent->_bf--; }
// 位置 2：新插入节点是右子节点 —> 父节点的平衡因子 +1
else{ parent->_bf++; }
// 第二步：根据父节点的平衡因子做进一步的更新
// 情况 1：父节点的平衡因子为 0 —> 高度变化未影响上层，结束更新
if(parent->_bf == 0){ break; }
// 情况 2：父节点的平衡因子为±1 —> 高度变化需向上传递，继续更新上层节点
else if(parent->_bf == -1 || parent->_bf == 1){ current = current->_parent; parent = parent->_parent; }
// 情况 3：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
else if(parent->_bf == -2 || parent->_bf == 2)
{
// 失衡 1：左左失衡（父子平衡因子都为'负'） —> 右单旋
if(parent->_bf == -2 && current->_bf == -1){ RotateR(parent); }
// 失衡 2：右右失衡（父子平衡因子都为'正'） —> 左单旋
else if(parent->_bf == 2 && current->_bf == 1){ RotateL(parent); }
// 失衡 3：左右失衡（父为'负'，子为'正'） —> 左右双旋
else if(parent->_bf == -2 && current->_bf == 1){ RotateLR(parent); }
// 失衡 4：右左失衡（父为'正'，子为'负'） —> 右左双旋
else if(parent->_bf == 2 && current->_bf == -1){ RotateRL(parent); }
// 特殊情况：非法平衡因子 —> 断言失败
else{ assert(false); }
break;
}
}
return true;
[图片]
AVL 树的删除操作较为复杂，涉及多次旋转调整以恢复平衡，此处暂不展开详细代码实现，重点在于理解插入过程中的平衡维护机制。
AVL 树通过下面的四种旋转操作维护平衡，这些操作在插入或删除节点导致树失衡时自动触发。
当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的左子树插入节点导致的（即左子树的左子树深度增加，称为'LL 型失衡'），此时需要通过右单旋来恢复平衡。
旋转过程分为三步（以节点 parent 为旋转中心）：
parent 的左子节点 subL 提升为新的根节点。subL 的右子树 subLR 需要重新挂接到 parent 的左子树。_parent 指针，维护三叉链结构。// 第一阶段：准备阶段
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
Node* pParent = parent->_parent;
// 第二阶段：调整阶段
parent->_left = subLR;
if(subLR){ subLR->_parent = parent; }
parent->_parent = subL;
subL->_right = parent;
// 第三阶段：调整根节点或祖父节点的子树指向
if(parent == _root){ _root = subL; subL->_parent = nullptr; }
else
{
if(parent == pParent->_left){ pParent->_left = subL; }
else{ pParent->_right = subL; }
subL->_parent = pParent;
}
// 第四阶段：更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
[图片]
当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的右子树插入节点导致（即右子树的右子树深度增加，称为'RR 型失衡'）时，需要通过左单旋恢复平衡。
旋转过程分为三步（以节点 parent 为旋转中心）：
parent 的右子节点 subR 提升为新的根节点。subR 的左子树 subRL 需要重新挂接到 parent 的右子树。_parent 指针，维护三叉链结构。// 第一阶段：准备阶段
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
Node* pParent = parent->_parent;
// 第二阶段：调整阶段
parent->_right = subRL;
if(subRL){ subRL->_parent = parent; }
parent->_parent = subR;
subR->_left = parent;
// 第三阶段：调整根节点或祖父节点的子树指向
if(pParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if(parent == pParent->_left){ pParent->_left = subR; }
else{ pParent->_right = subR; }
subR->_parent = pParent;
}
// 第四阶段：更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
[图片]
当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的右子树插入节点导致（即左子树的右子树深度增加，称为'LR 型失衡'）时，需要通过左右双旋恢复平衡。左右双旋是左单旋 + 右单旋的复合操作，专门处理 LR 型失衡。
subL 的右子节点 subLR 提升为新根，subLR 的左子树 subLRL 挂接到 subL 的右子树。subLR 提升为整棵子树的根，subLR 的原右子树 subLRR 挂接到 parent 的左子树。_parent 指针，确保三叉链结构正确。subLR 的左 / 右子树），分情况修正 subLR、subL、parent 的平衡因子为 0 或 ±1。void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
int bf = subLR->_bf;
// 首先对当前的节点的左子树进行'左单旋'
RotateL(parent->_left);
// 然后对当前的节点进行'右单旋'
RotateR(parent);
// 更新平衡因子
if(bf == -1){ subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; }
else if(bf == 1){ subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; }
else if(bf == 0){ subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; }
else{ assert(false); }
}
[图片]
当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的左子树插入节点导致（即右子树的左子树深度增加，称为'RL 型失衡'）时，需要通过右左双旋恢复平衡。右左双旋是右单旋 + 左单旋的复合操作，专门处理 RL 型失衡。
subR 的左子节点 subRL 提升为新根，subRL 的左子树 subRLR 挂接到 subR 的左子树。subRL 提升为整棵子树的根，subRL 的原左子树 subRLL 挂接到 parent 的右子树。_parent 指针，确保三叉链结构正确。subRL 的左 / 右子树），分情况修正 subRL、subR、parent 的平衡因子为 0 或 ±1。void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
int bf = subRL->_bf;
// 首先对当前的节点的右子树进行'右单旋'
RotateR(parent->_right);
// 然后对当前的节点进行'左单旋'
RotateL(parent);
// 更新平衡因子
if(bf == -1){ subRL->_bf = 0; subR->_bf = 1; parent->_bf = 0; }
else if(bf == 1){ subRL->_bf = 0; subR->_bf = 0; parent->_bf = -1; }
else if(bf == 0){ subRL->_bf = 0; subR->_bf = 0; parent->_bf = 0; }
else{ assert(false); }
}
[图片]
AVL 树在二叉链基础上，额外增加了父节点指针、平衡因子来实现'自平衡'。严格来说，它属于三叉链存储结构（节点包含左子、右子、父节点三类指针），再配合平衡因子记录子树高度差。
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};
template<class K, class V>
class AVLTree
{
private:
AVLTreeNode<K, V>* _root = nullptr;
typedef AVLTreeNode<K, V> Node;
public:
// ... 成员函数 ...
};
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};
template<class K, class V>
class AVLTree
{
private:
AVLTreeNode<K, V>* _root = nullptr;
typedef AVLTreeNode<K, V> Node;
void _InOrder(Node* root)
{
if(root == nullptr){ return; }
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
int _Height(Node* root)
{
if(root == nullptr){ return 0; }
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
bool _IsAVLTree(Node* root)
{
if(root == nullptr){ return true; }
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int bf = rightHeight - leftHeight;
if(abs(bf) >= 2){ return false; }
if(root->_bf != bf){ return false; }
return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
}
public:
Node* Find(const K& key)
{
Node* curr = _root;
while(curr)
{
if(curr->_kv.first < key){ curr = curr->_right; }
else if(curr->_kv.first > key){ curr = curr->_left; }
else{ return curr; }
}
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
if(_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* current = _root;
Node* parent = nullptr;
while(current)
{
if(current->_kv.first < kv.first)
{
parent = current;
current = current->_right;
}
else if(current->_kv.first > kv.first)
{
parent = current;
current = current->_left;
}
else{ return false; }
}
current = new Node(kv);
if(kv.first < parent->_kv.first){ parent->_left = current; }
else{ parent->_right = current; }
current->_parent = parent;
while(parent)
{
if(current == parent->_left){ parent->_bf--; }
else{ parent->_bf++; }
if(parent->_bf == 0){ break; }
else if(parent->_bf == -1 || parent->_bf == 1)
{
current = current->_parent;
parent = parent->_parent;
}
else if(parent->_bf == -2 || parent->_bf == 2)
{
if(parent->_bf == -2 && current->_bf == -1){ RotateR(parent); }
else if(parent->_bf == 2 && current->_bf == 1){ RotateL(parent); }
else if(parent->_bf == -2 && current->_bf == 1){ RotateLR(parent); }
else if(parent->_bf == 2 && current->_bf == -1){ RotateRL(parent); }
else{ assert(false); }
break;
}
else{ assert(false); }
}
return true;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
Node* pParent = parent->_parent;
parent->_left = subLR;
if(subLR){ subLR->_parent = parent; }
parent->_parent = subL;
subL->_right = parent;
if(parent == _root){ _root = subL; subL->_parent = nullptr; }
else
{
if(parent == pParent->_left){ pParent->_left = subL; }
else{ pParent->_right = subL; }
subL->_parent = pParent;
}
subL->_bf = 0;
parent->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
Node* pParent = parent->_parent;
parent->_right = subRL;
if(subRL){ subRL->_parent = parent; }
parent->_parent = subR;
subR->_left = parent;
if(pParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if(parent == pParent->_left){ pParent->_left = subR; }
else{ pParent->_right = subR; }
subR->_parent = pParent;
}
subR->_bf = 0;
parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if(bf == -1){ subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; }
else if(bf == 1){ subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; }
else if(bf == 0){ subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; }
else{ assert(false); }
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if(bf == -1){ subRL->_bf = 0; subR->_bf = 1; parent->_bf = 0; }
else if(bf == 1){ subRL->_bf = 0; subR->_bf = 0; parent->_bf = -1; }
else if(bf == 0){ subRL->_bf = 0; subR->_bf = 0; parent->_bf = 0; }
else{ assert(false); }
}
void InOrder(){ _InOrder(_root); cout << endl; }
int Height(){ return _Height(_root); }
int Size(){ return _Size(_root); }
bool IsAVLTree(){ return _IsAVLTree(_root); }
};
#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include"AVLTree.h"
void TestAVLTree1()
{
cout << "------------------测试基本插入和平衡性------------------" << endl;
AVLTree<int,int> t;
int a2[] = {4,2,6,1,3,5,15,7,16,14};
for(auto e : a2){ t.Insert({ e, e }); }
t.InOrder();
cout << "如果构建的那棵树是 AVL 树的话请扣 1：" << t.IsAVLTree() << endl;
}
int main()
{
TestAVLTree1();
return 0;
}
[图片]
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online