自平衡二叉搜索树

AVL树——一种自平衡搜索二叉树

核心目标

解决普通搜索二叉树再操作时退化成链表，导致查询、删除插入等操作的时间复杂度由O(log n)退化到O(n)的问题。AVL树通过自动维护树的高度平衡来确保最坏情况下操作的时间复杂度仍然是O(log n)

概念

平衡因子

定义：对于一个节点node，其平衡因子等于左子树的高度减去右子树的高度
关键性质：再一个AVL树中，每个节点的平衡因子只能是-1，0，1三个值之一
意义：BF直观地反映了该节点左右子树的高度差。BF=1表示左子树比右子树高一层；BF=0表示两子树等高；BF=-1表示右子树比左子树高一层。限制|BF| <=1就保证了局部的高度平衡。

高度

定义：树中一个节点的高度（Height）是指从该节点到其子树中最远叶子节点的最长路径上的边数
约定
- 空树的高度定义为-1
- 单个叶子节点的高度定义为0

AVL树的递归定义

基础：一颗空的二叉树是高度平衡的
递归步骤：一棵非空的二叉树T，以其左子树T_L和右子树T_R作为子树，是AVL树当且仅当：
- T_L是AVL树
- T_R是AVL树
- |height(T_L) - height(T_R)| <= 1
简单地说：当插入或删除破坏平衡时（检测到某个节点的|BF|=2），需要根据不平衡节点（A）、导致问题的子树方向以及问题节点（通常是新插入或删除位置附近的节点）的BF来决定执行哪种旋转。

四种基本旋转操作

1. LL型旋转（左左型，右旋转）

场景：不平衡节点A的BF = 2，且A的左子树B的BF = 1（或0）
操作：将B提升为新的根，A成为B的右子树，B的原右子树成为A的左子树
示意图：

1
2
3
4
5


    A(BF=2)           B
   /                 / \
  B(BF=1)     →     C   A
 /                     /
C                     D

2. RR型旋转（右右型，左旋转）

场景：不平衡节点A的BF = -2，且A的右子树B的BF = -1（或0）
操作：将B提升为新的根，A成为B的左子树，B的原左子树成为A的右子树
示意图：

1
2
3
4
5


A(BF=-2)              B
    \                / \
     B(BF=-1)   →   A   C
      \             \
       C             D

3. LR型旋转（左右型，先左旋后右旋）

场景：不平衡节点A的BF = 2，且A的左子树B的BF = -1
操作：
1. 对B进行左旋转（RR旋转）
2. 对A进行右旋转（LL旋转）
示意图：

1
2
3
4
5


    A(BF=2)        A           C
   /              /           / \
  B(BF=-1)  →    C      →    B   A
   \            /
    C          B

4. RL型旋转（右左型，先右旋后左旋）

场景：不平衡节点A的BF = -2，且A的右子树B的BF = 1
操作：
1. 对B进行右旋转（LL旋转）
2. 对A进行左旋转（RR旋转）
示意图：

1
2
3
4
5


A(BF=-2)           A               C
    \               \             / \
     B(BF=1)   →     C      →    A   B
    /                 \
   C                   B

AVL树的插入操作

插入步骤

标准BST插入：按照二叉搜索树的规则插入新节点
回溯更新高度：从插入位置向上回溯，更新每个祖先节点的高度
检查平衡性：计算每个节点的平衡因子
执行旋转：如果发现不平衡（|BF| = 2），根据情况执行相应的旋转操作

时间复杂度

查找位置：O(log n)
旋转操作：O(1)
总体：O(log n)

AVL树的删除操作

删除步骤

标准BST删除：按照二叉搜索树的规则删除节点
- 叶子节点：直接删除
- 只有一个子树：用子树替换
- 有两个子树：用中序后继（或前驱）替换
回溯更新高度：从删除位置向上回溯，更新每个祖先节点的高度
检查平衡性：计算每个节点的平衡因子
执行旋转：如果发现不平衡，执行相应的旋转操作

时间复杂度

查找节点：O(log n)
删除操作：O(1)
旋转操作：O(1)
总体：O(log n)

