Изменения

Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>parent</tex> - , последний посещенный узел, ключ которого больше <tex>x</tex>. Спускаемся вниз по дереву, как в алгоритме поиска узла, обновляя <tex>parent</tex> при переходе к левому потомку (если мы перешли к правому потомку, значит, что ключ в предыдущем узле меньше <tex>x</tex>). Таким образом, мы обойдем всё дерево и найдем элемент с минимальным ключем, большем большим <tex>x</tex>. Аналогично реализуется операция поиска предыдущего элемента.