AVL 树详解
概念介绍
什么是 AVL 树?
AVL 树(Adelson-Velsky and Landis Tree)是一种自平衡二叉搜索树。它由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出。AVL 树在普通二叉搜索树的基础上增加了平衡条件,确保树始终保持近似平衡状态。
一棵 AVL 树要么是空树,要么满足以下性质:其左、右子树也都是 AVL 树,并且左、右子树的高度差的绝对值不超过 1。
基本性质
- 高度近似平衡:通过不断调整结构,保证左右子树高度差在允许范围内。插入或删除节点后,会通过旋转操作恢复平衡。
- 查找效率稳定:由于高度平衡,树的高度近似于 O(log n),查找时间复杂度稳定在 O(log n)。相比普通二叉搜索树在最坏情况下退化为链表(O(n)),AVL 树效率更高且稳定。
- 优缺点比较:优点是查找效率高;缺点是每次插入和删除都可能涉及旋转,计算开销略大。
为什么要求高度差不超过 1 而非为 0?
从理想状态看,高度差为 0 更平衡,但在特定节点数量下(如 2、4 等),最优高度差只能是 1。这是'绝对平衡'与'实现可行性'之间的权衡设计。
什么是平衡因子?
每个节点都有一个平衡因子(balance factor),其值等于该节点右子树的高度减去左子树的高度。因此,任何节点的平衡因子只能是 -1、0 或 1。它是判断树是否失衡的'风向标',通过判断平衡因子是否超出 [-1, 1] 范围可快速定位需要调整的节点。
基本操作
查找操作
查找逻辑与普通二叉搜索树相同。从根节点开始,根据键值大小决定向左或向右遍历,直到找到目标或到达空节点。时间复杂度为 O(log n)。
插入操作
AVL 树的插入 = 二叉搜索树插入 + 平衡修复。
- 空树处理:新节点直接作为根。
- 查找位置:按 BST 规则找到父节点。
- 挂载节点:连接新节点并更新父指针。
- 更新平衡因子:从插入点向上更新路径上所有节点的平衡因子。
- 平衡修复:若某节点平衡因子绝对值 ≥ 2,则进行旋转操作(单旋或双旋)恢复平衡。
*注:删除操作同样需要维护平衡,但因逻辑复杂且涉及更多边界情况,本节暂不展开,重点聚焦于插入与平衡维护机制。
旋转平衡
AVL 树通过四种旋转操作维护平衡:
- 右单旋:处理 LL 型失衡(左子树过高)。
- 左单旋:处理 RR 型失衡(右子树过高)。
- 左右双旋:处理 LR 型失衡。
- 右左双旋:处理 RL 型失衡。
单旋
右单旋(LL 型)
当某个节点的左子树高度比右子树大 2,且失衡由左子树的左子树插入导致时触发。 核心步骤:提升左子节点为新根,原左子节点的右子树挂接到原根节点的左子树,更新父子关系及平衡因子。
左单旋(RR 型)
当某个节点的右子树高度比左子树大 2,且失衡由右子树的右子树插入导致时触发。 核心步骤:提升右子节点为新根,原右子节点的左子树挂接到原根节点的右子树,更新父子关系及平衡因子。
双旋
左右双旋(LR 型)
当左子树高度比右子树大 2,但失衡由左子树的右子树插入导致时触发。需先对左子节点执行左单旋,再对当前节点执行右单旋。
右左双旋(RL 型)
当右子树高度比左子树大 2,但失衡由右子树的左子树插入导致时触发。需先对右子节点执行右单旋,再对当前节点执行左单旋。


