数据结构13-平衡二叉树

平衡二叉树(Balanced Binary Tree),也称为AVL树(以发明者 Adelson-Velsky 和 Landis 命名),是一种高度平衡的二叉搜索树(BST)。它的核心目标是保证任意节点的左右子树高度差不超过 1,从而在最坏情况下仍能提供对数时间复杂度的查找、插入和删除操作。

以下是平衡二叉树的详细知识点:

折半查找的二叉判定树就是AVL树


1. 基本定义

平衡二叉树是满足以下条件的二叉搜索树:

  • 二叉搜索树性质:左子树所有节点的值小于根节点,右子树所有节点的值大于根节点。
  • 平衡条件:任意节点的左右子树高度差(平衡因子,BF)绝对值不超过 1。 BF=Height(Left Subtree)−Height(Right Subtree)BF = \text{Height(Left Subtree)} - \text{Height(Right Subtree)}BF=Height(Left Subtree)−Height(Right Subtree)

2. 平衡因子

  • 平衡因子可以是

    -1, 0, 1:

    • 0:左右子树高度相等。
    • 1:左子树高度比右子树高 1。
    • -1:右子树高度比左子树高 1。
  • 如果某个节点的平衡因子超出上述范围(即 |BF| > 1),需要进行旋转操作调整。


3. 常见操作

1. 插入操作

  1. 插入步骤
    • 按照二叉搜索树的规则插入新节点。
    • 回溯更新各个节点的高度和平衡因子。
    • 如果某个节点的平衡因子失衡(|BF| > 1),执行旋转操作。
  2. 旋转类型
    • 单旋转:
      • LL 型(左左失衡):右旋转。
      • RR 型(右右失衡):左旋转。
    • 双旋转:
      • LR 型(左右失衡):先左旋转,后右旋转。
      • RL 型(右左失衡):先右旋转,后左旋转。

2. 删除操作

  • 删除后可能导致某些节点失衡,同样需要更新高度并进行必要的旋转调整。

3. 查找操作

  • 查找操作与普通二叉搜索树相同,平均时间复杂度为 O(log⁡n)O(\log n)O(logn),最坏情况也为 O(log⁡n)O(\log n)O(logn)。

4. 旋转操作详解

右旋转(单旋转)

适用场景:LL 型失衡(左子树过高)。

  • 旋转后新的根节点为当前根节点的左子节点。
  • 操作步骤:
    1. 将当前根节点的左子节点提为新的根节点。
    2. 新根节点的右子树变成旧根节点的左子树。
    3. 旧根节点变为新根节点的右子节点。

左旋转(单旋转)

适用场景:RR 型失衡(右子树过高)。

  • 步骤与右旋转对称。

左-右旋转(双旋转)

适用场景:LR 型失衡(左子树的右子树过高)。

  • 操作步骤:
    1. 对当前根节点的左子节点执行左旋转。
    2. 对当前根节点执行右旋转。

右-左旋转(双旋转)

适用场景:RL 型失衡(右子树的左子树过高)。

  • 操作步骤:
    1. 对当前根节点的右子节点执行右旋转。
    2. 对当前根节点执行左旋转。

5. AVL 树的性质

  1. 平衡性
    • 保证每个节点的左右子树高度差不超过 1。
  2. 时间复杂度
    • 查找:O(log⁡n)O(\log n)O(logn)
    • 插入:O(log⁡n)O(\log n)O(logn)
    • 删除:O(log⁡n)O(\log n)O(logn)
  3. 空间复杂度
    • 通常为 O(n)O(n)O(n),用于存储节点信息。

6. AVL 树与其他平衡树的比较

特性AVL 树红黑树
平衡条件严格(BF 为 -1, 0, 1)较宽松(最长路径 ≤ 最短路径 2 倍)
插入/删除效率插入效率较低(需要多次旋转)插入效率较高(旋转次数少)
查找效率较高(树更平衡)较低
应用场景适用于频繁查找的场景适用于插入删除较频繁的场景

7. 实际应用

  • 数据库系统:例如实现索引结构。
  • 内存管理:如动态分区内存分配。
  • 搜索引擎:用于构建倒排索引。