好的，这是一个关于 平衡二叉树（AVL Tree） 的详细介绍。AVL树是一种自平衡的二叉搜索树（BST），由 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年提出。它的核心思想是通过维护每个节点的 平衡因子 来确保树的高度保持在 $O(\\log n)$ 级别，从而保证搜索、插入和删除操作的时间复杂度都为 $O(\\log n)$。
1. 平衡因子
AVL树的关键在于 平衡因子（Balance Factor, BF）。对于树中的任意节点 $N$，其平衡因子定义为： $$ \\text{BF}(N) = \\text{height}(\\text{left subtree}) – \\text{height}(\\text{right subtree}) $$ 在AVL树中，要求每个节点的平衡因子必须满足： $$ |\\text{BF}(N)| \\leq 1 $$ 即左子树和右子树的高度差最多为1。
2. 失衡与旋转
当插入或删除节点导致某个节点的平衡因子绝对值大于1时，树就 失衡 了。为了恢复平衡，AVL树使用四种基本的旋转操作：
- 左旋（Left Rotation）：处理右右（RR）失衡
- 右旋（Right Rotation）：处理左左（LL）失衡
- 先左后右（LR Rotation）：处理左右（LR）失衡
- 先右后左（RL Rotation）：处理右左（RL）失衡
旋转操作详解
- RR 失衡与左旋：当节点A的BF < -1（右子树比左子树高超过1），且其右子节点B的BF <= 0（右子树更高或等高）时，对A进行左旋。
- 效果：B成为新的根节点，A成为B的左子节点，B原来的左子树（如果有）成为A的右子树。
- 平衡恢复：调整后，A和B的BF都变为0或接近0。
- LL 失衡与右旋：当节点A的BF > 1（左子树比右子树高超过1），且其左子节点B的BF >= 0（左子树更高或等高）时，对A进行右旋。
- 效果：B成为新的根节点，A成为B的右子节点，B原来的右子树（如果有）成为A的左子树。
- 平衡恢复：调整后，A和B的BF都变为0或接近0。
- LR 失衡与先左后右旋：当节点A的BF > 1，但其左子节点B的BF < 0（B的右子树更高）时，说明失衡发生在A的左孩子的右子树上。
- 步骤：先对B进行左旋（将B的右孩子C提升为B的位置），将其转换为LL情况；再对A进行右旋。
- RL 失衡与先右后左旋：当节点A的BF < -1，但其右子节点B的BF > 0（B的左子树更高）时，说明失衡发生在A的右孩子的左子树上。
- 步骤：先对B进行右旋（将B的左孩子C提升为B的位置），将其转换为RR情况；再对A进行左旋。
3. 插入操作
AVL树的插入操作在普通BST插入的基础上增加了平衡维护：
4. 删除操作
删除操作比插入更复杂，因为删除节点可能引起多个祖先节点失衡：
5. C++ 实现框架
以下是一个简化的AVL树节点的C++实现框架（未包含完整旋转函数）：
template <typename T>
class AVLTreeNode {
public:
T key;
AVLTreeNode<T> *left;
AVLTreeNode<T> *right;
int height; // 节点高度
AVLTreeNode(T k) : key(k), left(nullptr), right(nullptr), height(1) {}
};
template <typename T>
class AVLTree {
private:
AVLTreeNode<T> *root;
// 获取节点高度（处理空指针）
int getHeight(AVLTreeNode<T> *node) {
return node ? node->height : 0;
}
// 计算平衡因子
int getBalanceFactor(AVLTreeNode<T> *node) {
return node ? getHeight(node->left) – getHeight(node->right) : 0;
}
// 更新节点高度（基于左右子树高度）
void updateHeight(AVLTreeNode<T> *node) {
if (node) {
node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
}
}
// 旋转函数 (示例：右旋)
AVLTreeNode<T>* rightRotate(AVLTreeNode<T> *y) {
AVLTreeNode<T> *x = y->left;
AVLTreeNode<T> *T2 = x->right;
// 执行旋转
x->right = y;
y->left = T2;
// 更新高度 (必须先更新y，再更新x，因为y在x的子树中)
updateHeight(y);
updateHeight(x);
return x; // 返回新的根节点
}
// 左旋、LR旋转、RL旋转函数实现类似…
// 插入辅助函数（递归）
AVLTreeNode<T>* insert(AVLTreeNode<T> *node, T key) {
// 1. 标准BST插入
if (!node) return new AVLTreeNode<T>(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // 重复键，不插入
// 2. 更新当前节点高度
updateHeight(node);
// 3. 获取平衡因子，检查是否失衡
int bf = getBalanceFactor(node);
// 4. 根据失衡类型进行旋转
// LL Case
if (bf > 1 && key < node->left->key)
return rightRotate(node);
// RR Case
if (bf < -1 && key > node->right->key)
return leftRotate(node);
// LR Case
if (bf > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL Case
if (bf < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
// 不需要旋转，直接返回当前节点
return node;
}
// 删除辅助函数（递归）实现类似，但更复杂…
public:
AVLTree() : root(nullptr) {}
void insert(T key) {
root = insert(root, key);
}
// 其他成员函数（删除、查找、遍历等）…
};
https://www.zhihu.com/zvideo/2010226933791744738
https://www.zhihu.com/zvideo/2010226743395510262
https://www.zhihu.com/zvideo/2010226632464540191
https://www.zhihu.com/zvideo/2010226933791744738
https://www.zhihu.com/zvideo/2010226743395510262
https://www.zhihu.com/zvideo/2010226632464540191
总结
AVL树通过严格的平衡条件（$|\\text{BF}| \\leq 1$）和四种旋转操作，保证了树的高度近似平衡，从而提供了高效的 $O(\\log n)$ 操作。虽然插入和删除时需要额外的旋转开销来维护平衡，但对于查找密集型应用或需要稳定性能的场景，AVL树是一个可靠的选择。理解其平衡因子和旋转机制是掌握该数据结构的关键。
