平衡二叉树（AVL）的平衡

Question

平衡二叉树（AVL）的平衡

algorithmcomputer-sciencebinary-treetheoryavl-tree

14

好的，这是关于计算机科学领域理论方面的又一个问题。

在90年代，我在实现二叉搜索树方面表现得相当不错。但是唯一让我困扰的是平衡二叉树（AVL）的算法复杂性。

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

- Gustavo Carreno

1

你想要树“完美”平衡吗？最常见的算法保证树是相对平衡的。例如，红黑树保证最深叶节点的深度不超过最浅叶节点深度的两倍。 - Adam Tegen

“perfectly”必须被定义。然而，在二叉树的上下文中，唯一有意义的定义是具有对数高度的二叉树，不是吗？ - Konrad Rudolph

1

你是在让人们投票选出他们最喜欢的平衡树算法吗？答案不取决于应用程序吗（例如，Splay树在重复最近搜索的情况下具有良好的性能，AVL树完全平衡，红黑树提供最美观的解释图表等）。 - Steve Jessop

1

抱歉，打错了。我是指“红黑树在插入时具有良好的最坏情况性能”。 - Steve Jessop

我希望这次编辑能够澄清事情。 - Gustavo Carreno

显示剩余3条评论

7个回答

15

一种可能是最简单的平衡树是Scapegoat Tree。它的平衡算法很容易理解。如果插入节点导致新节点过深，它会查找一个节点来重新平衡，通过查看权重平衡而非高度平衡。删除时重新平衡的规则也很简单。它不会在节点中存储任何奇怪的信息。证明其正确性更加困难，但你不需要这个来理解算法...

然而，与AVL树不同的是，Scapegoat Tree并不总是高度平衡的。像红黑树一样，它的不平衡有限制，但与红黑树不同的是，它可以通过参数进行调整，因此对于大多数实际目的而言，它看起来和你需要的平衡度一样好。我怀疑如果你把它调得太紧，最坏情况下插入变得糟糕或更糟比AVL树还要糟糕。

针对编辑后的问题：

以下是我理解AVL树的个人经验路径：

首先你必须理解什么是树旋转，所以忽略你之前听过的AVL算法的所有内容，并且理解其中的每一个步骤，知道向右旋转和向左旋转分别是哪个，以及每个旋转如何影响树形结构，否则精确方法的描述只会让你更加困惑。

接下来，理解AVL树平衡的技巧是每个节点记录其左右子树高度之差。'平衡高度'的定义是每个节点在-1和1之间（含-1和1）的高度差。

然后，理解如果你添加或删除了一个节点，可能会使树不平衡。但你只能改变添加或删除节点的先代节点的平衡状态。所以你要沿着树向上工作，使用旋转来平衡发现的任何不平衡节点，并更新它们的平衡得分，直到树再次平衡。了解AVL树的最后一部分是在一个良好的参考文献中查找用于重新平衡每个节点的特定旋转：这就是它的“技巧”，与高级概念相对应。您只需要记住详细信息，以修改AVL树代码或者在数据结构考试期间使用。我已经很多年没有看过AVL树代码了，因为实现往往会达到一个工作状态然后保持工作。所以我真的不记得了。您可以使用几个扑克筹码在表格上大致计算出来，但很难确定您是否真正掌握了所有情况（并不多）。最好还是查阅资料。

然后，就有了将其全部翻译成代码的业务。

我认为仅仅通过查看代码清单，并不能非常有效地帮助任何阶段，因此请忽略它们。即使在最好的情况下，代码明确编写，它看起来也像是过程的教科书描述，但却没有图表。在更典型的情况下，它是一堆C结构操作的混乱。因此，请坚持参考书籍。

- Steve Jessop

我接受你的答案，因为它是我从问题中想要的：一个详细的应该做什么的描述。 - Gustavo Carreno

3

很高兴你喜欢它——Konrad提供的维基百科链接也很有用，因为它们提供了我所遗漏的细节。 - Steve Jessop

4

最近我一直在做AVL树相关的工作。

我在谷歌上搜索到了关于如何平衡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
  }
}

- mscccc

1

AVL树的这一部分相当简单 - 有点棘手的是在旋转后更新平衡因子。 - user82238

1

我同意，完整的程序可能不太合适。

虽然传统的AVL和RB树使用确定性方法，但我建议看一下 "随机二叉搜索树"，它们更少地花费来保持平衡，并保证良好的平衡，无论键的统计分布如何。

- rdentato

0

为了平衡AVL树，我刚刚编写了一堆函数，想与大家分享。我认为这个实现是完美无缺的。当然，如果有任何疑问/问题/批评，欢迎提出：

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

作为 Stackoverflow 的新手，我尝试在这里发布我的代码，但遇到了糟糕的格式问题。因此，我在上面的链接上载了文件。

谢谢。

- Rocky

0

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

- cos

0

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

红黑树可能是更好的选择，因为插入/删除更加高效。该结构保证到叶子节点的最长路径不超过最短路径的两倍。因此，虽然比AVL树不太平衡，但避免了最坏的不平衡情况。

如果您的树将被多次读取，并且在创建后不会被修改，则完全平衡的AVL树可能值得额外的开销。此外，红黑树需要为每个节点提供一个额外的存储位，用于表示节点的“颜色”。

- user20493

就个人而言，我从未找到过红黑树的实际解释——只有规则的列表。似乎没有人理解红黑树的原因。另一方面，AVL对我来说是直观和易于理解的；你应该只编写你理解的代码。 - user82238

1

"为什么": RB树是将2-3-4树映射到二叉树上的一种方式，其中红色边连接拆分的2-3-4树节点的部分，黑色边对应于原始2-3-4树中的边。 - Jeffrey Hantin

2

关于“可能有多个旋转的插入/删除”这一点。AVL树的插入只需要一个单旋转或双旋转即可恢复平衡。但是，删除可能需要最多O(log N)次旋转。 - otherchirps

就程序设计而言，红黑树并不是非常快的数据结构。它们的主要优点在于操作时间的变化较小。如果追求速度，Treap是一个不错的选择，但它们的变异性较高。有关更多信息，请参阅http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/。 - user1277476

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Konrad Rudolph · Accepted Answer

我认为在此处发布完整的节点平衡算法代码并不好，因为它们会变得非常庞大。但是，红黑树的维基百科文章包含了该算法的完整C实现，而AVL树的文章则有几个高质量实现的链接。

对于大多数通用场景，这两个实现已经足够了。