AVL树

Kira 收录于类别数据结构与算法

2021-03-25 2023-03-20 约 1749 字预计阅读 4 分钟

警告

本文最后更新于 2023-03-20，文中内容可能已过时。

背景

二叉搜索树的主要问题是不平衡。在最坏的情况下，它会退变为链表，使查询时间变为 $O(n)$。

AVL树（Adelson-Velsky 和00 Landis）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，通过平衡因子使任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 $O(\log_{}{n})$。

在AVL树中，每个节点都会记录其左子树高度与右子树高度之差，也就是所谓的平衡因子（balance factor），平衡因子的值只能是-1、0或1。当树中每个节点的平衡因子都满足这个约束时，即可保证树的平衡。

平衡因子是AVL树中用来检查树的平衡条件的标准，因为在AVL树中，任何节点的左右子树高度差都不能超过1。一旦平衡因子的绝对值大于1，就说明树的平衡被破坏了，需要通过旋转操作来恢复树的平衡，从而保证AVL树的性质。

在AVL树中，平衡因子可以在O(1)时间内计算得到，并且在插入和删除等操作中需要动态更新。通过保持树的平衡，AVL树可以高效地支持各种搜索、插入和删除操作。

AVL 树可以通过跟踪每个节点的平衡因子来维持平衡。如果节点的平衡因子不在 [−1,1] 范围内，则 AVL 树可以执行旋转。每次平衡因子被破坏时，这些旋转涉及在不平衡节点的子树中切换节点的位置。

AVL树的插入操作可能会导致树失去平衡，因此需要进行旋转操作来重新平衡。AVL插入操作包含以下四种情况：

在AVL树左边的左子树中插入节点，破坏了左子树的平衡。需要对树进行右旋操作，把节点提升到原来不平衡节点的位置。

在AVL树右边的右子树中插入节点，破坏了右子树的平衡。需要对树进行左旋操作，把节点提升到原来不平衡节点的位置。

在AVL树左边的右子树中插入节点，破坏了左子树的平衡。需要进行两次操作：首先对节点的左子树进行左旋操作，然后对节点进行右旋操作，把节点提升到原来不平衡节点的位置。

AVL树的删除操作包含以下四种情况：

当要删除的节点没有子节点时，直接将其删除即可。
当要删除的节点只有一个子节点时，将其子节点提升到要删除的节点位置即可。
当要删除的节点有两个子节点时，找到其右子树的最小节点或左子树的最大节点，将其值复制到要删除的节点，然后删除这个最小或最大节点即可。
当要删除的节点有左右子树时，代价相对较大，需要进行旋转操作，具体有两种情况：
1. 左右子树高度差绝对值小于等于1。此时将左子树或右子树的最大节点提升到要删除的节点的位置，然后进行旋转操作即可。
2. 左右子树高度差绝对值大于1。此时先找到其右子树的最小节点或左子树的最大节点，然后将此节点的值复制到要删除的节点，最后删除这个最小或最大节点。此时要对其右子树或左子树进行旋转操作，使得树重新平衡。

需要注意的是，在进行节点的删除后可能会影响到其它节点的平衡状态，因此在删除操作时，要递归地检查，并进行相应的旋转操作，直到树恢复平衡为止。

AVL树的优点：

查询和修改操作的时间复杂度都是$O(\log_{}{n})$。因为AVL树始终保持着平衡，所以其高度始终是O(log n)级别的，每次操作的最多步数也是$O(\log_{}{n})$级别的，因而在大数据集合中实现的效率相当高。
AVL树在适当的情况下比红黑树更快。AVL树的查询和修改操作可能略微比红黑树更快，因为它需要进行的旋转操作少于红黑树。
网络优化。AVL树通常用于路由表这样的场合中。此类应用需要$O(\log_{}{n})$时间查找遍历，因此AVL结构更优。

AVL树的缺点：

插入和删除操作需要对树进行旋转操作，使得每个节点的平衡因子得到更新，这样的操作代价较高，在插入和删除操作次数很多时，性能会受到影响。
AVL树是一种自平衡二叉搜索树，它需要存储每个节点的平衡因子，这样会增加额外的内存消耗。对于大数据集合，原本很小的存储开销也可能成为显而易见的问题。
AVL树的实现比较困难。AVL树需要以平衡为优先考虑，因此实现难度相对于其他二叉搜索树较高，需要维护平衡因子、进行回溯计算等。这就需要实现者具有较高的代码编写和调试技能，需要大量的时间和精力。