Изменения

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

insert successor = next(v, t) v.key = successor.key '''if''' successor.parent.left, v== successor successor.parent.left = successor.right) v'''if''' successor.right != ''null'' successor.right.parent = successor.parent '''else''' successor.parent.right = successor.right '''if''' successor.right != ''null'' delete(t, v) successor.right.parent = successor.parent