algorithm - 什么是平均 log n 高度？

Question

我开始知道 Random-BST/Red-Black 树和其他一些树的高度是O(log n).

我想知道，这怎么可能。假设我有一棵这样的树

树的高度本质上是树的深度，在这种情况下将是4（离开父深度）。但是人怎么能说高度可以用O(log n)概念来表示呢？

我非常喜欢算法，这一点让我很困惑。我在哪里错过了重点？

Answer 1

在算法复杂性中，变量n通常是指集合中或参与某些计算的项目总数。在这种情况下，n是树中的节点总数。因此，在您发布的图片中n=31。如果树的高度是 ，则O(log n)意味着树的高度与 的对数成正比n。由于这是一棵二叉树，因此您将使用 log base 2。

⌊log₂(31)⌋ = 4

因此，树的高度应该约为 4 — 这正是您的示例中的情况。

Answer 2

正如我在评论中解释的那样，二叉树可以有多种情况：

• 在退化的情况下，二叉树只是一个链，它的高度是 O(n)。
• 在最好的情况下（对于大多数搜索算法），完整的二叉树具有对于任何节点，子树的高度都相同的属性。在这种情况下，长度将是 log(n) 的底（基数 2，或基数 k，对于 k 个分支）。您可以通过对树的大小进行归纳来证明这一点（构造函数中的结构归纳）
• 在一般情况下，您将混合使用这些，构建一棵树，其中任何节点都有可能不同高度的子树。