Блог

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

Верны ли эти предположения или я что-то упускаю?

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

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

В то время как n2 не v :

• n1 := n2
• если v.value > n2.value , n2 := n2.right
• еще n2 := n.left

Возврат n1

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