Изменения
Нет описания правки
if (x.right != null)
return Tree_min(x.right)
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении нулевого указателя нужно подвесить на него вставляемый элемент. Приведем итеративную реализацию этого алгоритма.
=== Удаление ===
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на null. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент(у этого элемента не будет левого потомка) и переместить его на место удаляемого узла.
Tree_delete(root t, root z) // корень дерева, вставляемый элемент
root x, y;
if(z.left == null or z.right == null)
y = z;
else
y = Tree_next(z);
if(y.left != null)
x = y.left;
else
x = y.right;
if(x != null)
x.parent = y.parent;
if(y.parent == null)
t = x;
else
if(y == y.parent.left)
y.parent.left = x;
else
y.parent.right = x;
if(y != z)
z.key = y.key;
z.data = y.data;
return y;
== Литература ==
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
