完美平衡二叉树的复杂性

Question

我的场景是一个包含整数的完美平衡二叉树。

我搜索并找到了许多关于二叉树最佳/最坏情况的解释。最好的情况是

O(1)

（在根中找到目标），最坏的情况是

O(log(n)) 

（树的高度）。

我发现几乎没有关于计算“平均”复杂度的信息。我能找到的最佳答案是O(log(n)) - 1，但我想我不太明白（如果正确的话）这个平均情况是如何计算的。

此外，搜索不在树中的整数会产生相同的复杂性吗？我认为会的，但任何见解都会受到赞赏。

Answer 1

n = 2k

个整数，因此深度为

log₂(n) = k

。最好和最坏的情况是，正如你所说，

O(1)

和

O(log(n))

。短路

让我们从二叉树中选择一个随机整数

X

（均匀分布）。树的最后一行包含与前

k-1

行相同数量的整数。

1/2

X

的概率位于第

k-1

行，因此我们最多需要

O(k-1) = O(log(n)-1)

步才能找到它。并且也有可能

1/2

X

位于最后一行，我们需要

O(k) = O(log(n))

步骤。我们总共得到

E

[X] ≤ P(X 的行 ≤ k-1)⋅O(log(n)-1) + P(X 的行 = k)⋅O(log(n))
     = 1/2⋅O(log(n)-1) + 1/2⋅O(log(n))
     = 1/2⋅O(log(n)-1) + 1/2⋅O(log(n)-1)
     = O(log(n)-1)
注意：这有点难看，但在 O 表示法中 

O(x)

和

O(x±c)

对于任何常数值

c

都是相同的。路途遥远

现在让我们尝试计算树中包含的随机（均匀分布）整数

X

的平均情况，并命名树

i

的第

Ti

“行”上的整数集。

Ti

包含

2i

元素。

T0

表示根。在第 i 行中选择一个整数的概率是

P(X ∈ Ti) = 2i/n = 2i-k

。

要在第

i

行查找整数，需要

O(2i) = O(i)

步骤。所以预期的步数是

E

[X] = Σi=0,...,k-1 O(i)⋅2i-k.
为了简化这个，我们使用

O(i)⋅2

i-k

 + O(i+1)⋅2i+1-k ≤ O(i)⋅2i+1-k + O(i+1)⋅2 i+1-k ≤ O(i+1)⋅2i+2-k
这引导我们

E

[X] = Σi=0,...,k-1 O(i)⋅2i-k ≤ O(k-1)⋅2⁰
自

k = log(n)

以来，我们看到平均情况在

O(log(n)-1) = O(log(n))

。值不在树中

如果值不在树中，则必须遍历整棵树。经过

log(n)

步骤后，您已经找到了一片叶子。如果该值等于您输入的值，则您已找到所需的内容。如果没有，您就知道您搜索的值不包含在树中。因此，如果您搜索树中没有的值，则需要

O(log(n))

。