一.AVL树的基本概念
AVL树是一种特殊的二叉树，AVL树是一颗空树或者具备以下性质：左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是通过控制高度差来去调节数据的。
二.平衡因子的介绍
我们通过平衡因子来确定AVL树是否平衡。
平衡因子=右子树高度-左子树高度，右边的数据大，而左边的数据小并且存在正负我们的比较是取其绝对值。
对于一个标准的AVL树来说，平衡因子只能是-1、1、0。平衡因子就像是风向标，来判断AVL树是否平衡，也主要利用平衡因子来判断AVL树的高度关系。
三.AVL树的结构设计
AVL树的效率比较高，效率严格控制在O（log n)级别。最差情况要远远优于二叉搜索树的做差情况。
AVL树的节点存储需要左右指针、父结点指针以及平衡因子来完整的组成。
template<class k,class v>
class AVLTree {
//类型别名：简化节点指针的使用
typedef AVLTreeNode<k, v> Node;
public:
//构造基本的框架
AVLTree():_root(nullptr){}
//插入、查找等基本操作
bool Insert(const pair < k, v)& kv);
Node* Find(const k& key);
bool IsBalanceTree();
//用于验证其性质
void InOrder() {
_InOrder(_root);
cout << "完整" << endl;
}
private:
Node* _root;
void _InOrder(Node* root) {
if (root == nullptr)return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
int _Height(NOde* root);
bool _IsBalanceTree(Node* root);
//重点：旋转操作
void RotateR(Node* parent);//右单旋
void RotateL(Node* parent);//左单旋
void RotateLR(Node* parent);//左右双旋
void RotateRL(Node* parent);//右左双旋
};
这就是AVL树的一个基本结构。
四.AVL树的插入
bool AVLTree<K, V>::Insert(const pair<K, V>& kv) {
// 情况1：树为空，直接创建根节点
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// 情况2：树非空，查找插入位置
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 {
// 键值已存在，插入失败（AVL树不允许重复键）
return false;
}
}
// 找到插入位置，创建新节点并建立父子关系
cur = new Node(kv);
if (parent->_kv.first < kv.first) {
// 新节点为父节点的右孩子
parent->_right = cur;
} else {
// 新节点为父节点的左孩子
parent->_left = cur;
}
// 建立父节点指针（关键：用于后续回溯）
cur->_parent = parent;
// 后续步骤：更新平衡因子并调整平衡（见3.3节）
// …
}
我们也可以通过图像来更好地理解：
我们还要注意的是对平衡因子的更新。
// 接3.2节代码，继续在Insert函数中实现
// 步骤2：回溯更新平衡因子
while (parent) {
// 1. 更新当前父节点的平衡因子
if (cur == parent->_left) {
// 新节点是父节点的左孩子，父节点bf–
parent->_bf–;
} else {
// 新节点是父节点的右孩子，父节点bf++
parent->_bf++;
}
// 2. 判断是否需要继续更新或调整平衡
if (parent->_bf == 0) {
// 情况1：bf变为0，子树高度不变，停止更新
break;
} else if (parent->_bf == 1 || parent->_bf == -1) {
// 情况2：bf变为±1，子树高度增加1，继续向上更新
cur = parent;
parent = parent->_parent;
} else if (parent->_bf == 2 || parent->_bf == -2) {
// 情况3：bf变为±2，子树失衡，需要旋转调整
// 根据失衡类型选择对应的旋转操作
if (parent->_bf == 2) {
// 右子树过高，需左单旋或右左双旋
if (cur->_bf == 1) {
// 右子树的右子树过高（RR型），左单旋
RotateL(parent);
} else {
// 右子树的左子树过高（RL型），右左双旋
RotateRL(parent);
}
} else { // parent->_bf == -2
// 左子树过高，需右单旋或左右双旋
if (cur->_bf == -1) {
// 左子树的左子树过高（LL型），右单旋
RotateR(parent);
} else {
// 左子树的右子树过高（LR型），左右双旋
RotateLR(parent);
}
}
// 旋转后子树高度恢复，无需继续向上更新，插入结束
break;
} else {
// 异常情况：bf绝对值超过2（代码逻辑错误）
assert(false);
}
}
return true;
五.AVL树的旋转
AVL树的旋转也是最重要和最有难度的内容。主要分为右单旋、左单旋、左右双旋、右左双旋。
parent (bf=-2)
/
subL (bf=-1)
/
newNode
如果出现这样的情况，就无法满足AVL树的条件了，但是可以通过旋转来实现。
void AVLTree<K, V>::RotateR(Node* parent) {
// 1. 保存关键节点
Node* subL = parent->_left; // parent的左孩子（即将成为新根）
Node* subLR = subL->_right; // subL的右子树（即将成为parent的左子树）
Node* parentParent = parent->_parent; // parent的父节点（上层节点）
// 2. 调整subLR与parent的关系
parent->_left = subLR;
if (subLR != nullptr) {
subLR->_parent = parent;
}
// 3. 调整parent与subL的关系
subL->_right = parent;
parent->_parent = subL;
// 4. 调整subL与上层节点的关系
if (parentParent == nullptr) {
// 情况1：parent是原根节点，subL成为新根
_root = subL;
subL->_parent = nullptr;
} else {
// 情况2：parent是上层节点的左/右孩子，subL替换其位置
if (parentParent->_left == parent) {
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
// 5. 重置平衡因子（旋转后subL和parent均平衡）
parent->_bf = 0;
subL->_bf = 0;
}
左单旋也是基本相同：
void AVLTree<K, V>::RotateL(Node* parent) {
// 1. 保存关键节点
Node* subR = parent->_right; // parent的右孩子（即将成为新根）
Node* subRL = subR->_left; // subR的左子树（即将成为parent的右子树）
Node* parentParent = parent->_parent; // parent的父节点
// 2. 调整subRL与parent的关系
parent->_right = subRL;
if (subRL != nullptr) {
subRL->_parent = parent;
}
// 3. 调整parent与subR的关系
subR->_left = parent;
parent->_parent = subR;
// 4. 调整subR与上层节点的关系
if (parentParent == nullptr) {
// 情况1：parent是原根节点，subR成为新根
_root = subR;
subR->_parent = nullptr;
} else {
// 情况2：parent是上层节点的左/右孩子，subR替换其位置
if (parentParent->_left == parent) {
parentParent->_left = subR;
} else {
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
// 5. 重置平衡因子
parent->_bf = 0;
subR->_bf = 0;
}
左右双旋：
void AVLTree<K, V>::RotateLR(Node* parent) {
// 1. 保存关键节点
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 记录subLR的平衡因子（用于后续重置）
int bf = subLR->_bf;
// 2. 第一步：以subL为旋转点进行左单旋（转为LL型）
RotateL(subL);
// 3. 第二步：以parent为旋转点进行右单旋（恢复平衡）
RotateR(parent);
// 4. 根据subLR的原始bf重置平衡因子
if (bf == 0) {
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
} else if (bf == -1) {
// subLR的左子树插入节点，parent的右子树高度增加
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
} else if (bf == 1) {
// subLR的右子树插入节点，subL的左子树高度增加
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
} else {
assert(false); // 异常情况
}
}
右左双旋：
void AVLTree<K, V>::RotateRL(Node* parent) {
// 1. 保存关键节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 记录subRL的平衡因子
int bf = subRL->_bf;
// 2. 第一步：以subR为旋转点进行右单旋（转为RR型）
RotateR(subR);
// 3. 第二步：以parent为旋转点进行左单旋（恢复平衡）
RotateL(parent);
// 4. 根据subRL的原始bf重置平衡因子
if (bf == 0) {
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
} else if (bf == 1) {
// subRL的右子树插入节点，parent的左子树高度增加
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
} else if (bf == -1) {
// subRL的左子树插入节点，subR的右子树高度增加
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
} else {
assert(false); // 异常情况
}
}
AVL树的难度主要体现在旋转和对其平衡的控制！
