algorithm - O(logn) 中的 AVL 树高度

Question

我正在尝试找出一种方法，利用每个节点都知道其平衡这一事实来计算树的高度。这个复杂度必须在 O(logn) 内

这是我到目前为止所得到的。

if(!node)
  return 0
if(node.balance > 0)
  return height(node.right) + 1
if(node.balance < 0)
  return height(node.left) + 1
return max( height(T.left), height(T.right)) + 1

我的想法是，如果树右边很重，遍历右边而忽略左边。如果树左边很重，请忽略右边并继续穿过那里。但是，如果树是平衡的，我不知道该怎么办。到那时，我们不会被迫运行 max( height(T.left), height(T.right)) + 1 这意味着将访问子树中的每个节点，因此无论哪种方式都使这个复杂度为 O(n)？

Answer 1

作为平衡树的直接结果，高度/深度与树的大小相关联。因为 AVL 是平衡的，所以如果您知道它的大小，您可以使用它的结构在 O(1) 中计算树的深度:

   lg N = log(N) / log(2) -- define a helper function for 2-log
   depth N = 1 + floor(lg(N)) -- calculate depth for size N > 0.

想象树被填满时的样子:每个新的深度“级别”对应于所达到的树大小的阈值，即 2 的下一次幂。

您可以看出这是为什么:当树 N 的大小仅差二的幂时，树的最深行“用完了”。 1+ 对应于当前正在填充的最深行，直到树的深度更改为下一个“级别”，floor(lg(N)) 对应到树在前一个“级别”上的深度。