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

Question

给定avl树，"best"计算树高的算法的时间复杂度是多少？

鉴于树中存在 n 个元素，我知道树的高度是 log(n)。但是如何计算高度呢？

Answer 1

假设构成高度为 h 的树的节点数是 N_h。因此，以左子节点为根的树的高度为 h-1，节点为 N_(h-1)，右子树的最小高度为 h - 2，节点为 N_(h-2) 作为 AVL 树是平衡的（左右子树的高度差不能大于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)

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

What is the complexity time for calculating the height of avl tree?

time-complexity

avl-tree