数据结构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. 实际应用

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