Изменения

Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>parentsuccessor</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. <br>Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла <tex>current</tex>. Если <tex>current.key \leq leqslant x</tex>, значит искомый следующий за <tex>x</tex> узел находится в правом поддереве (в левом поддереве все ключи меньше <tex>current.key</tex>). Если же <tex>x < current.key </tex>, то <tex> x< next(x) \leqslant current.key</tex>, значит либо поэтому <tex>current</tex> {{---}} искомый узел (сохраним его в может быть следующим для ключа <tex>parentx</tex> как возможный ответ), либо искомый следующий узел содержится в левом поддереве<tex>current</tex>. Перейдем к нужному поддереву и повторим те же самые действия. Таким образом, каждый раз, переходя в левое поддерево, мы будем уменьшать ответ (ключ узла <tex>parent</tex> будет уменьшаться после каждого обновления). В конце обхода, по достижении листа, в <tex>parent</tex> будет находиться узел с минимальным ключем, большим <tex>x</tex>.<br>

'''Node''' current = root, parent successor = ''null'' <font color="green">// root {{---}} корень дерева</font>

parent successor = current

'''return''' parentsuccessor

'''if''' v.parent == ''null'' delete(t = v.left; '''else if''' v.parent.left == v v.parent.left = v.left '''else''' v.parent.right = , v.left)

'''return''' root

root.right = remove(root.right, z)

root.key = minimum(root.right).key root.right = remove(root, root.right)

'''if''' root.left != ''null'' root = t.left '''else''' root = t.right