AVL树中的叶子之间的高度差 [英] Height difference between leaves in an AVL tree

问题描述

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

What is the maximum difference between any two leaves in an AVL tree? If I take an example, my tree becomes unbalanced, if the height difference is more than 2(for any two leaves), but the answer is the difference can be any value. I really don't understand, how this is possible.Can anyone explain with examples?

推荐答案

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

The difference in levels of any two leaves can be any value! Definition of AVL describes height difference only on two sub-trees from one node. So you need to fill subtrees with equal height then add new nodes just to create that single node difference. But nobody said that that subtree doesn't contain some subtrees with the exact same definition. Of course tree is selfbalanced but if we'll be that accurate to not touch it's balance then we can create any height difference between some leaves.

第24个叶子处于水平位置的示例3级和第6级叶10：

Example with leaf 24 on level 3 and leaf 10 on level 6:

这篇关于AVL树中的叶子之间的高度差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！