AVL树中叶子节点之间的高度差

Question

AVL树中任意两个叶子节点的最大差值是多少？如果高度差超过2（对于任意两个叶子），我的树就会失衡，但答案是差值可以是任何值。我真的不明白这是怎么回事。有人可以用示例解释一下吗？

- Prasita Mukherjee

---

你所说的“difference”具体指什么？是指两片叶子高度的差异吗？ - Codor

Answer 1

任意两个叶子节点之间的高度差可以是任何值！AVL树的定义仅描述了一个节点下的两个子树的高度差。因此，您需要填充子树以使它们具有相等的高度，然后添加新节点以创建单个节点差异。但是没有人说该子树不包含具有完全相同定义的其他子树。当然，树是自平衡的，但如果我们要保持它的平衡，则可以在某些叶子节点之间创建任何高度差。例如，在第3级上的叶子24和第6级上的叶子10的示例中：

- Vladimir Mezentsev

---

谢谢！解释得非常清楚 :) - Prasita Mukherjee

那么树的高度最大差异是多少？ - heysamhey

@heysamhey 我认为它是O(logn)，因为那是最大层数，差异不可能更大。 - Dunno

Answer 2

根据这篇维基百科文章中的解释，AVL树中的平衡操作旨在重新排列树，使得任意两个叶子节点的高度差不超过一。这是该数据结构的关键属性，使得节点检索高效（即在树的节点数量情况下最坏情况下遍历从根到叶子节点的路径的复杂度为对数级别）。

- Codor

---

AVL树维护两个子树之间的最大高度差为1，而不是任意两个叶子节点。 - Chaitanya Patel