AVL 树实现
1. 二叉搜索树的缺陷
性能分析
- 查找 / 插入 / 删除（平均）时间复杂度：，h 为树高。
C++算法
C++ 手搓 AVL 树实现详解
AVL 树是一种自平衡二叉搜索树，通过平衡因子控制左右子树高度差不超过 1。当插入或删除导致失衡时，通过单旋或双旋恢复平衡。详细讲解了 AVL 树的概念、平衡因子计算、旋转操作（左旋、右旋、左右双旋、右左双旋）及 C++ 模板类实现，并通过随机数据测试验证了正确性。
AVL 树是一种自平衡二叉搜索树，通过平衡因子控制左右子树高度差不超过 1。当插入或删除导致失衡时，通过单旋或双旋恢复平衡。详细讲解了 AVL 树的概念、平衡因子计算、旋转操作（左旋、右旋、左右双旋、右左双旋）及 C++ 模板类实现，并通过随机数据测试验证了正确性。
O(1)；递归版本额外 O(h) 递归栈。结点数为 N的二叉搜索树，最多查找高度次。对于随机插入的平衡树平均 h = O(log n)；最坏情况下 h = O(n)。
log2 NN，查找效率退化为 O(N)，这也正是二叉搜索树的缺陷综合而言，⼆叉搜索树增删查改时间复杂度为：O(N)，这样的效率显然是⽆法满⾜我们需求的
AVL 树，满足我们在内存中存储和搜索数据高性能需求。二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在链表中搜索元素，效率低下。
AVL 树：是一种 自平衡二叉搜索树，由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出，其名称来源于这两位发明者的名字缩写。
AVL 树是最早发明的自平衡二叉搜索树
AVL 树是在普通二叉搜索树的基础上增加了平衡条件，确保树始终保持近似平衡状态AVL 树要么是空树，要么是满足以下性质的二叉搜索树：
如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log2 n)，搜索时间复杂度O(log2 n)
AVL 树是一颗高度平衡的搜索二叉树，通过控制高度差去控制平衡
AVL 树可以始终保持平衡状态，是因为在实现 AVL 树时，我们引入了 平衡因子（balance factor） 的概念：
每个节点都有一个平衡因子，其值等于该节点右子树的高度减去左子树的高度
当然平衡因子并非 AVL 树的必需属性，因为AVL 树的维持平衡不一定需要平衡因子，也可以动态计算高度或其他方法使 AVL 树保持平衡
但平衡因子如同一个'风向标'：
[-1, 1] 范围以下就是一颗 AVL 树，同时附有相应的平衡因子
而下面这棵树就不是一棵 AVL 树，因为 10 这个节点它的左右子树的高度差超过了 1
核心特点：
AVL 树通过不断调整树的结构，保证树的左右子树高度差始终在允许范围内，使得树的高度相对较低。
AVL 树高度平衡，其高度近似于 O(log N)，其中 n 是节点数量，这意味着在 AVL 树中进行查找操作时，时间复杂度稳定在 O(log N)基本操作：
优缺比较：
为什么AVL 树要求左右子树的高度差不超过 1，而非必须为 0 呢？
从平衡的理想状态看，高度差为 0 确实更平衡，但实际情况中，部分树的结构无法满足这一要求：
AVL 树的平衡条件是在'绝对平衡'和'实现可行性'之间的权衡设计template<class K,class V>
struct AVLTreeNode {
pair<K, V> _kv; // 键值对
// 三叉链
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent; // 插入结点后，需要更新平衡因子，有了_parent，可以很方便的找父节点
int _balanceFactor; // balance factor 平衡因子，用于判断当前子树 有没有出现不平衡的问题
// Node 结点 的构造函数
AVLTreeNode(const pair<K, V>& kv) :_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_balanceFactor(0) // 新结点 初始的平衡因子为 0
{}
};
std::pair<K, V>来存储我们的键值对AVLTreeNode<K, V>* _left：指向左孩子的指针AVLTreeNode<K, V>* _right：指向右孩子的指针AVLTreeNode<K, V>* _parent：指向父节点的指针
_parent,可以很方便的找父节点int _balanceFactor：平衡因子，用于判断当前子树 有没有出现不平衡的问题AVLTreeNode(const pair<K, V>& kv)：
nullptr，初始化平衡因子为 0kv初始化类内的_kv成员struct设计，默认权限为public，方便下文的AVLTree类访问成员template<class K,class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
private:
AVLTreeNode<K, V>* _root = nullptr;
public:
// ... 对外共有接口
private:
// ... 内部私有成员函数
};
AVLTreeNode<K, V>* _root = nullptr：初始时根节点为空typedef AVLTreeNode<K, V> Node：结点类型重定义，简化书写插入操作的本质是：
AVL 树的插入操作是在二叉搜索树插入逻辑基础上，增加了平衡维护的关键步骤，核心要解决'插入新节点可能破坏树的平衡，导致查询效率下降'的问题。插入操作思路的简述：
AVL 树插入 == 二叉搜索树插入（找位置、挂节点） + 平衡修复（更新平衡因子 + 旋转调整）
流程分 5 步：
parent，确定挂左还是挂右parent 的 左 or 右 子树，并维护 parent 指针_balacnFactor），反映子树高度变化public:
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// _root 不为空时的操作
Node* parent = nullptr;
Node* curNode = _root;
// 先找空，找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
}
// 搜索树中不允许有重复的值 对于已有值，不插入
else
return false;
}
// while 循环结束后，代表找到了可以插入的位置
// 找到位置了，但父节点不知道 新结点 比自己大还是比自己小，需要再次判断
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first)
parent->_left = curNode;
else
parent->_right = curNode;
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作 的代码
// 控制平衡 ...
}
详细讲解二叉搜索树迭代插入的逻辑）：
_root == nullptr，直接把根设为新节点（new Node(key)）。_root 向下查找插入位置：
curNode 跟随，parent 保存其父节点（因为当 curNode 为 nullptr 时需要把新节点挂到 parent）。kv.first > curNode->_kv.first，curNode沿右子树移动；kv.first < curNode->_kv.first时，curNode沿左子树移动。kv.first == curNode->_kv.first，返回 false（二叉搜索树默认不允许重复键）。curNode 走到 nullptr（找到空位）后，代表curNode已找到合适的可以插入的位置。new Node(kv) 建节点
curNode的父节点内的左右孩子指针，但父节点并不知道要插入的 key 比自己大还是自己小，只知道下面由位置可以插入，不知道插入到哪个位置key 与 parent->_key 的比较把它接为左/右子节点。
curNode->_kv.first > parent->_kv.first → 插到右边 (parent->_right = curNode)curNode->_kv.first < parent->_kv.first → 插到左边 (parent->_left = curNode)curNode == nullptr 的地方。
✔️ 但是插入操作不能直接修改 curNode，必须通过 parent 去改指针。
✔️ 而 parent 自己并不知道空位是在左边还是右边，所以需要再比较一次来决定。新创建结点的平衡因子：
新结点插入在右：
新结点插入在左：
更新后平衡因子 == 0：不用继续沿着到root的路径往上更新平衡因子
更新后平衡因子 == 1 or -1：继续沿着到root的路径往上更新平衡因子
更新后平衡因子 == 2 or -2：树已失衡，需进行旋转
while(parent)public:
bool insert(const pair<K, V>& kv) {
// ... 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作 ...
// 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
while (parent) {
// 插入后，先更新平衡因子
if (curNode == parent->_left)
--parent->_balanceFactor;
else // if (curNode == parent->_right)
++parent->_balanceFactor;
// 当前 parent 结点更新完了，判断是否还需要再往上更新
// 处理平衡因子更新后有三种情况
// 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转，结束循环
if (parent->_balanceFactor == 0) {
break;
}
// 情况二 parent 所在子树高度变了，继续往上更新
else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
curNode = parent;
parent = parent->_parent;
}
// 情况三 当前子树不平衡了，需要旋转
else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
// 旋转的情况和操作
}
else // 其他情况报错
assert(false);
// 平衡因子不是 0 1 -1 2 -2 直接报错
}
// 插入结束后，return true
return true;
}
核心操作：
while (parent)
/-------------第一步：更新新插入节点的父节点的平衡因子-------------/
-1+1/-------------第二步：根据父节点的平衡因子做进一步的更新-------------/
return true;旋转总共分为四种：根据不同的不平衡情况我们需要采取不同的旋转方式，这些操作在插入或删除节点导致树失衡时自动触发
需要旋转的情况：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
核心操作：旋转过程分为三步（以节点 60(curNode) 为旋转中心，对 parent 进行左单旋）
curLeft 和 parent 的链接关系，注意curLeft可能为空curNode成为整棵树的新根，_parent 指向 nullptr。最后再将parent正确挂载，成为curNode的左子树curNode的祖父结点ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将parent正确挂载，成为curNode的左子树左单旋原理：
private:
// 左单旋 2 1 newNode 练成线，单纯的右边高
void RotateL(Node* parent) {
if (parent == nullptr || parent->_right == nullptr)
return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left; // curLeft 有可能为空
// 先处理 curNode 的 left 结点，curLeft 有可能是空
parent->_right = curLeft;
if (curLeft)
curLeft->_parent = parent;
// 再处理 curNode 结点
// parent 有可能是根节点，也有可能是子树的根节点
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
parent->_balanceFactor = curNode->_balanceFactor = 0;
}
右单旋可以看做是左单旋的镜像操作
核心操作：旋转过程分为三步（以节点 30(curNode) 为旋转中心，对 parent 进行右单旋）
curRight 和 parent 的链接关系，注意curRight可能为空curNode成为整棵树的新根，_parent 指向 nullptr。最后再将parent正确挂载，成为curNode的左子树curNode的祖父结点ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将parent正确挂载，成为curNode的右子树private:
// 右单旋 -2 -1 newNode 连成线，单纯的左边高
void RotateR(Node* parent) {
// parent 为空 或 curNode 为空的情况
if (parent == nullptr || parent->_left == nullptr)
return;
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
// 把 curNode 的 right 给给 parent 的 left
parent->_left = curRight;
if (curRight)
curRight->_parent = parent;
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
curNode->_right = parent;
parent->_parent = curNode;
} else {
Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
curNode->_right = parent;
parent->_parent = curNode;
}
curNode->_balanceFactor = parent->_balanceFactor = 0;
}
左右双旋的过程以及平衡因子的更新：
关键操作：
cur结点进行左旋parent结点进行右旋curRight结点成为树的新根// 左右双旋
void RotateLR(Node* parent) {
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
int bf_curRight = curRight->_balanceFactor;
// 旋转
RotateL(parent->_left);
RotateR(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curRight == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else if (bf_curRight == 1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = -1;
curRight->_balanceFactor = 0;
} else if (bf_curRight == -1) {
parent->_balanceFactor = 1;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else
assert(false);
}
右左双旋可以看做是左右双旋的镜像操作，二者可以看作是一个对称的关系。当插入节点在不平衡节点的右子树的左边时，可以记作右左型 (RL 型)，此时采用右左双旋的方法去调整平衡，即先对不平衡节点的右子树进行一次右单旋，之后再对不平衡节点为根的子树进行一次左单旋。
右左双旋的过程以及平衡因子的更新：
关键操作：
cur结点进行右旋parent结点进行左旋curLeft结点成为树的新根// 右左双旋 parent 的平衡因子为 2 或 -2
void RotateRL(Node* parent) {
Node* curNode = parent->_right;
Node* curLeft = curNode->_left;
int bf_curLeft = curLeft->_balanceFactor;
// 旋转
RotateR(parent->_right);
RotateL(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curLeft == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == 1) {
parent->_balanceFactor = -1;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == -1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 1;
curLeft->_balanceFactor = 0;
} else
assert(false);
}
parent，确定挂左还是挂右parent 的 左 or 右 子树，并维护 parent 指针_balacnFactor），反映子树高度变化public:
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// _root 不为空时，二叉搜索树的逻辑
Node* parent = nullptr;
Node* curNode = _root;
// 先找空，找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
}
// 搜索树中不允许有重复的值 对于已有值，不插入
else
return false;
}
// while 循环结束后，代表找到了可以插入的位置
// 找到位置了，但父节点不知道 新结点比自己大还是比自己小
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first) {
parent->_left = curNode;
} else {
parent->_right = curNode;
}
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作
// 控制平衡 ...
// 插入后，先更新平衡因子
// 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
while (parent) {
// 更新平衡因子
if (curNode == parent->_left)
--parent->_balanceFactor;
else // if (curNode == parent->_right)
++parent->_balanceFactor;
// 当前 parent 结点更新完了，判断是否还需要再往上更新
// 处理平衡因子更新后有三种情况
// 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转 结束循环
if (parent->_balanceFactor == 0) {
break;
}
// 情况二 parent 所在子树高度变了，继续往上更新
else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
curNode = parent;
parent = parent->_parent;
}
// 情况三 当前子树不平衡了，需要旋转
else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
// 左单旋'右子树右高'的一种情况
// 2 1 newNode 排成直线，单纯的右边高，进行 左单旋
// 2 -> 右高，1 -> 右高，右右 左单旋
if (parent->_balanceFactor == 2 && curNode->_balanceFactor == 1) {
RotateL(parent);
}
// -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋
// -2 -> 左高，-1 -> 左高，左左 右单旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == -1) {
RotateR(parent);
}
// 2 -1 newNode 排成折线 右左双旋
else if (parent->_balanceFactor == 2 && curNode->_balanceFactor == -1) {
RotateRL(parent);
}
// -2 1 newNode 排成折线 左右双旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == 1) {
RotateLR(parent);
} else {
assert(false);
}
// 旋转后，让这棵树平衡，且降低了这棵树的高度，
// 旋转后 就无需再更新平衡因子了，可以跳出循环
break;
} else {
assert(false); // 平衡因子不是 0 1 -1 2 -2 直接报错
}
}
return true;
}
AVL 树的删除操作这里不做重点讲解，这个操作会比插入稍复杂一些，但核心思路依然是走正常的二叉搜索树的删除操作 + 更新平衡因子 + 失衡时进行旋转
只不过与二叉搜索树删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
具体实现可参考《算法导论》或《数据结构 - 用面向对象方法与 C++ 描述》殷人昆版
求树的高度思路如下：
public:
int Height(Node* root) {
if (root == nullptr)
return 0;
// 分别求左右子树的高度
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 左右子树中 高度更大的那个 + 1
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
abs(rightHeight - leftHeight) < 2 &&
_IsBalance(root->_left) && _IsBalance(root->_right);public:
// 判断是否是 AVL 树
bool isBalance() {
return _IsBalance(_root);
}
private:
bool _IsBalance(Node* root) {
if (root == nullptr)
return true;
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 加一层保障
if (rightHeight - leftHeight != root->_balanceFactor) {
cout << "平衡因子异常：" << root->_kv.first << "->" << root->_balanceFactor << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
20000000 个随机数测试void test() {
const int N = 20000000;
vector<int> v;
v.reserve(N);
srand(time(0));
AVLTree<int, int> t;
for (size_t i = 0; i < N; ++i)
v.push_back(rand());
for (auto e : v)
t.insert(make_pair(e, e));
cout << t.isBalance() << endl;
}
int main() {
test();
return 0;
}
#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; // 插入结点后，需要更新平衡因子，有了_parent，可以很方便的找父节点
// 平衡因子，用于判断当前子树 有没有出现不平衡的问题
int _balanceFactor; // balance factor 平衡因子
// Node 的构造函数
AVLTreeNode(const pair<K, V>& kv) :_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_balanceFactor(0) // 新结点 初始的平衡因子为 0
{}
// 我们使用 平衡因子 = 右子树的高度 - 左子树的高度
// AVL 树的实现不是一定需要平衡因子，也可以动态的计算高度来判断
// 使用平衡因子实现只是其中一种方式
};
// 左右子树高度之差的绝对值 小于等于 1 (-1 0 1)
template<class K,class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
private:
AVLTreeNode<K, V>* _root = nullptr;
public:
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// _root 不为空时，二叉搜索树的逻辑
Node* parent = nullptr;
Node* curNode = _root;
// 先找空，找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
}
// 搜索树中不允许有重复的值 对于已有值，不插入
else
return false;
}
// while 循环结束后，代表找到了可以插入的位置
// 找到位置了，但父节点不知道 新结点比自己大还是比自己小
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first) {
parent->_left = curNode;
} else {
parent->_right = curNode;
}
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作
// 控制平衡 ...
// 插入后，先更新平衡因子
// 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
while (parent) {
// 更新平衡因子
if (curNode == parent->_left)
--parent->_balanceFactor;
else // if (curNode == parent->_right)
++parent->_balanceFactor;
// 当前 parent 结点更新完了，判断是否还需要再往上更新
// 处理平衡因子更新后有三种情况
// 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转 结束循环
if (parent->_balanceFactor == 0) {
break;
}
// 情况二 parent 所在子树高度变了，继续往上更新
else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
curNode = parent;
parent = parent->_parent;
}
// 情况三 当前子树不平衡了，需要旋转
else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
// 左单旋'右子树右高'的一种情况
// 2 1 newNode 排成直线，单纯的右边高，进行 左单旋
// 2 -> 右高，1 -> 右高，右右 左单旋
if (parent->_balanceFactor == 2 && curNode->_balanceFactor == 1) {
RotateL(parent);
}
// -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋
// -2 -> 左高，-1 -> 左高，左左 右单旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == -1) {
RotateR(parent);
}
// 2 -1 newNode 排成折线 右左双旋
else if (parent->_balanceFactor == 2 && curNode->_balanceFactor == -1) {
RotateRL(parent);
}
// -2 1 newNode 排成折线 左右双旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == 1) {
RotateLR(parent);
} else {
assert(false);
}
// 旋转后，让这棵树平衡，且降低了这棵树的高度，
// 旋转后 就无需再更新平衡因子了，可以跳出循环
break;
} else {
assert(false); // 平衡因子不是 0 1 -1 2 -2 直接报错
}
}
return true;
}
// 判断是否是 AVL 树
bool isBalance() {
return _IsBalance(_root);
}
private:
bool _IsBalance(Node* root) {
if (root == nullptr)
return true;
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 加一层保障
if (rightHeight - leftHeight != root->_balanceFactor) {
cout << "平衡因子异常：" << root->_kv.first << "->" << root->_balanceFactor << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
int Height(Node* root) {
if (root == nullptr)
return 0;
// 分别求左右子树的高度
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 左右子树中 高度更大的那个 + 1
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 左单旋 复习版
void RotateL_review(Node* parent) {
if (parent == nullptr || parent->_right == nullptr)
return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left;
parent->_right = curLeft;
if (curLeft) // curLeft 可能为空
curLeft->_parent = parent;
// parent 可能是根节点，也可能是一颗子树
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 先立新根
// 这里不知道 parent 是 ppNode 的左 还是右
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 再挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
parent->_balanceFactor = curNode->_balanceFactor = 0;
}
// 左单旋 2 1 newNode 练成线，单纯的右边高
void RotateL(Node* parent) {
if (parent == nullptr || parent->_right == nullptr)
return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left; // curLeft 有可能为空
// 先处理 curNode 的 left 结点，curLeft 有可能是空
parent->_right = curLeft;
if (curLeft)
curLeft->_parent = parent;
// 再处理 curNode 结点
// parent 有可能是根节点，也有可能是子树的根节点
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
parent->_balanceFactor = curNode->_balanceFactor = 0;
}
// 右单旋 -2 -1 newNode 连成线，单纯的左边高
void RotateR(Node* parent) {
// parent 为空 或 curNode 为空的情况
if (parent == nullptr || parent->_left == nullptr)
return;
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
// 把 curNode 的 right 给给 parent 的 left
parent->_left = curRight;
if (curRight)
curRight->_parent = parent;
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
curNode->_right = parent;
parent->_parent = curNode;
} else {
Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
curNode->_right = parent;
parent->_parent = curNode;
}
curNode->_balanceFactor = parent->_balanceFactor = 0;
}
// 右左双旋 parent 的平衡因子为 2 或 -2
void RotateRL(Node* parent) {
Node* curNode = parent->_right;
Node* curLeft = curNode->_left;
int bf_curLeft = curLeft->_balanceFactor;
// 旋转
RotateR(parent->_right);
RotateL(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curLeft == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == 1) {
parent->_balanceFactor = -1;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == -1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 1;
curLeft->_balanceFactor = 0;
} else
assert(false);
}
// 左右双旋
void RotateLR(Node* parent) {
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
int bf_curRight = curRight->_balanceFactor;
// 旋转
RotateL(parent->_left);
RotateR(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curRight == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else if (bf_curRight == 1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = -1;
curRight->_balanceFactor = 0;
} else if (bf_curRight == -1) {
parent->_balanceFactor = 1;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else
assert(false);
}
};
从最初的二叉搜索树到 AVL 树，我们一步步地走完了'从失衡到平衡'的进化历程。 AVL 树通过平衡因子 + 旋转操作巧妙地在插入、删除之间保持树的高度稳定，让查找性能始终维持在对数级别。
它是现代平衡树结构（如红黑树、Treap、B 树等）的理论基石，也让我们深刻理解了'以空间换时间'、'以维护换性能'的设计哲学。 虽然 AVL 树在插入删除时的维护成本略高，但在查找密集的场景中，它的稳定性与高效性仍然无可替代。
希望这篇文章能帮助你彻底理解平衡二叉树的核心思想，为你后续深入学习红黑树、STL map/set 底层实现打下坚实的基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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