AVL树：叶子深度之间的差异？

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。深度是另一回事。

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