建造二进制搜索树所需的时间复杂性之间的差异？

Question

当我学习二进制搜索树（平衡且不平衡）时，我提出了我需要解决的问题：

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

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

2. chere不仅仅是nlog（n）吗？ 因为我们需要大量的旋转来进行AVL树的结构。

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

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

我们从构造

Answer 1

开始。要创建一棵树，您必须在其中插入

n元素。要将元素插入平衡的树中，您需要log(n)

。因此，您最终得到了

O(n*log(n))

。

回到常规的

Bst

。它是违反直觉的，但这取决于您如何构造这棵树。如果您不知道BST的所有元素（

ONLINE算法），那么您必须彼此插入每个元素。如果您非常不幸，则插入的复杂性是

n，因此会恶化。 注意这种情况极不可能，但仍然有可能。 但是，如果您提前知道所有元素，您仍然可以实现

O(n)

。您可以对它们进行排序

O(n^2)

，然后按以下顺序插入元素。

获取中间元素并将其插入root

，然后递归地对剩下的两个部分进行相同的操作。您最终将创建平衡的BST，并使用

O(nlog(n))

.

插入

O(nlog(n))元素。

可以证明，BST的预期高度会满足[xn]o（n log n），因为每个添加元素的旋转量为o（1）。