Неизвестно - Prolog

Посмотреть ответ

9. 10. Определите процедуру

глубина( ДвДерево, Глубина)

вычисляющую глубину двоичного дерева в предположении, что глубина пустого дерева равна 0, а глубина одноэлементного дерева равна 1.

Посмотреть ответ

9. 11. Определите отношение

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

соответствующее "выстраиванию" всех вершин дерева в список.

Посмотреть ответ

9. 12. Определите отношение

максэлемент( Д, Элемент)

таким образом, чтобы переменная Элементприняла значение наибольшего из элементов, хранящихся в дереве Д.

Посмотреть ответ

9. 13. Внесите изменения в процедуру

внутри( Элемент, ДвСправочник)

добавив в нее третий аргумент Путьтаким образом, чтобы можно было бы получить путь между корнем справочника и указанным элементом.

Посмотреть ответ

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

9. 3. Двоичные справочники: добавление и удаление элемента

Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из него один из старых. В связи с этим набор основных операций, выполняемых над множеством S, таков:

внутри( X, S) % Х содержится в S

добавить( S, X, S1) % Добавить Х к S, результат - S1

удалить( S, X, S1) % Удалить Х из S, результат - S1

Рис. 9. 9. Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок:

добавить( Д1, 6, Д2), добавить( Д2, 6, Д3), добавить( Д3, 6, Д4)

доблист( nil, X, дер( nil, X, nil) ).

доблист( дер( Лев, Х, Прав), Х, дер( Лев, Х, Прав) ).

доблист( дер( Лев, Кор, Прав), Х, дер( Лев1, Кор, Прав)) :-

больше( Кор, X),

доблист( Лев, X, Лев1)).

доблист( дер( Лев, Кор, Прав), Х, дер( Лев, Кор, Прав1)) :-

больше( X, Кор),

доблист( Прав, X, Прав1).

Рис. 9. 10. Вставление в двоичный справочник нового элемента в качестве листа.

Определим отношение добавить . Простейший способ: ввести новый элемент на самый нижний уровень дерева, так что он станет его листом. Место, на которое помещается новый элемент, выбрать таким образом, чтобы не нарушить упорядоченность дерева. На рис. 9.9 показано, какие изменения претерпевает дерево в процессе введения в него новых элементов. Назовем такой метод вставления элемента в множество

доблист( Д, X, Д1)

Правила добавления элемента на уровне листьев таковы:

Результат добавления элемента Х к пустому дереву есть дерево дер( nil, X, nil).

Если Х совпадает с корнем дерева Д, то Д1 = Д (в множестве не допускается дублирования элементов).

Если корень дерева Д больше, чем X, то Х вносится в левое поддерево дерева Д; если корень меньше, чем X, то Х вносится в правое поддерево.

На рис. 9.10 показана соответствующая программа.

Теперь рассмотрим операцию удалить . Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину - дело не простое. Удаление листа можно на самом деле определить как операцию, обратную

Рис. 9. 11. Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.

операции добавления листа:

удлист( Д1, X, Д2) :-

доблист( Д2, X, Д1).

К сожалению, если Х - это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит рис. 9.11. Вершина Х имеет два поддерева Леви Прав. После удаления вершины Х в дереве образуется "дыра", и поддеревья Леви Правтеряют свою связь с остальной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способна принять только одно из них.

Если одно из поддеревьев Леви Правпусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты,

Рис. 9. 12. Заполнение пустого места после удаления X.