Изменения

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

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

8 байт добавлено, 17:14, 1 июня 2015
м
Нет описания правки
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>parent</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. <br>Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла <tex>current</tex>. Если <tex>current.key \leq x</tex>, значит искомый узел находится в правом поддереве (в левом поддереве все ключи меньше <tex>current.key</tex>). Если <tex>current.key > x</tex>, значит либо <tex>current</tex> {{---}} искомый узел (сохраним его в <tex>parent</tex> как возможный ответ), либо искомый узел содержится в левом поддереве. Перейдем к нужному поддереву и повторим те же самые действия. Таким образом, каждый раз, переходя в левое поддерево, мы будем уменьшать ответ (ключ узла <tex>parent</tex> будет уменьшаться после каждого обновления). В конце обхода, по достижении листа, в <tex>parent</tex> будет находиться узел с минимальным ключем, большим <tex>x</tex>.<br>
Аналогично реализуется операция поиска предыдущего элемента.
'''Node''' next(x : '''T'''):
188
правок

Навигация