2*N_2 = O(2^(h/2))
2*N_2 = O(2^(h/2))
提问于 2014-06-08 14:26:16
我试图证明有N个节点的AVL树的高度至多是log N。证明如下：
N_h = 1 + N_h-2 + N_h-1
> 2*N_h-2 (1)
> O(2^(h/2)) (2)
h < 2*lg N_h (3)首先，有人能解释为什么2*N_h-2 > O(2^(h/2))，我似乎不理解这里的代数规则。而且，我也不明白如何从2*N_h-2 > O(2^(h/2))到h < 2*lg N_h。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-06-08 15:31:47
在AVL树中，每个节点的子树的高度最多相差1。
因此，如果N_h表示有N个节点的AVL树的高度，那么：
N_h >= 1 + N_h-1 + N_h-2 ( the heights of both sub-trees can differ by at most one )
>= 1 + 2*N_h-2
>= 1 + 2*( 1 + 2*N_h-4 ) (by the same recurrence relation)
= 1 + 2 + 4*N_h-4
>= 1 + 2 + 4 + 8*N_h-6
>= 1 + 2 + 4 + 8 +...+ 2^(h/2)
= 2^(h/2) - 1 (sum of geometric series)
Hence N_h >= 2^(h/2) - 1.
h/2 <= log(N_h + 1)
h <= 2*log(N_h + 1)
Hence h = O(logN)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24107103
复制相关文章
相似问题
腾讯云开发者
