计算avl树高度的复杂时间是多少？

1 回答

• 0

  假设生成高度树h的节点数是 N_h . 因此，将子项作为根的树的高度是 h-1 具有 N_(h-1) 个节点，并且右侧子树可以具有 h - 2 的最小高度和 N_(h-2) 节点，因为AVL树是 balancer 的（左右子树的高度差不能大于1） . 我们可以写下如下公式

  N_h = N_(h -1) + N_(h -2) + 1           (i)
  

  基本案例是 N_1 = 1 和 N_2 = 2 和

  N_(h−1) = N_(h−2) + N_(h−3) + 1           (ii)
  

  把 (ii) 放在等式 (i) 中我们得到

  N_h = N_(h−2) + N_(h−3) + 1  + N_(h -2) + 1 
  => N_h = 2*N_(h−2) + N_(h−3) + 2 
  => N_h > 2*N_(h-2)
  => N_h > 2^(h/2)
  => log(N_h) > log(2^(h/2))
  => 2log(N_h) > h
  => h = O(log(N_h)
  

  我们可以写 n 替换 N_h

  h = O(lgn)
  

  回复于 2024-05-01T04:17:45+08:00