Изменения

Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>parent</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. Спускаемся вниз по дереву, как в алгоритме поиска узла, обновляя . Рассмотрим ключ текущего узла <tex>current</tex>. Если <tex>parentcurrent.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>. Аналогично реализуется операция поиска предыдущего элемента.

'''func''' insert(x : '''Node''', z : '''TNode'''): <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый ключэлемент</font> '''while''' x != ''null'' '''if''' z .key > x.key '''if''' x.right != ''null'' insert( x = x.right, z) '''else''' '''Node''' y y z.parent = x y x.key right = z x.right = y '''break''' '''else if''' z .key < x.key '''if''' x.left != ''null'' insert( x = x.left, z) '''else''' '''Node''' y y z.parent = x y x.key left = z x.left = y '''break'''

'''funcNode''' insert(x : '''Node''', z : '''T'''): <font color="green">// x {{---}} корень поддерева, z {{---}} вставляемый ключ</font>

x = '''return''' Node(z) <font color="green">// подвесим Node с key = z</font>

x.left = insert(x.left, z)

x.right = insert(x.right, z) '''return''' x

Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на <tex>null</tex>. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом(для упрощения реализации, можно использовать функцию, вставляющую узел в дерево, и вставить правый дочерний узел в левое поддерево). Таким образом, свойство бинарного дерева поиска не будет нарушено. Время работы алгоритма {{---}} <tex>O(h)</tex>.

successor = nextinsert(v.left, tv.right) v.key right = successor.key''null'' '''if''' successorv.parent.left == successor''null'' successor.parent t = v.left = successor.right; '''else if''' successorv.right !parent.left == ''null''v successor v.rightparent.parent left = successorv.parentleft

successor v.parent.right = successorv.right '''if''' successor.right != ''null'' successor.right.parent = successor.parentleft