Доказать эффективность повторных обращений к successor () в двоичных деревьях?

Question

Мне нужна подсказка для этого упражнения из книги Алгоритмы CLRS:

Докажите, что независимо от того, с какого узла мы начинаем в дереве бинарного поиска высоты-h, k последовательных вызовов Tree-Successor занимают O (k + h) время.

Answer 1

• Пусть x будет начальным узлом, а z будет конечным узлом после k последовательных вызовов TREE-SUCCESSOR.
• Пусть p будет простым путем между x и z включительно.
• Пусть y будет общим предком x и z, который посещает p.
• Длина p не более2h, то есть O(h).
• Пусть output будут элементами, значения которых находятся между x.key и z.key включительно.
• Размер output равенO(k).
• При выполнении k последовательных вызовов TREE-SUCCESSOR посещаются узлы, которые находятся в p, и кроме узлов x, y и zесли посещено поддерево узла в p, то все его элементы находятся в output.
• Таким образом, время выполнения составляет O(h+k).

Answer 2

Подсказка: отработайте небольшой пример, посмотрите на результат, попробуйте экстраполировать причину.

Для начала рассмотрим некоторые вещи.

Начните с определенного узла, k последовательных вызовов Tree-Succcesor составляет частичную прогулку по дереву. Сколько (по крайней мере и максимум) узлов посещает эта прогулка? (Подсказка: подумайте о ключе (x)). Помните, что край посещается максимум дважды (почему?).

Последний совет: результат O(2h+k).