Menu
CoddyTech
开始学习

AVL 树

最后更新

AVL 树是一种自平衡的二叉搜索树。它的用法和普通二叉搜索树（BST）一样，但每次插入后，它都会检查每个祖先节点的平衡因子，也就是左右子树的高度差。如果某个节点失去平衡（高度差大于 1），它就会通过旋转恢复平衡。点击上方的“播放”，观察数值依次插入，以及树如何通过旋转恢复原状。

因为 AVL 树从不允许自己明显倾斜，它能保证树高为 O(log n)，所以查找、插入和删除始终是 O(log n)，即使面对会让普通 BST 退化的有序输入也是如此。代价是每次插入时额外的旋转和高度维护。

时间和空间复杂度

操作复杂度说明
查找O(log n)树高始终约为 1.44 log n
插入O(log n)外加 O(1) 次旋转
删除O(log n)外加 O(log n) 次旋转
空间O(n)每个节点一个高度字段

四种旋转情况

情况失衡位置修复方法
LL 型（左左）左子节点的左侧过重一次右旋
RR 型（右右）右子节点的右侧过重一次左旋
LR 型（左右）左子节点的右侧过重先左旋，再右旋
RL 型（右左）右子节点的左侧过重先右旋，再左旋

示例演算

逐个插入 [10, 20, 30, 40, 50, 25]：

步骤结构操作
插入 1010第一个节点成为根节点，树是平衡的
插入 2010(_, 20)放在 10 的右边，仍然平衡
插入 3020(10, 30)10 处出现 RR 型失衡，一次左旋把 20 提升为根节点
插入 4020(10, 30(_, 40))放在 30 的右边，所有平衡因子都在 ±1 以内
插入 5020(10, 40(30, 50))30 处出现 RR 型失衡，在 30 处左旋，把 40 提升上来
插入 2530(20(10, 25), 40(_, 50))20 处出现 RL 型失衡：先对 40 的子树右旋，再对 20 左旋

什么时候使用 AVL 树

适合使用的情况不适合使用的情况
查找次数远多于插入，并且你希望树高尽可能低插入和删除占多数，额外的旋转和再平衡开销比红黑树更大
即使面对恶意构造或有序的输入，也需要保证最坏情况 O(log n)普通哈希表就够用，你不需要有序遍历或范围查询
需要有序操作：中序遍历、前驱和后继、范围查询数据量很小，普通 BST 或有序数组更简单，速度也够快
数据可能已经有序到达，这会让不平衡的 BST 退化成链表内存非常紧张，承担不起每个节点额外的高度字段

AVL Tree 代码

简洁、可运行的 AVL Tree 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。

AVL Tree 的 Python 代码

Python
1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6        self.height = 17
8
9def height(node):10    return node.height if node else 011
12
13def update(node):14    node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18    x = y.left19    y.left = x.right20    x.right = y21    update(y)22    update(x)23    return x24
25
26def rotate_left(x):27    y = x.right28    x.right = y.left29    y.left = x30    update(x)31    update(y)32    return y33
34
35def insert(node, key):36    if node is None:37        return Node(key)38    if key < node.key:39        node.left = insert(node.left, key)40    else:41        node.right = insert(node.right, key)42    update(node)43    balance = height(node.left) - height(node.right)44    # Four imbalance cases: LL, RR, LR, RL45    if balance > 1 and key < node.left.key:46        return rotate_right(node)47    if balance < -1 and key > node.right.key:48        return rotate_left(node)49    if balance > 1:50        node.left = rotate_left(node.left)51        return rotate_right(node)52    if balance < -1:53        node.right = rotate_right(node.right)54        return rotate_left(node)55    return node56
57
58def inorder(node):59    if node is None:60        return []61    return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66    root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)
在 Python 在线编辑器中运行这段代码

AVL 树常见问题

AVL 树中的平衡因子是什么？

节点的平衡因子等于它左子树的高度减去右子树的高度。AVL 树让每个节点的平衡因子保持在 -1、0 或 +1；如果一次插入使它超出这个范围，就通过旋转恢复平衡。

AVL 树和红黑树有什么区别？
两者都是自平衡的二叉搜索树，操作都是 O(log n)。AVL 树的平衡更严格，所以查找稍快，但插入和删除时可能需要更多旋转。红黑树的平衡更宽松，旋转次数更少，这就是很多标准库用它来实现 map 和 set 的原因。
为什么用 AVL 树而不用普通二叉搜索树？
如果数值按顺序到达，普通 BST 会形成一条倾斜的链，操作退化为 O(n)。AVL 树通过旋转保持平衡，无论插入顺序如何，都能保证树高和操作为 O(log n)。
做数据库索引，AVL 树比红黑树更好吗？

这取决于工作负载。AVL 树的平衡更严格，所以在读多写少、希望查找路径尽可能短时更有优势。但大多数数据库和语言库选择红黑树（或 B 树），因为在写入频繁的场景下它们再平衡所需的旋转更少，而插入和删除频繁时这一点更重要。

AVL 树插入一个值需要几次旋转？
插入一个值后，最多只需要一次旋转（单旋转或分两步的双旋转）就能让树恢复平衡。这是因为一次插入最多让某棵子树的高度增加 1，所以只需在最低的失衡祖先处修复一次即可。删除则不同：随着再平衡向根节点传播，最多可能需要 O(log n) 次旋转。
每次旋转后都需要更新节点高度吗？

需要。一个常见的 bug 是指针旋转得没问题，却忘了重新计算相关两个节点的高度。每次旋转后，必须先更新被降级的节点的高度，再更新被提升的节点，因为被提升节点的高度取决于它的新子节点。跳过这一步会留下过时的平衡因子，破坏之后的再平衡判断。

相关资源

更多可视化

Coddy 编程语言插图

在 Coddy 掌握算法

开始