algorithm - 创建平衡二叉搜索树的时间复杂度？

Question

虽然构建一个最小堆的时间复杂度看起来是O(nlogn)，但可以证明是O(n) .

为什么我们不能套用同样的逻辑，说平衡二叉搜索树的时间复杂度也是O(n)。

Answer 1

除了 BST 提供顺序，而堆只确保元素大于下面的元素(对于最大堆)，构建堆的复杂性取决于构建策略。这wiki image清楚地证明了这一点。

如果您使用siftDown(自下而上)方法，复杂度为O(n)，而使用siftUp 为O (nlogn)，就像在 BST 中一样。

Why can't we apply the same logic and say the time complexity of a balanced binary search tree is also O(n)?

构建堆的自下而上方法不适用于 BST，除非输入列表已经排序，但在这种情况下，由于排序，您已经具有 O(nlogn) 的复杂性。