Программирование на языке Пролог для искусственного интеллекта
Шрифт:
добавив в нее третий аргумент
9.3. Двоичные справочники: добавление и удаление элемента
Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из него один из старых. В связи с этим набор основных операций, выполняемых над множеством S, таков:
Рис. 9.9. Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок:
Рис. 9.10. Вставление в двоичный справочник нового элемента в качестве листа.
Определим отношение добавить. Простейший способ: ввести новый элемент на самый нижний уровень дерева, так что он станет его листом. Место, на которое помещается новый элемент, выбрать таким образом, чтобы не нарушить упорядоченность дерева. На рис. 9.9 показано, какие изменения претерпевает дерево в процессе введения в него новых элементов. Назовем такой метод вставления элемента в множество
Правила добавления элемента на уровне листьев таковы:
• Результат добавления элемента X к пустому дереву есть дерево
• Если X совпадает с корнем дерева Д, то Д1 = Д (в множестве не допускается дублирования элементов).
• Если корень дерева Д больше, чем X, то X вносится в левое поддерево дерева Д; если корень меньше, чем X, то X вносится в правое поддерево.
На рис. 9.10 показана соответствующая программа.
Теперь рассмотрим операцию удалить. Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину — дело не простое. Удаление листа можно на самом деле определить как операцию, обратную операции добавления листа:
Рис. 9.11. Удаление X
К сожалению, если X — это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит рис. 9.11. Вершина X имеет два поддерева
Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты, то можно использовать следующую идею (рис. 9.12): если самую левую вершину Y поддерева
Рис. 9. 2. Заполнение пустого места после удаления X.
На рис. 9.13 показана программа, реализующая операцию удаления элементов в соответствии с изложенными выше соображениями. Основную работу по перемещению самой левой вершины выполняет отношение
Здесь Y — минимальная (т.е. самая левая) вершина дерева
Существует другой, элегантный способ реализация операции добавить и удалить. Отношение добавить можно сделать недетерминированным в том смысле, что новый элемент вводится на произвольный уровень дерева, а не только на уровень листьев. Правила таковы:
Для того, чтобы добавить X в двоичный справочник Д, необходимо одно из двух:
• добавить X на место корня дерева (так, что X станет новым корнем) или
• если корень больше, чем X, то внести X в левое поддерево, иначе — в правое поддерево.