AVL树的性质与优势

关键性质

高度保证：对于n个节点的AVL树，树高h满足：log₂(n+1) ≤ h ≤ 1.44log₂(n+2)
平衡性：任何节点的两个子树高度差最多为1
操作复杂度：查找、插入、删除操作都是O(log n)

优势

稳定的性能：保证最坏情况下仍有良好的时间复杂度
自动维护：无需手动调整，自动保持平衡状态
适用范围广：适合频繁查找、插入、删除的应用场景

劣势

空间开销：需要存储额外的高度或平衡因子信息
旋转开销：插入和删除时可能需要进行旋转操作
实现复杂：相比普通BST，实现较为复杂

应用场景

数据库索引：需要频繁查询和更新的索引结构
内存管理：操作系统中的虚拟内存管理
编译器：符号表的维护
图形学：空间数据结构的基础
网络路由：路由表的高效查找

与其他平衡树的比较

特性	AVL树	红黑树	B树
平衡性	严格平衡	近似平衡	多路平衡
查找性能	最优	良好	良好
插入/删除	较多旋转	较少旋转	复杂分裂/合并
应用场景	查找密集	通用场景	磁盘存储

Splay树（伸展树）————另一种自平衡的二叉搜索树

核心思想

Splay树的核心思想是“最近被访问过的元素很可能被再次访问），通过伸展操作调整高访问频率的节点的位置（靠近根节点）来提高访问速度

伸展操作(Splaying)

伸展：每次对树进行访问后，Splay树都会经过一系列旋转将被访问节点移动到靠近根节点的位置
目标
- 平衡
- 自适应
- 简化
操作
- zig/zag（单旋转）
  - 场景：p是根节点
  - 操作：进行一次标准BST单旋
    - 如果p是左节点，右旋
    - 如果p是右节点，左旋
  - 结果：p取代根节点
- zig—zig/zag-zag（单向双旋转）
  - 场景：p和p的父节点都是左子节点
  - 操作：p的父节点先进行一个标准BST单旋，p再进行一次标准BST单旋
  - 结果：p取代p的祖父节点
- zig-zag/zag-zig（异向双旋转）
  - 场景：x和p的方向相反
  - 操作：先对x和p进行一次旋转，再对x和g进行一次旋转
    - 结果：x移动到原来g的位置

摊还分析（Amortized Analysis）

定义与核心思想

定义：摊还分析是一种分析算法复杂度的技术，它不关注单次操作的最坏情况时间复杂度，而是分析一系列操作的平均时间复杂度
核心思想：某些操作虽然单次执行可能代价很高，但在一系列操作中，高代价操作的频率较低，因此平均下来每次操作的代价是可接受的
与平均情况分析的区别：
- 平均情况分析：基于输入的概率分布
- 摊还分析：基于操作序列，不依赖概率分布

三种摊还分析方法

1. 聚合方法（Aggregate Method）

基本思路：分析n次操作的总代价，然后除以n得到平均代价
步骤：
1. 证明n次操作的总代价为T(n)
2. 摊还代价 = T(n) / n
示例：栈的多重弹出操作

1
2
3
4
5
6
7


// MultiPop操作：弹出k个元素或栈为空
void MultiPop(Stack& s, int k) {
    while (!s.empty() && k > 0) {
        s.pop();
        k--;
    }
}

分析：

单次MultiPop最坏O(n)
n次操作中，每个元素最多被push一次，pop一次
总代价：O(n)
摊还代价：O(1)

2. 会计方法（Accounting Method）

基本思路：为每种操作分配摊还代价，建立"银行账户"概念
原则：
- 摊还代价 ≥ 实际代价（保证账户余额非负）
- 某些操作预付费用，为将来的高代价操作储备
示例：动态数组扩容

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class DynamicArray {
private:
    int* arr;
    int size;
    int capacity;
    
public:
    void push_back(int val) {
        if (size == capacity) {
            // 扩容：代价为O(size)
            int new_capacity = capacity * 2;
            int* new_arr = new int[new_capacity];
            for (int i = 0; i < size; i++) {
                new_arr[i] = arr[i];  // 复制代价
            }
            delete[] arr;
            arr = new_arr;
            capacity = new_capacity;
        }
        arr[size++] = val;  // 实际插入代价O(1)
    }
};

