当然，下面是对 AVL 树（平衡二叉搜索树） 的详细讲解，适合用作入门到进阶的数据结构学习内容。
🌲 数据结构【AVL树】——自平衡的二叉搜索树详解
📚 目录
- AVL 树简介
- 为什么需要 AVL 树？
- AVL 树的性质
- 旋转操作（LL、RR、LR、RL）详解
- AVL 插入操作过程
- AVL 删除操作简述
- Python 示例代码
- 应用场景
- 常见面试题与考点
- 延伸阅读
1️⃣ AVL 树简介
AVL 树是一种自平衡的二叉搜索树（BST）。它在每次插入或删除节点后，自动通过旋转保持平衡，从而确保查询操作的时间复杂度为 O(log n)。
2️⃣ 为什么需要 AVL 树？
普通的二叉搜索树（BST）在最坏情况下可能退化为链表，导致搜索效率降为 O(n)：
举例：
插入顺序：1 → 2 → 3 → 4 → 5
BST 结构：单边树
查询 5 需要 5 步，效率极低
❗ 解决办法：每次插入后检查树的平衡性，并进行必要的旋转维护平衡。
3️⃣ AVL 树的性质
- 每个节点记录一个“平衡因子（Balance Factor）”：
bf = height(left subtree) - height(right subtree) - 对每个节点：
bf ∈ {-1, 0, 1}
超出范围则说明不平衡，需要旋转恢复。 - AVL 树的高度 h ≈ 1.44 × log₂(n)，保证 查询效率稳定在 O(log n)。
4️⃣ 旋转操作详解
🔁 失衡类型与旋转方式
| 类型 | 插入方向 | 恢复操作 |
|---|---|---|
| LL | 左子树的左子树 | 右旋 |
| RR | 右子树的右子树 | 左旋 |
| LR | 左子树的右子树 | 左旋再右旋 |
| RL | 右子树的左子树 | 右旋再左旋 |
✅ 示例：右旋（LL）
A B
/ / \
B ==> 右旋 C A
/
C
✅ 示例：左旋（RR）
A B
\ / \
B ==> 左旋 A C
\
C
5️⃣ AVL 插入操作步骤
- 像普通 BST 一样插入；
- 回溯路径上 更新每个节点的高度；
- 判断是否失衡（平衡因子 ∉ {-1, 0, 1}）；
- 根据 LL/RR/LR/RL 类型进行旋转；
- 返回新的根节点；
6️⃣ AVL 删除操作简述
删除比插入更复杂：
- 正常 BST 删除；
- 回溯更新高度；
- 若某节点失衡，根据子树高度进行相应旋转；
- 注意多次旋转可能连续发生；
7️⃣ Python AVL 树插入实现（简化版）
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def get_height(self, root):
return root.height if root else 0
def get_balance(self, root):
return self.get_height(root.left) - self.get_height(root.right) if root else 0
def right_rotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1
return x
def left_rotate(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = max(self.get_height(x.left), self.get_height(x.right)) + 1
y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
return y
def insert(self, root, key):
if not root:
return TreeNode(key)
elif key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
# 更新高度
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
# 检查平衡因子
balance = self.get_balance(root)
# 四种失衡情况
if balance > 1 and key < root.left.key:
return self.right_rotate(root) # LL
if balance < -1 and key > root.right.key:
return self.left_rotate(root) # RR
if balance > 1 and key > root.left.key:
root.left = self.left_rotate(root.left) # LR
return self.right_rotate(root)
if balance < -1 and key < root.right.key:
root.right = self.right_rotate(root.right) # RL
return self.left_rotate(root)
return root
8️⃣ AVL 树应用场景
| 应用场景 | 原因 |
|---|---|
| 数据库索引（部分） | 查询频繁，需维持高度平衡 |
| 词典、字符串搜索系统 | 保持搜索性能，支持频繁插入/删除 |
| 内存索引结构 | 实时性强，使用 AVL 能保持响应稳定 |
9️⃣ 常见面试题与考点
- 设计一个支持插入、删除、查找的平衡搜索结构（可用 AVL）；
- 手写 AVL 插入与旋转过程；
- AVL 和 红黑树 的对比（AVL 查询快、红黑树插入删除快）；
- 如何在 AVL 中查找第 k 小的元素？
🔍 10. 延伸阅读
- 《算法导论》第 13 章：AVL 与红黑树
- VisuAlgo AVL 动画演示：https://visualgo.net/zh/bst
- GeeksForGeeks AVL Tree Tutorial
发表回复