数据结构

平衡二叉树AVL

JACIN··9 分钟阅读

目录#

[[toc]]

概念#

  • 定义：任意结点的左、右子树高度差不超过 1。
  • 目的：保证查找、插入、删除的时间复杂度始终是 O(log n)。
  • 维护方式：插入或删除后，如果局部失衡，就通过旋转（单旋/双旋）来恢复平衡。
术语说明
AVL 树最早的自平衡二叉搜索树（Balanced Binary Search Tree）之一，由 Adelson-Velsky 和 Landis 提出。
平衡条件任意结点的左右子树高度差不超过 1。
平衡因子 (Balance Factor, BF)定义为BF=height(left)−height(right)，取值∈−1,0,1。定义为 BF = height(left) - height(right)，取值 ∈ {-1,0,1}。
高度从根到最深叶子结点的边数。

目的：保证查找、插入、删除等操作的时间复杂度都稳定在 O(log n)。

基本操作#

  • 和普通二叉搜索树(BST)相同：

    比根小 → 左子树；比根大 → 右子树。

  • 不需要额外旋转。

  • 时间复杂度：O(log n)

2.2 插入 (Insert)#

步骤：

  1. 按 BST 规则找到插入位置，新节点高度为 1。
  2. 自下而上回溯，更新各结点的高度和平衡因子。
  3. 如果某个结点失衡（|BF|>1），根据失衡类型做旋转恢复平衡。

四种失衡类型与旋转方式

失衡类型条件旋转
LL插入在失衡结点的左孩子的左子树右旋
RR插入在失衡结点的右孩子的右子树左旋
LR插入在失衡结点的左孩子的右子树先左后右（双旋）
RL插入在失衡结点的右孩子的左子树先右后左（双旋）

旋转只影响失衡结点附近的局部结构，时间复杂度 O(1)。

LL 型（Left-Left）

插入在失衡结点 X 的左孩子的左子树

python 
    X
   /
  Y
 /
Z  (新结点插在这里)
  • 插入点在 X 的左-左方向。
  • 解决：右旋一次即可。
python 
      Y
     / \
    Z   X

RR 型（Right-Right） 插入在 X 的右孩子的右子树。

python 
X
 \
  Y
   \
    Z  (新结点插在这里)
  • 插入点在 X 的右-右方向。
  • 解决：左旋一次即可。
python 
      Y
     / \
    X   Z

LR 型（Left-Right）

插入在X 的左孩子的右子树

python 
    X
   /
  Y
   \
    Z  (新结点插在这里)
  • 插入点在 X 的左-右方向。
  • 解决：先左旋 Y，再右旋 X（双旋）。
python 
   X            X             Z
  /     左旋    /    右旋    / \
 Y     =>    Z   =>    Y   X. Y
  \         /
   Z       Y

2.3 删除 (Delete)#

  1. 按 BST 规则删除：
    • 如果是叶子，直接删除。
    • 如果有一个孩子，用孩子替代。
    • 如果有两个孩子，用直接前驱或后继替代，然后删除对应叶子。
  2. 自下而上回溯，更新高度和平衡因子。
  3. 若失衡（|BF|>1），需要做旋转。
    • 可能一次删除导致多次回溯和多次旋转。

常见删除触发的旋转类型：

LL、RR、LR、RL，规则与插入类似，但可能在多层触发。

时间复杂度：O(log n)

应用例子与实践场景#

✅ 数据库索引的核心思想#

  • 数据库的 B 树 / B+ 树 是多路平衡树的变体。
  • 它们保证无论插入、删除还是查询，树高始终接近 log n，从而让磁盘读写次数恒定在 O(log n)。
  • 应用：MySQL 的 InnoDB 索引、PostgreSQL 的 B-Tree 索引、SQLite 的 B+Tree 文件格式。

尽管 AVL 是二叉树，但它的“始终保持高度对数级”的思想，是 B/B+ 树的直接理论基础。

任何需要动态有序 + 频繁增删

你每天用的数据库、操作系统、IDE，其核心数据结构里几乎都包含平衡树思想。

评论

还没有评论，来发第一个吧