data-structures - AVL 树 : difference between leaves' depths?

Question

测试题:

让T是一棵 AVL 树，并且 x,y是树中的两片叶子 ( x != y )。 depth(x) - depth(y) 的最大值是多少？ ？

A. 0
B. 1
C. 2
D. None of the above

正确(？)答案是 D。谁能解释为什么不是 B，因为 AVL 属性之一是 height(a.left) - height(a.right) <= 1对于每个节点 a ？

Answer 1

以一般方式进行解释比显示反例需要更多时间。因此，考虑以下 8 阶斐波那契树，它是一棵 AVL 树:

将深度作为从根到节点的边数，叶子 0 的深度为 7，而叶子 52 的深度为 4。差异为 3。对于其他和更大的 AVL 树，差异可能更大。

请记住，树 AVL 的作用是每个节点的左右子树的高度差小于或等于 1。深度是另一回事。

老实说，这是一个棘手的问题。