AVL 平衡二叉树 可视化交互式动画版

AVL 是一种自平衡二叉搜索树 (BST)，其中任何节点的左子树和右子树的高度之差不能大于 1。

关键点

• 它是高度平衡树
• 它是一个二叉搜索树
• 它是一棵二叉树，其中左子树和右子树的高度差几乎为1
• 高度是从根到叶的最大深度

AVL树的特点：

• 它遵循二叉搜索树的一般属性。
• 树的每个子树都是平衡的，即左右子树的高度差最多为1。
• 当插入新节点时，树会自行平衡。 因此插入操作比较耗时

AVL树的应用：

• 大多数内存中的集合和字典都是使用 AVL 树存储的。
• 数据库应用程序中，插入和删除不太常见，但需要频繁的数据查找，因此也经常使用 AVL 树。
• 除了数据库应用程序之外，它还用于需要更好搜索的其他应用程序。
• 有序关联容器（集合、多重集合、映射和多重映射）的大多数 STL 实现都使用红黑树而不是 AVL 树。

AVL树的优点：

• AVL树可以自我平衡。
• 它还提供更快的搜索操作。
• AVL 树还具有不同类型旋转的平衡能力
• 比其他树（例如二叉树）更好的搜索时间复杂度。
• 高度不得大于 log(N)，其中 N 是树中的节点总数。

AVL树的缺点：

• AVL树很难实现
• AVL 树对于某些操作具有较高的常数因子。

最大和最小节点数

最大节点数 = 2 ^H+1  – 1

高度 H 的最小节点数 = 高度 (H-1) 的最小节点数 + 高度 (H-2) 的最小节点数 + 1

其中 H(0)=1

              H(1)=2

你还能读什么？

• AVL树简介
• 插入 AVL 树
• AVL 树中的删除

AVL 树 定义为自平衡 二叉搜索树 (BST)，其中任何节点的左子树和右子树的高度之差不能大于 1。

任何节点的左子树和右子树的高度之差称为 该节点的 平衡因子。

AVL 树以其发明者 Georgy Adelson-Velsky 和 ​​Evgenii Landis 的名字命名，他们在 1962 年的论文“信息组织算法”中发表了该树。

AVL 树的示例：

上面的树是AVL，因为每个节点的左右子树的高度差小于或等于1。

AVL 树上的操作：

• 插入
• 删除
• 搜索 [与BST中的搜索类似]

旋转 AVL 树中的子树：

AVL 树可以通过以下四种方式之一进行旋转以保持自身平衡：

左旋转 ：

当一个节点被添加到右子树的右子树中时，如果树失去平衡，我们会进行一次左旋转。

右旋转 ：

如果将一个节点添加到左子树的左子树上，AVL树可能会失去平衡，我们做一次右旋转。

左右旋转 ：

左右旋转是在执行右旋转之后发生第一次左旋转的组合。

左右旋转 ：

左右旋转是在执行左旋转之后发生第一次右旋转的组合。

AVL树的应用：

1. 它用于索引数据库中的大量记录并在其中进行有效搜索。
2. 对于所有类型的内存集合（包括集合和字典），都会使用 AVL 树。
3. 数据库应用程序，其中插入和删除不太常见，但需要频繁的数据查找
4. 需要优化搜索的软件。
5. 应用于企业领域和故事情节游戏。

AVL树的优点：

1. AVL 树可以自我平衡。
2. 肯定没有歪斜。
3. 它提供比红黑树更快的查找
4. 与二叉树等其他树相比，搜索时间复杂度更高。
5. 高度不能超过 log(N)，其中 N 是树中节点的总数。

AVL树的缺点：

1. 实施起来很困难。
2. 对于某些操作来说，它具有较高的常数因子。
3. 与红黑树相比，使用较少。
4. 由于其相当严格的平衡，AVL 树随着执行更多的旋转而提供复杂的插入和删除操作。
5. 采取更多处理以实现平衡。

相关文章：

• 二叉搜索树简介 - 数据结构和算法教程
• 插入 AVL 树
• AVL 树中的删除