Каково амортизированное время нахождения элемента-преемника в бинарном дереве поиска с использованием алгоритма inorder?

Question

Как я могу амортизировать анализ и доказать, что функция-преемник (та, которая находит следующий элемент в алгоритме переупорядочения) принимает в среднем O(1)? Предполагая, что функция-преемник работает с последним найденным элементом. Это даже O(1)? Это O(log n)?

Answer 1

Один из способов думать об этом состоит в том, что N приложений функции-преемника пересекают все дерево. Какова сложность обхода всего дерева? И что это, когда амортизируется через N вызовов функций?