分析：

摊还代价设为3：插入(1) + 预付将来复制自己(1) + 预付将来复制之前元素(1)
扩容时使用预付的费用，无需额外支付
摊还代价：O(1)

3. 势能方法（Potential Method）

基本思路：定义势能函数Φ(Di)，表示数据结构在状态Di时的"势能"
摊还代价公式：
- ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁)
- 其中：ĉᵢ是摊还代价，cᵢ是实际代价
势能函数要求：
- Φ(D₀) = 0（初始状态势能为0）
- Φ(Dᵢ) ≥ 0（势能非负）
示例：二进制计数器递增

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class BinaryCounter {
private:
    vector<int> bits;  // bits[i] = 0 or 1
    
public:
    void increment() {
        int i = 0;
        while (i < bits.size() && bits[i] == 1) {
            bits[i] = 0;  // 翻转代价
            i++;
        } //全部置0
        if (i == bits.size()) {
            bits.push_back(1);
        } else {
            bits[i] = 1;
        }
        //置1和延伸
    }
};

分析：

势能函数：Φ(D) = 二进制表示中1的个数
设翻转了t个1，则：
- 实际代价：cᵢ = t + 1
- 势能变化：Φ(Dᵢ) - Φ(Dᵢ₋₁) = 1 - t
- 摊还代价：ĉᵢ = (t + 1) + (1 - t) = 2
摊还代价：O(1)

Splay树的摊还分析

访问定理（Access Theorem）

定理：在一棵有n个节点的Splay树中，从空树开始的m次操作的总时间复杂度为O(m log n + n log n)

势能函数定义

对于节点x，定义：
- size(x) = x子树中的节点数
- rank(x) = ⌊log₂ size(x)⌋
- 势能函数：Φ(T) = Σ rank(x) for all x in T

伸展操作的摊还分析

引理：伸展操作将节点x移动到根的摊还代价最多为3(rank(root) - rank(x)) + 1

证明思路：

Zig步骤（x的父节点是根）：
- 摊还代价 ≤ 1 + 3(rank’(x) - rank(x))
Zig-Zig步骤：
- 摊还代价 ≤ 3(rank’(x) - rank(x))
Zig-Zag步骤：
- 摊还代价 ≤ 2(rank’(x) - rank(x))

重要结论

单次操作：摊还代价为O(log n)
m次操作：总摊还代价为O(m log n)
动态最优性：Splay树在访问模式具有局部性时表现优异

摊还分析的应用场景

1. 数据结构操作

动态数组：插入操作的摊还复杂度
哈希表：带扩容的插入操作
堆：斐波那契堆的decrease-key操作

2. 算法分析

并查集：路径压缩的摊还分析
最小生成树：Kruskal算法中的并查集操作
图算法：某些最短路径算法

3. 实际系统

内存管理：垃圾回收的摊还代价
数据库：B+树的分裂和合并操作
编译器：词法分析器的缓冲区管理

摊还分析与Splay树的优势

自适应性：频繁访问的节点自动上移
简单实现：相比AVL树，实现更简单
空间效率：不需要存储额外的平衡信息
缓存友好：局部性原理的体现

实际应用中的考虑

访问模式：如果访问完全随机，Splay树优势不明显
最坏情况：单次操作可能需要O(n)时间
实际性能：在具有局部性的应用中表现优异

摊还分析的局限性

不保证单次操作的性能：某些关键实时系统可能不适用
分析复杂：相比最坏情况分析，证明更复杂
依赖操作序列：分析结果依赖于具体的操作模式

总结

摊还分析是理解Splay树等自适应数据结构性能的关键工具。它告诉我们：

Splay树虽然单次操作可能较慢，但长期表现优异
通过势能方法可以严格证明其O(log n)的摊还复杂度
在具有访问局部性的应用中，Splay树是优秀的选择