平衡二叉树（AVL Tree）

一句话说明

AVL 树是在二叉搜索树上额外要求“左右高度差不能超过 1”，用更严格的平衡换来更稳定的查找效率。

先理解它为什么出现

普通 二叉搜索树 的问题是：

• 平均很快
• 但最坏可能退化成链表

AVL 的解决思路就是：

• 插入和删除之后主动调整
• 让整棵树始终保持比较矮

所以它的核心目标不是“好看”，而是“查找别退化”。

AVL 最关键的定义

对任意节点，都要求：

|height(left) - height(right)| <= 1

这个差值也叫平衡因子。

balance factor = 左子树高度 - 右子树高度

只要某个节点平衡因子绝对值大于 1，就说明这里失衡了，要旋转修复。

为什么它比普通 BST 查找更稳

因为 AVL 的高度被严格控制住了。
树越矮，搜索路径越短，所以查找复杂度稳定在：

O(log n)

代价是：

• 插入后可能要旋转
• 删除后也可能要一路向上修复

Go 代码：节点定义

type AVLNode struct {
    Val    int
    Height int
    Left   *AVLNode
    Right  *AVLNode
}

Go 代码：辅助函数

func height(node *AVLNode) int {
    if node == nil {
        return 0
    }
    return node.Height
}
 
func updateHeight(node *AVLNode) {
    node.Height = max(height(node.Left), height(node.Right)) + 1
}
 
func balanceFactor(node *AVLNode) int {
    return height(node.Left) - height(node.Right)
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

旋转才是 AVL 的核心动作

失衡之后，本质上就做两件事：

• 单旋
• 双旋

你不用一开始就记住所有图形，先记住 4 种名字就够了：

• LL：右旋
• RR：左旋
• LR：先左旋左子树，再右旋根
• RL：先右旋右子树，再左旋根

Go 代码：左右旋

func rightRotate(y *AVLNode) *AVLNode {
    x := y.Left
    t2 := x.Right
 
    x.Right = y
    y.Left = t2
 
    updateHeight(y)
    updateHeight(x)
    return x
}
 
func leftRotate(x *AVLNode) *AVLNode {
    y := x.Right
    t2 := y.Left
 
    y.Left = x
    x.Right = t2
 
    updateHeight(x)
    updateHeight(y)
    return y
}

Go 代码：插入并维护平衡

func Insert(root *AVLNode, val int) *AVLNode {
    if root == nil {
        return &AVLNode{
            Val:    val,
            Height: 1,
        }
    }
 
    if val < root.Val {
        root.Left = Insert(root.Left, val)
    } else if val > root.Val {
        root.Right = Insert(root.Right, val)
    } else {
        return root
    }
 
    updateHeight(root)
    balance := balanceFactor(root)
 
    if balance > 1 && val < root.Left.Val {
        return rightRotate(root)
    }
    if balance < -1 && val > root.Right.Val {
        return leftRotate(root)
    }
    if balance > 1 && val > root.Left.Val {
        root.Left = leftRotate(root.Left)
        return rightRotate(root)
    }
    if balance < -1 && val < root.Right.Val {
        root.Right = rightRotate(root.Right)
        return leftRotate(root)
    }
 
    return root
}

这 4 种失衡到底怎么判断

LL

• 当前节点左边太高
• 新节点插在左孩子的左边

直接右旋。

RR

• 当前节点右边太高
• 新节点插在右孩子的右边

直接左旋。

LR

• 当前节点左边太高
• 新节点插在左孩子的右边

先把左孩子左旋，转成 LL，再整体右旋。

RL

• 当前节点右边太高
• 新节点插在右孩子的左边

先把右孩子右旋，转成 RR，再整体左旋。

删除为什么比插入更麻烦

插入时，失衡位置通常比较集中。
删除时，某个节点删掉后，影响可能一路向上传播，所以修复可能不止一次。

因此做题里常见情况是：

• 插入模板要求会写
• 删除模板知道思路即可

如果不是手写平衡树题，很多场景其实不会让你完整实现 AVL 删除。

Go 代码：判断一棵树是否平衡

这是更常见的 LeetCode 题型，不要求你手写真 AVL 树，但思路和 AVL 定义一致。

func IsBalanced(root *TreeNode) bool {
    return heightOrFail(root) != -1
}
 
func heightOrFail(node *TreeNode) int {
    if node == nil {
        return 0
    }
 
    left := heightOrFail(node.Left)
    if left == -1 {
        return -1
    }
 
    right := heightOrFail(node.Right)
    if right == -1 {
        return -1
    }
 
    if abs(left-right) > 1 {
        return -1
    }
 
    return max(left, right) + 1
}
 
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

AVL 和红黑树怎么理解差别

AVL

• 平衡更严格
• 查找路径更短
• 更新时可能做更多旋转

红黑树

• 平衡稍松
• 查找略逊一点
• 插入删除更偏工程友好

所以可以粗暴记成：

AVL 更偏“查找性能”
红黑树更偏“综合更新表现”

复杂度

操作	时间复杂度
查找	O(log n)
插入	O(log n)
删除	O(log n)

易错点

AVL 题最容易错的地方

• 旋转之后要先更新低层节点高度，再更新高层节点高度。
• 判断 LL / RR / LR / RL 时，不只是看当前节点失衡，还要看新值落在哪一侧。
• “平衡二叉树”题通常只是检查是否平衡，不等于让你实现完整 AVL 树。

经典题目

• 平衡二叉树 - LeetCode 110
• 将有序数组转换为二叉搜索树 - LeetCode 108
• 有序链表转换二叉搜索树 - LeetCode 109
• 手写支持插入的 AVL 树

相关主题

• 二叉搜索树：AVL 的基础。
• 红黑树：更常见的工程化平衡树。
• 二叉树：树结构入门基础。

---

返回：数据结构 | 算法学习导航