Двоичное дерево поиска в порядке предшественника сложности пространства

Question

Я изучаю бинарные деревья поиска и не смог найти много информации о пространстве, необходимом для поиска предшественника данного узла.Основываясь на итеративном подходе, я считаю, что мне понадобится пространство O (1) (на месте), потому что нам нужна только одна переменная плюс один узел в стеке.Чтобы выполнить это рекурсивно, мы должны были бы поддерживать стек.Поскольку можно пройти к самому левому / минимальному узлу, возможно, что мы пройдем всю высоту двоичного дерева поиска.Следовательно, сложность пространства для этого будет O (h).

Эти предположения верны или я что-то упустил?

Answer 1

Имейте в виду, что каждый рекурсивный вызов уменьшает высоту, и для каждого значения высоты существует только один вызов. Поэтому мы можем выполнить итеративный поиск.

Пусть n1, n2 будут такими узлами, что n2 является корнем, а n1 является нулем. Пусть v будет тем узлом, который вы ищете

Пока n2 не v:

• n1: = n2
• если v.value> n2.value, n2: = n2.right
• остальное n2: = n.left

возврат n1

Я сохранил постоянное количество (2) указателей, поэтому сложность составляет O(1).