数据结构13-平衡二叉树
数据结构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. 插入操作
- 插入步骤:
- 按照二叉搜索树的规则插入新节点。
- 回溯更新各个节点的高度和平衡因子。
- 如果某个节点的平衡因子失衡(|BF| > 1),执行旋转操作。
- 旋转类型:
- 单旋转:
- LL 型(左左失衡):右旋转。
- RR 型(右右失衡):左旋转。
- 双旋转:
- LR 型(左右失衡):先左旋转,后右旋转。
- RL 型(右左失衡):先右旋转,后左旋转。
- 单旋转:
2. 删除操作
- 删除后可能导致某些节点失衡,同样需要更新高度并进行必要的旋转调整。
3. 查找操作
- 查找操作与普通二叉搜索树相同,平均时间复杂度为 O(logn)O(\log n)O(logn),最坏情况也为 O(logn)O(\log n)O(logn)。
4. 旋转操作详解
右旋转(单旋转)
适用场景:LL 型失衡(左子树过高)。
- 旋转后新的根节点为当前根节点的左子节点。
- 操作步骤:
- 将当前根节点的左子节点提为新的根节点。
- 新根节点的右子树变成旧根节点的左子树。
- 旧根节点变为新根节点的右子节点。
左旋转(单旋转)
适用场景:RR 型失衡(右子树过高)。
- 步骤与右旋转对称。
左-右旋转(双旋转)
适用场景:LR 型失衡(左子树的右子树过高)。
- 操作步骤:
- 对当前根节点的左子节点执行左旋转。
- 对当前根节点执行右旋转。
右-左旋转(双旋转)
适用场景:RL 型失衡(右子树的左子树过高)。
- 操作步骤:
- 对当前根节点的右子节点执行右旋转。
- 对当前根节点执行左旋转。
5. AVL 树的性质
- 平衡性
- 保证每个节点的左右子树高度差不超过 1。
- 时间复杂度
- 查找:O(logn)O(\log n)O(logn)
- 插入:O(logn)O(\log n)O(logn)
- 删除:O(logn)O(\log n)O(logn)
- 空间复杂度
- 通常为 O(n)O(n)O(n),用于存储节点信息。
6. AVL 树与其他平衡树的比较
特性 | AVL 树 | 红黑树 |
---|---|---|
平衡条件 | 严格(BF 为 -1, 0, 1) | 较宽松(最长路径 ≤ 最短路径 2 倍) |
插入/删除效率 | 插入效率较低(需要多次旋转) | 插入效率较高(旋转次数少) |
查找效率 | 较高(树更平衡) | 较低 |
应用场景 | 适用于频繁查找的场景 | 适用于插入删除较频繁的场景 |
7. 实际应用
- 数据库系统:例如实现索引结构。
- 内存管理:如动态分区内存分配。
- 搜索引擎:用于构建倒排索引。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 寻觅~流光!
评论