AVL 树的性质

1962 年，GM Adelson-Velsky 和 EM Landis 创建了 AVL 树。为了纪念创造者，这棵树被称为 AVL。

AVL 树的定义是高度平衡的二叉搜索树，其中每个节点都有一个平衡因子，该平衡因子是通过从左子树的高度中减去右子树的高度来确定的。

如果每个节点的平衡因子介于 -1 和 1 之间，则认为树是平衡的；否则，需要平衡树。

平衡因子

• 如果任何节点的平衡因子为 1，则左子树比右子树高一个级别。
• 平衡因子为零的任何节点都表示左子树和右子树的高度相等。
• 如果节点的平衡因子为负一，则左子树比右子树低一个级别。
• 下图展示了一棵 AVL 树。我们可以看到每个节点的平衡因子都在 -1 到 +1 之间。因此，这是 AVL 树的一个例子。
• 今天我们将讨论 AVL 树及其用途。BST 的最坏情况性能接近线性搜索算法，即 O (n)。我们无法实时预测实时数据中的数据模式和频率。因此，平衡当前 BST 的需求应运而生。
• AVL 树，代表 Adelson、Velski 和 Landis，是高度平衡的二叉搜索树。AVL 树确保左右子树的高度差不超过 1。这被称为平衡因子。
• 为了更好地理解平衡和不平衡树的区别，让我们看一些例子
  

• 由于上例中根节点的左右高度相同，我们可以看到第一棵树是平衡的。而另外两棵则不是这样，中间图中的树在节点左侧是倾斜的。类似地，最后一幅图右侧的树在根节点右侧是倾斜的，导致其不平衡。

为什么要使用 AVL 树？

大多数 BST 操作，包括搜索、最大值、最小值、插入、删除等，都需要 O(h) 时间，其中 h 是 BST 的高度。对于倾斜的二叉树，这些操作的成本可能会增加到 O(n)。如果我们确保在每次插入和删除后树的高度保持 O(log(n))，我们可以为所有这些操作提供 O(log(n)) 的上限。AVL 树的高度始终为 O(log(n))，其中 n 是树的节点数。

AVL 树上的操作

由于 AVL 树也是二叉搜索树，因此所有操作的执行方式与二叉搜索树中的操作相同。搜索和遍历不会导致 AVL 树属性的违反。然而，可能破坏此条件的动作是插入和删除；因此，需要对其进行审查。

• 插入
• 删除

AVL 树的插入

为了确保在每次插入后提供的树保持 AVL，我们必须在典型的 BST 插入过程中添加一些重新平衡。

以下两个简单的操作（键(左) 键(根) 键(右)）可以在不违反 BST 属性的情况下用于平衡 BST。

• 左旋
• 右旋

插入的步骤如下

• 设 w 为新添加的节点。
• 对 w 执行典型的 BST 插入。
• 通过从 w 开始向上移动来找到第一个失衡节点。假设 z 是初始失衡节点，y 是 z 的子节点，位于从 w 到 z 的路径上，x 是 z 的孙节点，位于上述路径上。
• 以适当的方向旋转以 z 为根的子树以重新平衡树。由于 x、y 和 z 可以有 4 种不同的排序方式，因此可能有 4 种潜在的场景需要解决。
• 四种潜在的配置如下
  • 左左情况：y 是 z 的左子节点，x 是 y 的左子节点。
  • 左右情况：z 的右子节点和 x 的右子节点。
  • 右右情况：y 是 z 的右子节点，x 是 y 的左子节点。
  • 右右情况：y 是 z 的右子节点，x 是 y 的左子节点。

下面列出了在上述四种情况下要执行的过程。在每种情况下，我们只需要重新平衡以 z 为根的子树，并且一旦以 z 为根的子树的高度等于其插入前的值（通过适当的旋转），整个树就会平衡。

1. 左左情况

2. 左右情况

3. 右右情况

4. 右左情况

AVL 树的优点

• 由于高度始终保持平衡，AVL 树的高度永远不会超过 log N，其中 N 是树中的节点总数。
• 与简单的二叉搜索树相比，它提供了更好的搜索时间复杂度。
• AVL 树能够自平衡。

AVL 树的缺点

• 上述示例表明，AVL 树的实现可能很复杂。
• 此外，对于特定操作，AVL 树具有显著的常数因子。
• 与 AVL 树相比，红黑树被用于大多数已排序关联容器（集合、多重集、映射和多重映射）的 STL 实现中。与 AVL 树不同，红黑树在插入或删除时只需要一次重构。

AVL 树，专门为平衡数据库索引中使用的不平衡二叉树而开发，可以说已经达到了特定目的。它们与二叉搜索树的区别仅在于，在这种情况下，我们需要维护平衡因子，这意味着数据结构在各种操作后应保持为平衡树，这通过使用我们之前学过的 AVL 树旋转来实现。

AVL 树的属性

属性 1： 高度为 H 的 AVL 树可能拥有的最大节点数

= 2^H+1 - 1

高度为 3 的 AVL 树的最大可能节点数

= 23+1 - 1

= 16 - 1

= 15

因此，高度为 3 的 AVL 树可以插入的最大节点数为 15。

属性 2： 递归关系确定了高度为 H 的 AVL 树的最小节点数。

N(H) = N(H-1) + N(H-2) + 1

此递归关系的基本条件为-

N(0) = 1

N(1) = 2

属性 3： 具有 N 个节点的 AVL 树的最小可能高度

= [log2N]

使用 8 个节点的 AVL 树的最小可能高度

= [log28]

= [log223]

= [3log22]

= [3]

= 3

属性 4： 使用递归关系计算具有 N 个节点的 AVL 树的最大高度。

N(H) = N(H-1) + N(H-2) + 1

此递归关系的基本条件为-

N(0) = 1

N(1) = 2

注意

• 具有 n 个节点的 AVL 树的最大高度不能超过 1.44log2n。
• 换句话说，1.44log2n 是具有 n 个节点的 AVL 树的最坏情况高度。

AVL 树上的问题

问题 1：找出构建高度为 3 的 AVL 树所需的最小节点数。

解答： 众所周知，递归关系确定了高度为 H 的 AVL 树的最小节点数。

N(H) = N(H-1) + N(H-2) + 1

其中 N(0) = 1 和 N(1) = 2

步骤 01

将 H = 3 代入递归关系，我们得到-

N(3) = N(3-1) + N(3-2) + 1

N(3) = N(2) + N(1) + 1

N(3) = N(2) + 2 + 1 （使用基本条件）

N(3) = N(2) + 3 …………(1)

为了解决这个递归关系，我们需要 N(2) 的值。

步骤 02

将 H = 2 代入递归关系，我们得到-

N(2) = N(2-1) + N(2-2) + 1

N(2) = N(1) + N(0) + 1

N(2) = 2 + 1 + 1 （使用基本条件）

∴ N(2) = 4 …………(2)

步骤 03

将 (2) 代入 (1)，我们得到-

N(3) = 4 + 3

∴ N(3) = 7

因此，构建高度为 3 的 AVL 树所需的最小节点数为 7。