3622
правки
Изменения
м
→Нерекурсивная реализация
| [[Файл:Bst_del3.png|900px]]
|}
'''func''' delete(t : '''Node''', v : '''Node'''): <font color="green">// <tex>t</tex> {{---}} дерево и , <tex>v</tex> {{---}} удаляемый элемент</font>
p = v.parent <font color="green">// предок удаляемого элемента</font>
'''if''' v.left == ''null'' '''and''' v.right == ''null'' <font color="green">// первый случай: удаляемый элемент - лист</font>
'''if''' successor.right != ''null''
successor.right.parent = successor.parent
====Рекурсивная реализация====
При рекурсивном удаления узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
