以下是关于**数据结构之——平衡二叉树（AVL树）**的完整详解内容，适合学习与教学参考：

目录

  1. 什么是平衡二叉树
  2. 平衡因子与AVL树定义
  3. 插入操作与四种旋转
    • LL型旋转
    • RR型旋转
    • LR型旋转
    • RL型旋转
  4. 删除操作与再平衡
  5. 实现平衡二叉树（伪代码）
  6. 平衡二叉树的时间复杂度
  7. 应用场景
  8. AVL树与红黑树的对比
  9. 拓展知识：平衡二叉树的变种
  10. 小结

1. 什么是平衡二叉树

平衡二叉树（Balanced Binary Tree）是指左右子树的高度差不超过1的二叉查找树（BST）。其中最常见的是AVL树，它由两位苏联数学家Adelson-Velsky和Landis提出，因此得名。

2. 平衡因子与AVL树定义

每个节点的平衡因子（Balance Factor）= 左子树高度 – 右子树高度

  • AVL树要求每个节点的平衡因子只能是 -1、0、1。
  • 一旦插入或删除节点后出现不平衡（平衡因子超出范围），则需要通过旋转操作恢复平衡。

3. 插入操作与四种旋转

插入可能破坏平衡，我们需要在最小不平衡子树处进行旋转来恢复平衡。

LL型（右旋）：

        A
       /
      B
     /
    C

右旋以A为支点，使B上升为根节点。

RR型（左旋）：

    A
     \
      B
       \
        C

左旋以A为支点，使B上升为根节点。

LR型（先左后右旋）：

      A
     /
    B
     \
      C

先左旋B，再右旋A。

RL型（先右后左旋）：

    A
     \
      B
     /
    C

先右旋B，再左旋A。

4. 删除操作与再平衡

删除节点后也可能破坏平衡，类似插入：

  • 沿路径向上检查是否失衡。
  • 如果失衡，进行旋转操作。
  • 删除操作后可能要多次旋转才能恢复整体平衡。

5. 实现平衡二叉树（伪代码）

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    if not node:
        return 0
    return node.height

def get_balance(node):
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x

def rotate_left(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    node.height = 1 + max(get_height(node.left), get_height(node.right))
    balance = get_balance(node)

    if balance > 1 and key < node.left.key:  # LL
        return rotate_right(node)
    if balance < -1 and key > node.right.key:  # RR
        return rotate_left(node)
    if balance > 1 and key > node.left.key:  # LR
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1 and key < node.right.key:  # RL
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

6. 平衡二叉树的时间复杂度

  • 插入：O(log n)
  • 删除：O(log n)
  • 查找：O(log n)

因为AVL树始终保持平衡，所以操作效率优于普通二叉搜索树（BST）。

7. 应用场景

  • 数据库索引（如MySQL B+树就是变种）
  • 词典/集合实现（如Java的TreeMap）
  • 实时查找与频繁更新的数据结构（如内存数据库）

8. AVL树与红黑树对比

特性AVL树红黑树
平衡性严格平衡较松弛
插入/删除调整多（最多O(log n)次旋转）少（最多3次）
查找效率较高（更矮）略低
应用场景查找频繁插入删除频繁

9. 拓展知识：平衡二叉树的变种

  • 红黑树：平衡因子采用颜色（红/黑），较宽松，插入删除效率高。
  • Treap：结合二叉搜索树与堆的特性。
  • Splay树：最近使用的数据项会移动到树根。

10. 小结

平衡二叉树（AVL树）是数据结构中经典的高效查找结构之一，适合频繁查找的应用。虽然插入与删除比红黑树稍复杂，但其更高的查找效率使其在一些对查找性能极度敏感的场景下仍被广泛使用。