algorithm - BST O(NLogN) 构建证明

Question

我正在尝试学习测试，我知道单次插入是 O(logn) 并且树的高度是 n，因此比较将使时间成为 Ω(n log n)。

我如何证明，给定一个包含 n 个元素的未排序数组 A，构建 BST 所需的时间在最坏情况下为 Ω(n log n)。

Answer 1

遍历 BST 可以在线性时间内完成，所以如果你可以比 O(n * log(n)) 更快地从未排序的数组构建 BST，这意味着你可以比 O(n * log(n)) 并且我们知道 this can't be done除非您有关于被排序元素的额外信息。

另一方面，您可以在 Ω(n*log(n)) 中对数组进行排序，并且可以在线性时间内从排序的数组构建 BST(例如构建“类列表”树)。