平衡二叉树(AVL)

好吧,这是CS领域的另一个理论领域.

在90年代,我在实施BST方面做得相当不错.我唯一无法理解的是算法的复杂性以平衡二叉树(AVL).

你能帮助我吗？

我认为在这里发布节点平衡算法的完整代码并不好,因为它们变得非常大.但是,关于红黑树的维基百科文章包含了算法的完整C实现,而关于AVL树的文章也有几个链接到高质量的实现.

这两种实现对于大多数通用场景都足够了.

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

然而,与AVL不同,它始终不是高度平衡的.像红黑一样,它的不平衡是有界的,但与红黑不同,它可以通过参数进行调节,因此对于大多数实际用途来说,它看起来像你需要的那样平衡.我怀疑,如果你把它调得太紧,那么最坏情况插入时最终会比AVL更差或更差.

回答问题编辑

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

首先,您必须了解树旋转的内容,因此请忽略您听过的所有其他AVL算法并理解它.直接在你的头部,这是一个正确的旋转,这是一个左旋转,每个人对树做什么,否则精确方法的描述会让你感到困惑.

接下来,要了解平衡AVL树的技巧是每个节点在其中记录其左右子树的高度之间的差异."高度平衡"的定义是树中每个节点的介于-1和1之间.

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

理解它的最后一部分是在一个不错的参考中查找用于重新平衡你找到的每个节点的特定旋转:这是它的"技术"而不是高概念.您只需在修改AVL树代码时或在数据结构检查期间记住细节.自从我上次使用AVL树代码以及在调试器中打开以来已经很多年了 - 实现往往会达到他们工作的程度,然后继续工作.所以我真的不记得了.你可以使用一些扑克筹码在桌面上进行练习,但很难确定你真的得到了所有的情况(没有很多).最好只是查找它.

然后就是把它全部翻译成代码的业务.

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