Изменения

Рассмотрим поиск следующего элемента для некоторого ключа <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>