准备考试。这不是作业问题。
我认为最坏的情况是 O(N^2) 来构建 BST。 (每次插入 req N-1 比较，您将所有比较相加 0 + 1 + ... + N-1 ~ N^2)。这就是偏斜 BST 的情况。
(平衡)BST 的插入是 O(log N)，那么为什么最好的情况是 O(N logN) 来构造树？
我的猜测最好的猜测 - 因为单次插入是 log N，而不是总和所有插入以某种方式给我们 N log。
谢谢 !
最佳答案
正如您所写:) 单次插入是 O(log N)。因为 N 元素的加权树高度是 log N，所以您需要最多对 log N 次比较才能插入单个元素。您需要进行 N 次这些插入。所以 N*logN。
关于binary-tree - 为什么 O(N Log N) 构建二叉搜索树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5142653/