为什么O（N日志N）构建二进制搜索树？

Question

准备考试。这不是作业问题。

我认为构建BST的最坏情况是O（N^2）。 （每个插入req N-1的比较，你总结所有的比较0 + 1 + ... + N-1〜N^2）。 BST偏斜的情况就是这种情况。 （平衡）BST的插入是O（log N），那么为什么最好的情况是O（N logN）来构造树？

我的猜测最好的猜测 - 因为单个插入是log N，而不是总结所有插入以某种方式给我们N log。

谢谢！

Answer 1

正如你写的:)单一插入是O（log N）。因为N元素的加权树高度是log N，你需要记录N个comparsions来插入单个元素。你需要做N个这些插入。所以N * logN。