问题标签 [avl-tree]

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

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

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

上图来自“维基百科关于 AVL 树的条目”，维基百科指出它是不平衡的。这棵树怎么还不平衡？这是文章的引述：

节点的平衡因子是其右子树的高度减去其左子树的高度，平衡因子为 1、0 或 -1 的节点被认为是平衡的。具有任何其他平衡因子的节点被认为是不平衡的，需要重新平衡树。平衡因子要么直接存储在每个节点上，要么根据子树的高度计算。

左子树和右子树的高度均为 4。左树的右子树的高度为 3，但仍然比 4 小 1。有人可以解释我缺少什么吗？

我正在寻找所有 AVL 树都可以像红黑树一样着色的证据？任何人都可以提供证据吗？

我正在寻找在AVL-tree中计算节点余额的最佳方法。我以为我可以正常工作，但是经过一些繁重的插入/更新后，我可以看到它（根本）无法正常工作。

这是一个两部分的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是从该节点到叶子的最长向下路径的长度。” 我理解它，但我未能实施它。为了让我更加困惑，这句话可以在 wikipedia on tree-heights 上找到“通常，值 -1 对应于没有节点的子树，而 0 对应于具有一个节点的子树。”

第二部分是获取 AVL 树中子树的平衡因子，我对“获取您的树和子树的高度并从中减去”LRRL这个概念没有问题。这被定义为这样的：BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在维基百科上阅读描述插入 AVL 树的前几行是这样说的：“如果平衡因子变为 -1、0 或 1，那么树仍然是 AVL 形式，不需要旋转。”

然后它继续说“如果平衡因子变为 2 或 -2，则以该节点为根的树是不平衡的，需要进行树旋转。最多需要单轮或双轮旋转来平衡树。” - 我很容易掌握。

但是（是的，总是有一个但是）。

这是令人困惑的地方，文本指出“如果 R 的平衡因子为 1，则意味着插入发生在该节点的（外部）右侧并且需要左旋转”。但是根据我的理解，文本说（正如我所引用的）如果平衡因素在范围内，[-1, 1]那么就不需要平衡了吗？

我觉得我已经非常接近掌握这个概念了，我已经降低了树的旋转，实现了一个正常的二叉搜索树，并且在掌握 AVL 树的边缘，但似乎只是缺少了那个重要的顿悟。

编辑：代码示例优于学术公式，因为我总是更容易掌握代码中的某些内容，但非常感谢任何帮助。

编辑：我希望我可以将所有答案都标记为“已接受”，但对我来说，尼克的答案是第一个让我“啊哈”的答案。

更具体地说，是 AVL 树。可能吗？我想这样做，但我认为未删除的节点可能难以管理旋转。

我有一个可以正常工作的，但我想用这个延迟删除来做其他事情。

我有一个大的AVL 树，我在程序期间从未排序的集合中构建了一些时间（它将用于稍后插入/删除项目）。

有没有比在每个项目上使用简单插入更好的算法？首先对集合进行排序然后尝试以不同的方式构建它会更有效吗？

我的应用程序分析告诉我这个 AVL 建筑物是一个热点位置。

我正在阅读 Steve Yegge 关于单身人士的文章。在其中他提到他的老师告诉他 AVL 树是邪恶的。仅仅是红树和黑树是更好的解决方案吗？

作为程序员，我什么时候应该考虑使用 RB 树、B-树或 AVL 树？在决定选择之前需要考虑哪些关键点？

有人可以为每个树结构解释一个场景，为什么参考关键点选择它而不是其他树结构？

我希望这段代码成为可能。

具体来说，我想强制 Comparer 类具有一个static int compare(K key1, K key2)功能。我正在考虑使用派生，但找不到任何可以使用模板的想法。

谢谢你。

如何平衡这种树状结构