algorithm - 平衡二叉树 (AVL)

Question

好的，对于周围的 CS 家伙来说，这是另一个理论领域。

在 90 年代，我在实施 BST 方面做得相当好。唯一让我无法理解的是平衡二叉树 (AVL) 的算法的复杂性。

你们能帮我解决这个问题吗？

score 16 · Accepted Answer

我认为在这里发布节点平衡算法的完整代码并不好，因为它们变得相当大。但是，关于红黑树的 Wikipedia 文章包含该算法的完整 C 实现，而关于AVL 树的文章也有几个指向高质量实现的链接。

这两种实现对于大多数通用场景来说已经足够了。

score 15 · Accepted Answer

替罪羊树可能有最简单的平衡确定算法来理解。如果任何插入导致新节点太深，它会通过查看重量平衡而不是高度平衡来找到要重新平衡的节点。删除时是否重新平衡的规则也很简单。它不在节点中存储任何神秘信息。证明它是正确的比较棘手，但你不需要它来理解算法......

然而，与 AVL 不同，它并非始终保持高度平衡。像红黑一样，它的不平衡是有界的，但与红黑不同的是，它可以通过参数进行调整，因此对于大多数实际目的，它看起来就像你需要的一样平衡。但是，我怀疑如果您将其调整得太紧，那么对于最坏情况的插入，它最终会比 AVL 更差或更差。

对问题编辑的回应

我将提供我个人理解 AVL 树的途径。

首先，您必须了解什么是树旋转，因此请忽略您曾经听过 AVL 算法的所有其他内容并理解这一点。直截了当地了解哪个是右旋转，哪个是左旋转，以及每个对树的作用，否则对精确方法的描述只会让你感到困惑。

接下来，了解平衡 AVL 树的技巧是每个节点在其中记录其左右子树的高度差。“高度平衡”的定义是，对于树中的每个节点，它都介于 -1 和 1 之间。

接下来，了解如果您添加或删除了一个节点，您可能会使树不平衡。但是您只能更改作为您添加或删除的节点的祖先的节点的平衡。所以，你要做的就是沿着树的方向工作，使用旋转来平衡你找到的任何不平衡节点，并更新它们的平衡分数，直到树再次平衡。

理解它的最后一部分是在一个体面的参考中查找用于重新平衡您找到的每个节点的特定旋转：这是它的“技术”，而不是高级概念。您只需要在修改 AVL 树代码或可能在数据结构考试期间记住细节。自从我上次在调试器中打开 AVL 树代码以来已经有好几年了 - 实现往往会达到它们工作的程度，然后继续工作。所以我真的不记得了。您可以使用一些扑克筹码在桌子上解决问题，但很难确定您是否真的掌握了所有情况（数量不多）。最好只是查一下。

然后就是将其全部转换为代码的业务。

我不认为查看代码清单对除最后一个以外的任何阶段都有很大帮助，因此请忽略它们。即使在最好的情况下，代码写得很清楚，它看起来就像教科书上的过程描述，但没有图表。在更典型的情况下，它是 C 结构操作的混乱。所以只能坚持看书。

score 4 · Accepted Answer

我最近一直在用 AVL 树做一些工作。

我能找到的关于如何平衡它们的最佳帮助是通过搜索谷歌。

我只是围绕这个伪代码编写了代码（如果你了解如何进行旋转，它很容易实现）。

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

score 1 · Accepted Answer

我同意，一个完整的程序是不合适的。

虽然经典的 AVL 和 RB 树使用确定性方法，但我建议看一下“随机二叉搜索树”，无论密钥的统计分布如何，保持平衡和保证良好平衡的成本更低。

score 0 · Accepted Answer

AVL 树效率低下，因为每次插入/删除都可能需要进行多次旋转。

红黑树可能是更好的选择，因为插入/删除更有效。这种结构保证到叶子的最长路径不超过最短路径的两倍。因此，虽然不如 AVL 树平衡，但避免了最严重的不平衡情况。

如果您的树将被多次读取，并且在创建后不会被更改，那么对于完全平衡的 AVL 树来说，额外的开销可能是值得的。此外，红黑树需要为每个节点提供一个额外的存储空间，从而赋予节点的“颜色”。

score 0 · Accepted Answer

为了平衡 AVL 树，我刚刚写了一堆函数，我想在这里与大家分享。我想这个实现是完美的。当然欢迎提问/提问/批评：

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

作为 Stackoverflow 的新手，我尝试在此处发布我的代码，但遇到了错误的格式问题。因此，将文件上传到上述链接。

干杯。

score 0 · Accepted Answer

有一个自平衡 avl 树的完整实现 @ http://code.google.com/p/self-balancing-avl-tree/。它还实现了对数时间连接和拆分操作以及映射/多映射集合

algorithm - 平衡二叉树 (AVL)

7 回答 7

Related

Reference