前言
map/set容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，有了AVL树。
（一）AVL树介绍
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis
在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
（1）AVL树的概念
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
-它的左右子树都是AVL树
-左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
平衡因子=右子树的高度-左子树的高度。
平衡因子是一个存在于二叉树中的变量
（实现AVL树不一定需要引入平衡因子，可以计算右子树高度和左子树高度差进行平衡比较）
1.新增结点在左，parent平衡因子减减
2、新增在右，parent平衡因子加加
3、更新后parent平衡因子==0，说明parent所在的子树的高度不变，不会再影响祖先，不用再继续沿着到root的路径往上更新
4、更新后parent平衡因子=1 or -1，说明parent所在的子树的高度变化，会再影响祖先，需要继续沿着到root的路径往上更新
5、更新后parent平衡因子==2or-2，说明parent所在的子树的高度变化且不平衡，对parent所在子树进行旋转，让他平衡
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 log(n),搜索时间复杂度O(logN)。
（二）AVL树的实现
这里我通过引入平衡因子来进行AVL树的旋转操作。
（1）AVL树节点的定义
数据存放在pair中：
pair是一种STL中的类，该类将一对不同类型的值(T1和T2)耦合在一起。单个值可以通过它的公共成员first和second来访问。
key和value：
key是存取时进行比较大小的标准，val是key对应的值。他们是一组键值对pair{key，val}，key和val可以是相同的类型，也可以是不同的。
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K, V>& kv = pair<K,V>())
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
AVLTreeNode<K, V>* _left; // 该节点的左孩子
AVLTreeNode<K, V>* _right; // 该节点的右孩子
AVLTreeNode<K, V>* _parent; // 该节点的双亲
pair<K, V> _kv; //数据存在与pair中
int _bf; // 节点的平衡因子 balance factor
};（2）AVL树的旋转
AVL树的旋转总结来说一共右四种情况，分别是：左单旋，右单旋，左右双旋，右左双旋。
只有当平衡因子 = 2 或者 -2 时，才需要进行旋转平衡）
（i）左单旋（新节点插入较高右子树的右侧）
当插入节点在c的节点上时，进行左旋。（不能在a或者b中，这样不是左单旋）
parent的平衡因子为2，cur的平衡因子为1。
如何进行左单旋的旋转操作？
i.将parent的right指向curleft，curleft的父亲改为parent（需要判断curleft是否为空）。
ii. 将parent的parent记录下来(Pparent)，因为parent上面可能还有节点。
iii. cur的left指向parent，然后将parent的parent指向cur。
iiii. 判断Pparent是否为空，若为空则将cur的parent指向空。
若Pparent不为空，则需要判断原先的parent是Pparent的左孩子还是右孩子，将Pparent的左孩子（或者右孩子）指向cur。
iiiii. 最后要修改cur和 parent的 平衡因子 为 0；
代码如下：
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
Node* Pparent = parent->_parent;
cur->_left = parent;
parent->_parent = cur;
if (Pparent == nullptr)
{
cur->_parent = nullptr;
}
else //父亲的父亲不是空
{
if (Pparent->_kv.first < cur->_kv.first)
{
Pparent->_right = cur;
}
else
{
Pparent->_left = cur;
}
cur->_parent = Pparent;
}
cur->_bf = parent->_bf = 0;
}（ii）右单旋 （新节点插入较高左子树的左侧）
当插入节点在a的节点上时，进行右旋。（不能在b或者c中，这样不是左单旋）
parent的平衡因子为-2，cur的平衡因子为-1。
如何进行右单旋的旋转操作？
i.将parent的left指向curright，curright的父亲改为parent（需要判断curright是否为空）。
ii. 将parent的parent记录下来(Pparent)，因为parent上面可能还有节点。
iii. cur的right指向parent，然后将parent的parent指向cur。
iiii. 判断Pparent是否为空，若为空则将cur的parent指向空。
若Pparent不为空，则需要判断原先的parent是Pparent的左孩子还是右孩子，将Pparent的左孩子（或者右孩子）指向cur。
iiiii. 最后要修改cur和 parent的 平衡因子 为 0；
代码如下：
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright)
{
curright->_parent = parent;
}
Node* Pparent = parent->_parent;
cur->_right = parent;
parent->_parent = cur;
if (Pparent == nullptr)
{
cur->_parent = nullptr;
}
else
{
if (Pparent->_kv.first < cur->_kv.first)
{
Pparent->_right = cur;
}
else
{
Pparent->_left = cur;
}
cur->_parent = Pparent;
}
cur->_bf = parent->_bf = 0;
}（iii） 右左双旋（新节点插入较高右子树的左侧）
当插入节点在b或c的节点上时，进行右左旋。
parent的平衡因子为2，cur的平衡因子为-1。
如何进行右左双旋的旋转操作？
i.对cur所在树进行右旋操作。
ii. 再对parent所在树进行左旋操作。
需要注意的是我的左右旋操作都会将平衡因子改为 0， 所以需要将行旋转后需要修改平衡因子：
（1）若插入的地方为c时，即curleft的平衡因子为 1 时，由于右旋操作，已经将c连接到了cur的左孩子上，（此时cur的左右孩子高度相同）所以此时cur平衡因子为0，而b 经过左旋被连接到了parent的右孩子上（此时parent的左孩子高度比右孩子高1），此时parent的平衡因子为-1。
（2）若插入的地方为b时，同理可知，此时parent的平衡因子为 0，cur的平衡因子为1。
代码如下：
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf; //记录bf的值
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
curleft = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
}
（iiii） 左右双旋（新节点插入较高左子树的右侧）
当插入节点在b或c的节点上时，进行左右旋。parent的平衡因子为-2，cur的平衡因子为1。
如何进行左右双旋的旋转操作？
i.对cur所在树进行左旋操作。
ii. 再对parent所在树进行右旋操作。
需要注意的是我的左右旋操作都会将平衡因子改为 0， 所以需要将行旋转后需要修改平衡因子：
（1）若插入的地方为c时，即curright的平衡因子为 1 时，由于左旋操作b连接到了cur的右孩子上，（此时cur的左孩子高度比右孩子高1）所以此时cur平衡因子为-1，而c 经过右旋被连接到了parent的左孩子上（此时parent的左右孩子高度相同），此时parent的平衡因子为0。
（2）若插入的地方为b时，同理可知，此时parent的平衡因子为 1，cur的平衡因子为0。
代码如下：
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curright = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
}（3） AVL树的插入
AVL树的插入过程分为两个步骤：
（1）与普通二叉树相同的插入操作；
（2）调整节点的平衡因子，根据平衡因子，判断是否要进行旋转操作。
代码如下：
bool Insert(const pair<K, V>& kv)
{
//如果_root 等于空
if (_root == nullptr)
{
_root = new Node(kv);
}
Node* parent = nullptr;
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;
}
}
cur = new Node(kv);
//将插入结点的值进行连接
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
cur->_parent = parent;
//平衡因子，满足AVL树的性质
while (parent) //当到空时，平衡退出（根结点的父亲是空）
{
if (cur == parent->_right)
{
parent->_bf++;
}
else if (cur == parent->_left)
{
parent->_bf--;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
if (parent->_bf == 2 && cur->_bf == 1) //左旋
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1) //右旋
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1) //先右再左
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) //先左后右
{
RotateLR(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}（三） AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1. 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确
// AVL树的验证 bool IsAVLTree() { return _IsAVLTree(_root); } size_t _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; } // 根据AVL树的概念验证Root是否为有效的AVL树 bool _IsAVLTree(Node* root) { if (root == nullptr) return true; int LeftHeight = _Height(root->_left); int RightHeight = _Height(root->_right); if (RightHeight - LeftHeight != root->_bf) { cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl; return false; } return abs(LeftHeight - RightHeight) <= 1 && _IsAVLTree(root->_left) && _IsAVLTree(root->_right); }
（四）AVL树总结
1. 基本特性
AVL树是一种严格平衡的二叉搜索树，通过维护每个节点的平衡因子（左子树高度与右子树高度之差）确保树的高度平衡。其平衡条件要求所有节点的平衡因子绝对值不超过1。
2. 时间复杂度
- 插入、删除、查找操作：时间复杂度均为O(logn)。
由于AVL树始终保持高度平衡，树的高度严格满足h≤1.44log2(n+1)h≤1.44log2(n+1)，这使得其查询效率接近最优。- 平衡操作：插入或删除节点后可能需要通过旋转操作恢复平衡，单次旋转的时间复杂度为O(1)，但最坏情况下可能需要从插入点回溯到根节点调整平衡因子，因此平衡操作的总体时间复杂度仍为O(logn)。
3. 性能优缺点
- 优点：
- 严格平衡保证查询效率极高，适合读多写少的场景（如数据库索引）。
- 时间复杂度稳定，无极端退化情况。
- 缺点：
- 插入和删除时需频繁调整平衡因子和旋转，写操作开销较大。
- 与红黑树相比，平衡操作更复杂，可能影响实际性能