AVL

AVL 树（以发明者 Adelson-Velsky 和 Landis 命名）是计算机科学中第一种自平衡二叉搜索树。

它在 BST 的基础上增加了一个硬性条件：任何节点的两个子树的高度差（平衡因子）最多为 1。

---

1. 核心概念：平衡因子 (Balance Factor)

对于 AVL 树中的任何节点 $N$，其平衡因子定义为：

$$BF(N) = Height(LeftSubtree) - Height(RightSubtree)$$

• $BF = 0$：左右完全平衡。
• $BF = 1$ 或 $-1$：轻微倾斜，但仍被视为平衡。
• $BF > 1$ 或 $< -1$：失去了平衡，需要通过旋转来修复。

---

2. 四种旋转方式

当我们在 AVL 树中插入或删除节点导致失衡时，会根据失衡的形态采取四种不同的旋转操作：

1. 左左型 (LL) -> 右旋 (Right Rotation)

插入点位于左子树的左侧。

2. 右右型 (RR) -> 左旋 (Left Rotation)

插入点位于右子树的右侧。

3. 左右型 (LR) -> 先左旋再右旋

插入点位于左子树的右侧。先对左子树进行左旋，变成 LL 型，再进行一次右旋。

4. 右左型 (RL) -> 先右旋再左旋

插入点位于右子树的左侧。先对右子树进行右旋，变成 RR 型，再进行一次左旋。

---

3. AVL 树的 C++ 实现

AVL 树的代码比普通 BST 复杂，因为每次插入后都需要更新高度并回溯检查平衡。

C++

#include <iostream>
#include <algorithm>using namespace std;struct Node {int val;int height; // 记录高度以计算平衡因子Node *left, *right;Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};class AVLTree {
public:Node* root = nullptr;// 获取高度的辅助函数int getHeight(Node* n) { return n ? n->height : 0; }// 计算平衡因子int getBalance(Node* n) { return n ? getHeight(n->left) - getHeight(n->right) : 0; }// 右旋转 (LL)Node* rotateRight(Node* y) {Node* x = y->left;Node* T2 = x->right;x->right = y;y->left = T2;y->height = max(getHeight(y->left), getHeight(y->right)) + 1;x->height = max(getHeight(x->left), getHeight(x->right)) + 1;return x;}// 左旋转 (RR)Node* rotateLeft(Node* x) {Node* y = x->right;Node* T2 = y->left;y->left = x;x->right = T2;x->height = max(getHeight(x->left), getHeight(x->right)) + 1;y->height = max(getHeight(y->left), getHeight(y->right)) + 1;return y;}// 递归插入Node* insert(Node* node, int val) {if (!node) return new Node(val);if (val < node->val) node->left = insert(node->left, val);else if (val > node->val) node->right = insert(node->right, val);else return node; // 不允许重复值// 1. 更新当前节点高度node->height = 1 + max(getHeight(node->left), getHeight(node->right));// 2. 获取平衡因子并检查是否失衡int balance = getBalance(node);// LL 情况if (balance > 1 && val < node->left->val) return rotateRight(node);// RR 情况if (balance < -1 && val > node->right->val) return rotateLeft(node);// LR 情况if (balance > 1 && val > node->left->val) {node->left = rotateLeft(node->left);return rotateRight(node);}// RL 情况if (balance < -1 && val < node->right->val) {node->right = rotateRight(node->right);return rotateLeft(node);}return node;}void inorder(Node* n) {if (!n) return;inorder(n->left);cout << n->val << " ";inorder(n->right);}
};

---

4. AVL 树 vs 红黑树 (Red-Black Tree)

在实际应用中，你可能经常听到这两者的对比：

特性	AVL 树	红黑树
平衡程度	严格平衡 (高度差 $\le 1$)	弱平衡 (最长路径不超最短两倍)
查找性能	更好 (因为树更矮)	稍逊
插入/删除性能	较慢 (可能涉及多次旋转)	更好 (旋转次数少)
适用场景	查找频繁、插入删除少的场景	插入删除频繁的场景 (如 C++ STL, Java HashMap)