На этом шаге мы рассмотрим, как удалить вершину из дерева.
Опишем предикат, который будет удалять заданное значение из бинарного дерева. У него будет три аргумента. Два входных (исходное дерево и удаляемое значение) и результат удаления.
Реализовать этот предикат оказывается не так просто, как хотелось бы. Без особых проблем можно удалить элемент, когда он является корневым, а левое или правое поддерево пустое. В этом случае результатом будет, соответственно, правое или левое поддерево.
Когда значение, содержащееся в корне дерева, отличается от удаляемого значения, также реализуется без проблем. Нужно выяснить, меньше удаляемое значение корневого или больше. В первом случае перейти к удалению данного значения из левого поддерева, во втором - к удалению этого значения из правого поддерева.
Проблема возникает, когда нужно удалить корневую вершину в дереве, у которого и левое, и правое поддеревья не пусты.
Есть несколько вариантов разрешения возникшей проблемы. Один из них заключается в следующем. Можно удалить из правого поддерева минимальный элемент (или из левого дерева максимальный) и заменить им значение, находящееся в корне. Так как любой элемент правого поддерева больше любого элемента левого поддерева, дерево, получившееся в результате такого удаления и замены корневого значения, останется бинарным деревом.
Для удаления из дерева вершины, содержащей минимальный элемент, нам понадобится отдельный предикат. Его реализация будет состоять из двух предложений. Первое будет задавать граничное значение рекурсии и срабатывать в случае, когда левое поддерево пусто. В этой ситуации минимальным элементом дерева является значение, находящееся в корне, потому что, по определению бинарного дерева, все значения, находящиеся в вершинах правого поддерева, больше значения, находящегося в корневой вершине. И, значит, нам достаточно удалить корень, а результатом будет правое поддерево.
Второе предложение будет выполняться, когда левое поддерево не пусто. В этой ситуации минимальный элемент находится в левом поддереве и его нужно оттуда удалить. Так как минимальное значение нам потребуется, чтобы вставить его в корневую вершину, у этого предиката будет не два аргумента, как можно было бы ожидать, а три. Третий (выходной) аргумент будет нужен нам для возвращения минимального значения.
Запишем оба эти предиката. Начнем со вспомогательного предиката, удаляющего минимальный элемент бинарного дерева.
delete1 (tr (nil, Y, R), Y, R). /* Если левое поддерево пусто, то минимальный элемент - корень, а дерево без минимального элемента - это правое поддерево.*/ delete1 (tr (L, K, R), Y, tr (L1, K, R)):- delete1 (L, Y, L1). /* Левое поддерево не пусто, значит, оно содержит минимальное значение всего дерева, которое нужно удалить */
Основной предикат, выполняющий удаление вершины из дерева, будет выглядеть следующим образом.
delete (tr (nil, X, R), X, R, 0):-
nl, write ("Элемент из дерева удален.").
/* X совпадает с корневым значением исходного дерева, левое поддерево пусто */
delete (tr (L, X, nil), X, L, 0):-
nl,write("Элемент из дерева удален.").
/* X совпадает с корневым значением исходного дерева, правое поддерево пусто */
delete (T, _, T, 1):-
nl,write ("Такого элемента нет!!!").
/*четвертый аргумент 1, поэтому такого элемента в дереве нет.*/
delete (tr (L, X, R), X, tr (L, Y, R1), _):-
delete1(R,Y,R1).
/* X совпадает с корневым значением исходного дерева, причем ни левое,
ни правое поддеревья не пусты */
delete (tr (L, K, R), X, tr (L1, K, R), H):-
X<K,
delete(L,X,L1,H).
/* X меньше корневого значения дерева */
delete (tr (L, K, R), X, tr (L, K, R1), H):-
X>K,
delete (R, X, R1, H).
/* X больше корневого значения дерева */
На следующем шаге мы рассмотрим программу, реализующую основные операции над деревьями.
