asymptotic 运行 打印红黑树中所有落在一定范围内的key的时间
asymptotic running time of printing all keys in a red-black tree that fall in a certain range
我正在做 CLRS 的练习 14.2-4（算法介绍 3ed）：
We wish to augment red-black trees with an operation RB-ENUMERATE(x, a, b) that outputs all the keys k such that a ≤ k ≤ b in a red-black tree rooted at x. Describe how to implement RB-ENUMERATE in Θ(m + lg n) time, where m is the number of keys that are output and n is the number of internal nodes in the tree. (Hint, you do not need to add new attributes to the red-black tree.)
我找到了一个algorithm in a solution online，似乎做的不错，但我不知道复杂度是否真的是Θ(m + lg n)。
RB-ENUMERATE(x, a, b)
T = red-black tree that x belongs in
nil = T.nil // sentinel NIL leaf node
if a <= x.key <= b
print(x)
if a <= x.key and x.left != nil
RB-ENUMERATE(x.left, a, b)
if x.key <= b and x.right != nil
RB-ENUMERATE(x.right, a, b)
这个递归算法真的是Θ(m + lg n) 运行次，还是这个算法不满足那个要求？我知道 lg n 的来源，但我担心 m = Θ(lg n) 的情况，但 运行 时间渐近地大于 lg n。
特别地，在RB-ENUMERATE的每次调用中，如果x落在区间内则发生2次递归调用，或者如果x不落在区间内则发生1次递归调用。因此，恰好有 m "instances" 个 RB-ENUMERATE 进行了 2 次递归调用，但是进行了 1 次递归调用的数目不清楚。如果所有 m 个“2-递归”调用都发生在递归树的上层，并且它们都一直向下传播到红黑树的底部怎么办？那样的话，不就是Θ(m lg n)运行次吗？
即使一个节点在区间内，也可以有 0、1 或 2 次递归调用。黑色节点的一侧可以有一个红色节点，而另一侧可以有一个 nil 节点（哪一侧是哪一侧并不重要）。一个红色节点会有两个黑色children。这将匹配是否为零。
最多需要 lg(n) 次操作来确定从哪里开始打印，然后需要 m 次操作来打印感兴趣的节点，然后停止。该算法实际上可以比严格的 lg(n) 做得更好，因为它可能不必在找到修剪点之前一直沿着树向下走。
我正在做 CLRS 的练习 14.2-4（算法介绍 3ed）：
We wish to augment red-black trees with an operation RB-ENUMERATE(x, a, b) that outputs all the keys k such that a ≤ k ≤ b in a red-black tree rooted at x. Describe how to implement RB-ENUMERATE in Θ(m + lg n) time, where m is the number of keys that are output and n is the number of internal nodes in the tree. (Hint, you do not need to add new attributes to the red-black tree.)
我找到了一个algorithm in a solution online，似乎做的不错，但我不知道复杂度是否真的是Θ(m + lg n)。
RB-ENUMERATE(x, a, b)
T = red-black tree that x belongs in
nil = T.nil // sentinel NIL leaf node
if a <= x.key <= b
print(x)
if a <= x.key and x.left != nil
RB-ENUMERATE(x.left, a, b)
if x.key <= b and x.right != nil
RB-ENUMERATE(x.right, a, b)
这个递归算法真的是Θ(m + lg n) 运行次，还是这个算法不满足那个要求？我知道 lg n 的来源，但我担心 m = Θ(lg n) 的情况，但 运行 时间渐近地大于 lg n。
特别地，在RB-ENUMERATE的每次调用中，如果x落在区间内则发生2次递归调用，或者如果x不落在区间内则发生1次递归调用。因此，恰好有 m "instances" 个 RB-ENUMERATE 进行了 2 次递归调用，但是进行了 1 次递归调用的数目不清楚。如果所有 m 个“2-递归”调用都发生在递归树的上层，并且它们都一直向下传播到红黑树的底部怎么办？那样的话，不就是Θ(m lg n)运行次吗？
即使一个节点在区间内，也可以有 0、1 或 2 次递归调用。黑色节点的一侧可以有一个红色节点，而另一侧可以有一个 nil 节点（哪一侧是哪一侧并不重要）。一个红色节点会有两个黑色children。这将匹配是否为零。
最多需要 lg(n) 次操作来确定从哪里开始打印，然后需要 m 次操作来打印感兴趣的节点，然后停止。该算法实际上可以比严格的 lg(n) 做得更好，因为它可能不必在找到修剪点之前一直沿着树向下走。