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

Question

AVL树中的任何两个叶子之间的最大差是多少？如果我举一个例子，如果高度差大于2（对于任何两片叶子），我的树就会变得不平衡，但是答案是该差可以是任何值。我真的不明白，这怎么可能。有人可以举例说明吗？

Answer 1

任何两片叶子的水平差异可以是任何值！AVL的定义仅描述来自一个节点的两个子树上的高度差。因此，您需要以相等的高度填充子树，然后添加新节点以创建该单节点差异。但是没有人说该子树不包含某些定义完全相同的子树。当然，树是自平衡的，但是如果我们能不碰到它的平衡那么精确，那么我们可以在一些叶子之间创建任何高度差。

在第3级叶子24和第6级叶子10的示例：

Answer 2

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