Я работаю над упражнением 14.2-4 CLRS (Введение в алгоритмы 3ed):
Мы хотим дополнить красно-черные деревья операцией RB-ENUMERATE(x, a, b), которая выводит все ключи k такие, что a ≤ k ≤ b в красно-черном дереве с корнем x. Опишите, как реализовать RB-ENUMERATE за время Θ(m + lg n), где m — количество выводимых ключей, а n — количество внутренних узлов в дереве. (Подсказка, вам не нужно добавлять новые атрибуты в красно-черное дерево.)
Я нашел алгоритм в онлайн-решении, который, кажется, делает работает хорошо, но я не могу сказать, действительно ли сложность равна Θ(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 есть либо 2 рекурсивных вызова, которые происходят, если x попадает в интервал, либо 1 рекурсивный вызов, который происходит, если x не попадает в интервал. Следовательно, существует ровно m «экземпляров» RB-ENUMERATE, которые делают 2 рекурсивных вызова, но число, которое делает 1 рекурсивный вызов, неясно. Что, если все m «2-рекурсивных» вызовов происходят на верхних уровнях дерева рекурсии, и все они распространяются вниз до основания красно-черного дерева? В таком случае не будет ли это время работы Θ(m lg n)?
