Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

22 байта убрано, 19:18, 31 мая 2015
м
Нет описания правки
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>parent</tex> - , последний посещенный узел, ключ которого больше <tex>x</tex>. Спускаемся вниз по дереву, как в алгоритме поиска узла, обновляя <tex>parent</tex> при переходе к левому потомку (если мы перешли к правому потомку, значит, что ключ в предыдущем узле меньше <tex>x</tex>). Таким образом, мы обойдем всё дерево и найдем элемент с минимальным ключем, большем большим <tex>x</tex>. Аналогично реализуется операция поиска предыдущего элемента.
'''Node''' next(x : '''T'''):
'''Node''' current = root, parent = ''null'' <font color="green">// root {{---}} корень дерева</font>
188
правок

Навигация