algorithm - 在给定范围内打印 BST 键

Question

我试图了解在给定范围内打印 BST 密钥的运行时间。我试图从这个例子中理解它，但我做不到。

我想我明白它的O(log n)来源。那是递归地通过BST，这将O(log n)适用于每一方，但我不确定：

1. 是从哪里来K的。它只是打印所需的恒定时间吗？如果是，为什么运行时不是O(log n)+ O(k)，而不是你会忽略 K

2. O(n)from in order 遍历在哪里？因为它不在这个运行时。

3. 如果我们在树的每一侧的范围内都有多个值，运行时将如何变化。例如，如果范围从 4 开始呢？

Answer 1

理解解决方案的更简单方法是考虑以下算法：

1. 在 BST 树中搜索大于键 k1 的最小值 - O(lgn)
2. 从 k1 按顺序遍历 BST 树节点，直到我们到达小于或等于 k2 的节点，并打印它们的键。因为完整的 BST 的中序遍历需要 O(n) 时间，如果 k1 和 k2 之间有 k 个键，则中序遍历需要 O(k) 时间。

给定的算法正在做同样的事情；在 k1 和 k2 之间搜索一个键需要 O(lgn) 时间，而打印只对 k1 和 k2 范围内的 k 个键进行，即 O(k)。如果所有 BST 密钥都位于 k1 和 k2 内，则运行时间将为 O(lgn) + O(n) = O(n)，因为需要打印出所有 n 个密钥。