AVL 树中 "empty" 节点数的 O 复杂度是多少？

Question

我们知道AVL树通常非常接近平衡。假设我们取一个AVL树并将其放入一个数组中(非常类似于堆，其中父级是索引i，左子级是2i，右子级是1i+1(，就大O复杂性而言，你会得到多少个空索引？

所以我知道树高度h的最小节点数=斐波那契(h+2(-1。因此，空指数的数量=2^h-1-(斐波那契(h+2(-1(=2^h-斐波纳契(h+2(。但我不知道下一步该怎么做才能证明它的复杂性。我想是O(log(n((，但我不确定。

Answer 1

如果h是基于0的(按照通常的约定(，则高度为h的AVL树中的最小节点数为F(h+3) - 1。

设n = F(h+3) - 1，并尝试求解h，以找到具有n节点的AVL树的最大高度。

F(x(的闭合形式由Binet公式给出(详见此处(：

F(x) = (phi^n - psi^n)/sqrt(5)

因此，

n = (phi^(h+3) - psi^(h+3))/sqrt(5) - 1
>= (phi^(h+3) - 1)/sqrt(5) - 1 since |psi| < 1

求解h产生

h <= log_phi(sqrt(5)(n + 1) + 1) - 3
<= 1.4405 log2(n)

高度为h的完整树具有2^(h+1) - 1个节点。或根据n:

2^(h+1) - 1
<= 2^(1.4405 log2(n) + 1) - 1
= 2 * (2^log(n))^1.4405 - 1
= 2n^1.4405 - 1   

因此，空节点的数量受的限制

2n^1.4405 - 1 - n = O(n^1.4405)