平衡二叉树(AVL)

Question

好了，这是另一个在理论领域的CS的家伙。

在90年代，我在实现BST时做得相当好，唯一一件我永远不能理解的事情是平衡二叉树(AVL)算法的复杂性。

你们能帮帮我吗？

Answer 1

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

然而，与AVL不同的是，它并不总是高度平衡的。像红-黑一样，它的不平衡是有界的，但与红-黑不同的是，它可以通过一个参数进行调整，所以在大多数实际用途中，它看起来就像你需要的那样平衡。我怀疑如果你调得太紧，在最坏的情况下，它会和AVL一样糟糕，甚至比AVL更糟糕。

对问题的响应编辑

我将提供我个人理解AVL树的方法。

首先，你必须了解什么是树轮换，所以忽略你听说过的AVL算法，并理解这一点。在你的脑海中弄清楚什么是右旋转，哪个是左旋转，以及每种旋转对树的作用，否则精确的方法描述只会让你感到困惑。

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

接下来，请理解，如果添加或删除了节点，则可能会使树不平衡。但您只能更改节点的平衡，这些节点是您添加或删除的节点的祖先。所以，你要做的就是回到树上，使用旋转来平衡你找到的任何不平衡的节点，并更新它们的平衡分数，直到树再次平衡。

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

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

除了最后一个阶段，我不认为查看代码清单对任何阶段都有很大帮助，所以忽略它们。即使在最好的情况下，代码写得很清楚，它看起来也像是对该过程的教科书描述，但没有图表。在更典型的情况下，这是一堆C结构操作。所以只要照本宣科就好。

Answer 2

我不认为在这里发布节点平衡算法的完整代码是好的，因为它们变得非常大。但是，red-black trees上的维基百科文章包含了算法的完整C实现，AVL trees上的文章也有几个指向高质量实现的链接。

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

Answer 3

我最近一直在做一些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
  }
}