AVL树：叶子深度之间的差异？
AVL tree: difference between leaves' depths?
一道测试题：
设T是一棵AVL树，x,y是树中的两片叶子（x != y）。 depth(x) - depth(y)的最大值是多少？
A. 0
B. 1
C. 2
D. None of the above
正确（？）答案是 D。有人可以解释为什么它不是 B，因为 AVL 属性之一是每个节点 a 的 height(a.left) - height(a.right) <= 1？
AVL 树保证 "worst" 案例查找时间为 O(log(n))。并且它保证任意两棵子树的高度差最多为1。但这并不能保证整棵树的最低节点和最高节点之间的高度差为1。在一棵大树中，可能会变大整棵树的高度差异。
理解 AVL 树的关键是理解它对 "subtree" 的定义。对于任何给定的节点，都有 2 个子树，有时称为左子树和右子树。这两个子树之间的高度差最多为 1。现在想象一下，这两个子树都可以附加到一个节点，并成为更大树中的一个子树。这个新的子树，称为节点的左子树，与同一节点上的右子树的高度差最多为 1。但这也意味着整棵树中任意 2 个叶子之间的最大高度差将为 2。可以重复此过程，并且 AVL 树可以在任何叶子之间具有较大的高度差，但仍然保持大 O 运行次。
笼统地解释比给出反例要花更多的时间。因此，考虑以下 8 阶斐波那契树，它是一棵 AVL 树：
以深度作为从根到节点的边数，叶子0的深度为7，而叶子52的深度为4。相差3。对于其他和更大的AVL树，差异可能更大。
请记住，树AVL的作用是每个节点的左右子树高度之间的差异小于或等于1。深度是另一回事。
老实说，这是一个棘手的问题。
一道测试题：
设T是一棵AVL树，x,y是树中的两片叶子（x != y）。 depth(x) - depth(y)的最大值是多少？
A. 0
B. 1
C. 2
D. None of the above
正确（？）答案是 D。有人可以解释为什么它不是 B，因为 AVL 属性之一是每个节点 a 的 height(a.left) - height(a.right) <= 1？
AVL 树保证 "worst" 案例查找时间为 O(log(n))。并且它保证任意两棵子树的高度差最多为1。但这并不能保证整棵树的最低节点和最高节点之间的高度差为1。在一棵大树中，可能会变大整棵树的高度差异。
理解 AVL 树的关键是理解它对 "subtree" 的定义。对于任何给定的节点，都有 2 个子树，有时称为左子树和右子树。这两个子树之间的高度差最多为 1。现在想象一下，这两个子树都可以附加到一个节点，并成为更大树中的一个子树。这个新的子树，称为节点的左子树，与同一节点上的右子树的高度差最多为 1。但这也意味着整棵树中任意 2 个叶子之间的最大高度差将为 2。可以重复此过程，并且 AVL 树可以在任何叶子之间具有较大的高度差，但仍然保持大 O 运行次。
笼统地解释比给出反例要花更多的时间。因此，考虑以下 8 阶斐波那契树，它是一棵 AVL 树：
以深度作为从根到节点的边数，叶子0的深度为7，而叶子52的深度为4。相差3。对于其他和更大的AVL树，差异可能更大。
请记住，树AVL的作用是每个节点的左右子树高度之间的差异小于或等于1。深度是另一回事。
老实说，这是一个棘手的问题。