10

在学习二叉搜索树（平衡和不平衡）时，我提出了需要解决的问题：

  1. 如果我构造一个二叉搜索树（不需要平衡），使用 n 个元素，那么树构造的总时间复杂度是多少？

  2. 如果 AVL 树由 n 个元素构成，那么构建该 AVL 树的时间复杂度是多少？

它应该超过 nlog(n) 吗？因为我们需要大量的旋转来构建 AVL 树。

我知道 AVL 树中的插入和删除操作将是 log(n) 顺序（如果用随机元素构造的二叉搜索树具有 log(n) 高度，也是如此）。

但我需要了解整体树构建成本以及它如何变化，因为我需要使用平衡搜索树进行排序。

4

2 回答 2

30

让我们从构建AVL 树开始。要创建一棵树，您必须在n其中插入元素。要在平衡树中插入元素，您需要log(n). 因此你最终得到O(n*log(n)).

回到常规的BST。这是违反直觉的，但这取决于你如何构建这棵树。如果您事先不知道 BST 的所有元素（在线算法），那么您必须一个接一个地插入每个n元素。如果你非常倒霉，插入的复杂度会O(n)因此恶化到O(n^2).

请注意，这种情况极不可能发生，但仍有可能。

但是，O(nlog(n))如果您提前了解所有要素，您仍然可以实现。您可以对它们进行排序O(nlog(n))，然后按以下顺序插入元素。取中间元素并将其作为 root 插入，然后递归地对剩下的两个部分执行相同的操作。您最终将创建平衡的 BST，n使用log(n).

于 2015-02-03T07:27:10.627 回答
9
  1. 可以证明BST的期望高度满足E[Xn] <= 3 log n + O(1)，所以期望时间为O(n log n)。最坏的情况仍然是 O(n^2)，例如，如果输入已排序。
  2. O(n log n) 因为每个添加元素的旋转量是 O(1)。
于 2013-07-13T14:33:58.843 回答