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

height/depth 与树的大小相关联，这是树被平衡的直接结果。因为一个 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.

想象树被填满的样子：每个新的 'level' 深度对应于达到树的大小的阈值，即 2 的下一个幂。

你可以明白这是为什么：树的最深行是 'maxed out'，而树 N 的大小正好是二的幂的差一。 1+ 对应于当前正在填充的最深行，直到树的深度变为下一个 'level'，floor(lg(N)) 对应于树在前一个 'level'.

O(logn) 中的 AVL 树高度

AVL tree height in O(logn)

algorithm

time-complexity

avl-tree