好的，这是周围CS人士在理论领域中的另一个问题。

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

你们可以帮我吗？

解决方案

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

对于大多数通用方案而言，这两种实现方式就足够了。

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

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

回答问题

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

首先，我们必须了解什么是树旋转，因此，请忽略我们曾经听过的AVL算法的所有其他内容，并加以理解。直截了当，这是向右旋转，是向左旋转，每个操作对树的作用，否则对精确方法的描述将使我们感到困惑。

接下来，了解平衡AVL树的技巧是每个节点都在其中记录其左子树和右子树的高度之间的差异。 "平衡的高度"的定义是，对于树中的每个节点，此高度都在-1和1之间(包括-1)。

接下来，了解如果我们添加或者删除了一个节点，则可能使树不平衡。但是我们只能更改作为添加或者删除节点的祖先的节点的余额。因此，我们要做的是用自己的方式备份树，使用旋转来平衡找到的所有不平衡节点，并更新其平衡分数，直到树再次平衡为止。

理解的最后一部分是在体面的参考中查找用于重新平衡找到的每个节点的特定旋转：这是它的"技术"，而不是高级概念。我们只需要在修改AVL树代码时或者在进行数据结构检查时记住细节即可。自从我上次使用AVL树代码以来已经有好几年了，在调试器实现中打开它们的程度往往会达到它们可以工作然后再继续工作的地步。所以我真的不记得了。我们可以使用一些扑克筹码在桌子上进行排序，但是很难确定我们确实拥有所有情况(数量不多)。最好只是查找一下。

然后就是将所有内容转换为代码的业务。

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

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

虽然经典的AVL树和RB树使用确定性方法，但我建议我们看一下"随机化的二进制搜索树"，这种树不但可以保持平衡并保证良好的平衡，而且无论密钥的统计分布如何，其开销都较小。

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

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

如果树将被读取很多次，并且在创建后不会被更改，那么对于完全平衡的AVL树而言，这可能值得额外的开销。同样，红黑树需要为每个节点多留一点存储空间，这为节点提供了"颜色"。

我最近一直在处理AVL树。

我能够找到有关如何平衡它们的最佳帮助是通过搜索google。

我只是围绕此伪代码进行编码(如果我们了解如何进行旋转，则很容易实现)。

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
  }
}

为了平衡AVL树，我只写了很多功能，我想与这里的所有人共享。我猜这种实现是完美的。当然欢迎提出疑问/问题/批评：

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

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

干杯。