打印给定范围内的BST键

我想了解打印BST键在给定范围内的运行时间。我试图从this example了解它，但我不能。打印给定范围内的BST键

我想我明白O(log n)是从哪里来的。这是从通过BST去递归，这将需要O(log n)每边，但我不知道：

2013-02-23 Quantico

K是打印的项目数。无论你多快找到开始和结束，你都必须打印所有的项目。您需要打印的项目越多，需要的时间就越长。 – 2013-02-23 14:47:33

有用，当你有一个常数，你说'O（某个值）'+'O（C）'，并忽略C因为它渐近较小。为什么我们在这种情况下将这个添加到我们的'O（log）'中？ – Quantico 2013-02-23 14:49:43

K不是一个常数。它根据输入而变化。 – 2013-02-23 14:51:29

更简单的方法来了解该解决方案是要考虑下面的算法：

搜索在BST树的最小值比关键k1更大 - O（LGN）
在执行从k1开始遍历BST树节点，直到我们到达小于或等于k2的节点，并打印它们的键。因为完整BST的有序遍历需要O（n）次，所以如果k1和k2之间有k个密钥，按顺序遍历需要O（k）次。

给定的算法是做同样的事情;搜索k1和k2之间的关键字需要O（lgn）时间，而仅对k（k）范围内的k个关键点进行打印，该范围是O（k）。如果所有BST键位于k1和k2内，运行时间将为O（lgn）+ O（n）= O（n），因为所有n个键都需要打印出来。

2013-02-24 04:13:17 Faraz

回答