Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

207 байт добавлено, 21:05, 22 марта 2011
Нет описания правки
=== Удаление ===
[[Файл: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;
[[Файл:Bst_del1.png‎|thumb|250px|Удаление листа]]
== Литература ==
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
21
правка

Навигация