21
правка
Изменения
Нет описания правки
=== Удаление ===
[[Файл:Bst_del1.png|thumb|250px|Удаление листа]]
[[Файл:Bst_del2.png|thumb|250px|Удаление листа]]
[[Файл:Bst_del3.png|thumb|250px|Удаление листа]]
[[Файл:Bst_del4.png|thumb|250px|Удаление листа]]
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на null. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент(у этого элемента не будет левого потомка) и переместить его на место удаляемого узла.
Tree_delete(root t, root z) // корень дерева, вставляемый элемент
z.data = y.data;
return y;
== Литература ==
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
