Q

基于比较的二叉搜索树构建算法可以采用多快？

2016-07-15 66 views 0 likes

0

我们知道遍历二叉搜索树的顺序将在O（n）时间按排序顺序列出树的元素。但基于比较的二叉搜索树构造算法可以采用多快？基于比较的二叉搜索树构建算法可以采用多快？

2016-07-15 junjunbaobao

+1

你知道任何关于需要插入到二叉树中的元素还是随机化的？ –

+2

未指定。如果输入已经排序，则可以在* O（N）*时间内完成。 Knuth Vol 3，＃6.2.3练习21. – EJP

+0

确实@NickLarsen看起来不错！花费的时间将取决于输入元素的大小和顺序。 –

A

回答

0

最坏的情况下，我认为最长的运行时间是O（log n）。

2016-07-15 17:57:47

相关问题