构建二叉搜索树的时间复杂度是多少？

Question

"对于任意比较排序算法，最坏情况下排序n个元素的比较次数必须达到Ω(nlogn)。基于这个事实，请问构建一个n个节点的二叉搜索树的复杂度会是多少？为什么？"

根据这个问题，我认为构建复杂度至少为O(nlogn)。但是，我似乎无法找出构建总复杂度的方法。

- Jake

---

我认为这个问题更适合在https://cstheory.stackexchange.com上讨论。 - Eduardo Pascual Aseff

当然，这取决于您是否在努力保持树的平衡（例如AVL、RedBlack、Splay、随机二叉搜索树）。对于AVL和RedBlack，最坏情况下是O(n log(n))，对于随机BST来说是平均情况，对于Splay来说是摊销情况。如果排序是您的目标，则堆优于BST，可以达到O(n log(n))的时间复杂度。 - wcochran

如果树不平衡（例如，键按顺序插入），则每次插入的时间复杂度为O(n)，总时间复杂度为O(n^2)。@Daniele - wcochran

@EduardoPascualAseff 可能是cs.stackexchange.com而不是cstheory.stackexchange.com。 - Jim Mischel

Answer 1

问题的标题和你引用的文本在询问不同的事情。我将回答引语所说的内容，因为通过查看算法就可以找到构建BST的昂贵程度。

假设有一种方法可以以优于Ω(nlogn)的速度构建BST。使用二叉搜索树，您可以在Θ(n)的时间内读取排序列表。这意味着我可以创建以下排序算法。

Algorithm sort(L) 
  B <- buildBST(L)
  Sorted <- inOrderTraversal(B)
  return Sorted

通过这种算法，我将能够以优于Ω(nlogn)的速度对列表进行排序。但正如你所说，这是不可能的，因为Ω(nlogn)是下限。因此，不可能在优于Ω(nlogn)的时间内创建二叉搜索树。

此外，由于存在一种算法可以在O(nlogn)时间内创建BST，因此您实际上可以说该算法在比较基准模型下是最佳的。

- Mitch

Answer 2

BST的构建将是O(n(log(n)))。
您需要插入每个节点，这是一个O(n)操作。
要插入那n个节点，您至少需要进行O(log(n))次比较。
因此，最小值将是O(n(log(n)))。
仅在数组已经排序的最佳情况下，时间复杂度才为O(n)

- Pritam Banerjee

---

实际上，要插入每个节点，您需要进行最多 O(log(n)) 次比较。排序数组并不能为您提供 O(n) 的 BST 创建。仍然有许多情况需要进行 O(log n) 次比较才能找到正确的插入点。 - Jim Mischel