C++ AVL 树

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

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

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

平衡因子

平衡因子 (k) = 高度 (左(k)) - 高度 (右(k))

• 如果任何节点的平衡因子为 1，则左子树比右子树高一个级别。
• 平衡因子为零的任何节点都表示左子树和右子树的高度相等。
• 如果节点的平衡因子为负一，则左子树比右子树低一个级别。
• 下图展示了一棵 AVL 树。我们可以看到每个节点的平衡因子都在 -1 到 +1 之间。因此，这是 AVL 树的一个例子。

为什么要使用 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. 右左情况

插入方法

其思想是利用递归 BST 插入，在插入后，我们会单独收到指向每个祖先的自底向上的指针。因此，我们不需要父指针来向上移动。递归代码本身会向上移动并访问之前插入的每个节点。

为将该思想付诸实践，请遵循以下步骤

• 执行标准的 BST 插入。
• 新插入节点的祖先必须是当前节点。应更新当前节点的高度。
• 找到当前节点的平衡因子（左子树高度减去右子树高度）。
• 如果平衡因子大于 1，则当前节点失衡，我们处于左左情况或左右情况。将新插入的键与左子树根节点处的键进行比较，以确定是否为左左情况。

插入程序

输出

Preorder traversal of the constructed AVL tree is 
30 20 10 25 40 50 
…………………………………………………………………………..
Process executed in 1.22 seconds
Press any key to continue

说明

在旋转操作（左旋和右旋）期间仅更新少数几个点，因此所需时间是恒定的。更新高度和获取平衡因子也需要恒定的时间。因此，AVL 插入的时间复杂度与 BST 插入相同，即 O(h)，其中 h 是树的高度。由于 AVL 树是平衡的（Logn），因此高度为 O。因此，AVL 插入的时间复杂度为 O(Logn)。

与红黑树比较

红黑树

红黑树是一种自平衡二叉搜索树，每个节点拥有的额外位通常被理解为颜色（红色或黑色）。这些颜色的使用在插入和删除过程中保持了树的平衡。尽管树的平衡不是完美的，但足以缩短搜索时间并将其保持在 O(log n) 或以下，其中 n 是树组件的总数。Rudolf Bayer 于 1972 年发明了这种树。

通过使用 AVL 树和其他自平衡搜索树（如红黑树），所有基本操作都可以在 O(log n) 时间内完成。与红黑树相比，AVL 树的分布更均匀，尽管在插入和删除过程中可能会导致更多的旋转。因此，如果您的应用程序包含频繁的插入和删除，则推荐使用红黑树。此外，如果搜索的频率更高，而插入和删除的频率较低，则应选择 AVL 树而不是红黑树。

AVL 树的删除

为了确保在每次删除后提供的树保持 AVL，我们必须在典型的 BST 删除过程中添加一些重新平衡。以下两个简单操作（左键(左) 根键(右键)）可用于重新平衡 BST，而不会违反 BST 属性。

• 左旋
• 右旋

树的 T1、T2 和 T3 子树以 y（在左侧）或 x（在右侧）为根。

上述两棵树中键的顺序如下

键(T1) < 键(x) < 键(T2) < 键(y) < 键(T3)

设 w 表示被删除的节点

• 对 w 执行典型的 BST 删除。
• 通过从 w 开始向上移动来找到第一个失衡节点。设 y 为 z 的较高子节点，x 为 y 的较高子节点，z 为初始失衡节点。请注意，x 和 y 的定义与插入时不同。
• 以适当的方向旋转以 z 为根的子树以重新平衡树。由于 x、y 和 z 可以有 4 种不同的排序方式，因此可能有 4 种潜在的场景需要解决。四种潜在的配置如下
• 左左情况：y 是 z 的左子节点，x 是 y 的左子节点
• y 是 z 的左子节点，x 是 y 的右子节点。（左右情况）
• y 是 z 的右子节点，X 是 y 的右子节点（右右情况）
• Z 的右子节点是 y，而 x 是 y 的左子节点（右左情况）

就像插入一样，下面列出了在上述 4 种情况下要执行的过程。请注意，与插入不同，修复节点 z 可能不会完全修复 AVL 树。

1. 左左情况

2. 左右情况

3. 右右情况

4. 右左情况

与插入不同，在 z 处的旋转之后，可能需要在其祖先处进行旋转。因此，为了到达根节点，我们必须继续沿着路径前进。

删除方法

下面提供了 AVL 树删除的 C 实现。递归 BST 删除是以下 C 实现的基础。在递归 BST 删除之后，我们依次收到指向每个祖先的自底向上指针。因此，向上移动不需要父指针。递归代码本身会向上移动并访问被删除节点的所有祖先。

• 执行标准的 BST 删除。
• 被删除节点的祖先之一必须是当前节点。应更新当前节点的高度。
• 找到当前节点的平衡因子（左子树高度减去右子树高度）。
• 如果平衡因子大于 1，则当前节点失衡，我们处于左左情况或左右情况。获取左子树的平衡因子以确定是左左情况还是左右情况。如果左子树的平衡因子大于或等于 0，则为左左情况；否则，为左右情况。
• 如果平衡因子小于 -1，则当前节点失衡，我们处于右左情况或右右情况。获取右子树的平衡因子以确定是右右情况还是右左情况。如果右子树的平衡因子小于或等于 0，则表示右右情况；否则，表示右左情况。

输出

Preorder traversal of the constructed AVL tree is 
9 1 0 -1 5 2 6 10 11 
Preorder traversal after deletion of 10 
1 0 -1 9 5 2 6 11
…………………………………………………………………………….
Process executed in 1.11 seconds
Press any key to continue

说明

由于在旋转操作（左旋和右旋）期间仅更新少数几个点，因此所需时间是恒定的。获取平衡因子和更新高度都需要时间。因此，AVL 删除的时间复杂度为 O(h)，其中 h 是树的高度，与 BST 删除相同。由于 AVL 树的平衡（Logn），高度为 O。因此，AVL 删除的时间复杂度为 O。(Log n)。

AVL 树的优点

• 高度平衡是恒定的。
• N 是节点数，高度永远不会超过 logN。
• 与二叉搜索树相比，它提供了更好的搜索性能。
• 它具有自平衡的能力。

总结

• 这些二叉搜索树是自平衡的。
• 平衡因子值介于 -1 和 +1 之间。
• 当平衡因子超出范围时，必须进行旋转。
• 插入、删除和搜索时间为 O。(log N)。
• AVL 树通常用于搜索比插入和删除更频繁的场景。