Представление множеств двоичными деревьями на Прологе



Скачать 155.39 Kb.
Дата30.04.2016
Размер155.39 Kb.

Лабораторная работа на тему: «Представление множеств двоичными деревьями на Прологе»
Цель работы: изучить представление и способы манипулирования с двоичными деревьями в системе логического программирования Turbo Prolog.
Теоретические сведения

Списки часто применяют для представления множеств. Такое использование списков имеет тот недостаток, что проверка принадлежности элемента множеству оказывается довольно неэффективной. Обычно предикат принадлежит( X, L) для проверки принадлежности Х к L программируют так:

принадлежит ( Х, [Х | L] ).

принадлежит ( Х, [ Y | L] ):- принадлежит ( X, L).

Для того чтобы найти Х в списке L, эта процедура последовательно просматривает список элемент за элементом, пока ей не встретится либо элемент Х, либо конец списка. Для длинных списков такой способ крайне неэффективен.

Для более эффективной реализации отношения принадлежности применяют различные древовидные структуры, в частности, двоичные деревья.

Двоичное дерево либо пусто, либо состоит из следующих трех частей:

• корень

• левое поддерево

• правое поддерево

Корень может быть чем угодно, а поддеревья должны сами быть двоичными деревьями. На рис. 1 показа­но представление множества [а, b, c, d] двоичным деревом. Элементы множества хранятся в виде вершин дерева. Пустые поддеревья на рис. 1 не показаны. Например, вершина b имеет два поддерева, которые оба пусты.

Существует много способов представления двоичных деревьев на Прологе. Одна из простых возмож­ностей — сделать корень главным функтором соответ­ствующего терма, а поддеревья — его аргументами. Тогда дерево рис. 1 примет вид

а( b, c(d) )

Такое представление имеет среди прочих своих недостатков то слабое место, что для каждой вершины дерева нужен свой функтор. Это может привести к неприятностям, если вершины сами являются струк­турными объектами.

корень

левое


поддерево правое

поддерево

Рис.1. Двоичное дерево.
Существует более эффективный и более привычный способ представления двоичных деревьев: нам нужен специальный символ для обозначения пустого дерева и функтор для построения непустого дерева из трех компонент (корня и двух поддеревьев). Относительно функтора и специального символа сделаем следую­щий выбор:

Пусть атом empty представляет пустое дерево.

В качестве функтора примем tree, так что дерево с корнем Х, левым поддеревом L и правым поддеревом R будет иметь вид терма tree( L, X, R) (см. рис.2).

В этом представлении дерево рис. 1 выглядит как



tree ( tree( empty, b, empty), а,

tree ( tree ( empty, d, empty), с, empty) ).
tree ( L, X, R)

Рис. 2. Представление двоичных деревьев.


На Турбо-Прологе определение дерева в разделе domains может выглядеть следующим образом:
domains

der = tree ( der, k, der ) ; empty

k = integer
Рассмотрим отношение принадлежности, кото­рое будем обозначать внутри. Цель внутри ( Х, Т ) истинна, если Х есть вершина дерева Т. Отношение внутри можно определить при помощи следующих правил:

Х есть вершина дерева Т, если

  • корень дерева Т совпадает с Х, или

  • Х — это вершина из левого поддерева, или

  • Х — это вершина из правого поддерева.

Эти правила непосредственно транслируются на Пролог следующим образом:

внутри ( Х, tree ( _, Х, _ ) ).

внутри ( Х, tree ( L, _, _ ) ) :- внутри ( X, L).

внутри ( Х, tree ( _, _, R) ) :- внутри ( Х, R).
Очевидно, что цель внутри ( Х, empty) терпит неудачу при любом Х.

Если между элементами множества существует отношение порядка, то можно упорядочить данные в дереве слева направо в соответствии с этим отношением. Будем говорить, что непустое дерево tree ( Лев, Х, Прав) упорядочено слева направо, если



  1. все вершины левого поддерева Лев меньше Х;

  2. все вершины правого поддерева Прав больше Х;

  3. оба поддерева упорядочены.

Будем называть такое двоичное дерево двоичным справочником. Пример показан на рис.3.

Рис. 3. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути

Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в двоичном справоч­нике всегда достаточно просмотреть не более одного поддерева. Экономия при поиске объекта Х достига­ется за счет того, что, сравнив Х с корнем, мы можем сразу же отбросить одно из поддеревьев. Например, пусть мы ищем элемент 6 в дереве, изображенном на рис. 3. Мы начинаем с корня 5, сравни­ваем 6 с 5, получаем 6 > 5. Поскольку все элементы данных в левом поддереве должны быть меньше, чем 5, единственная область, в которой еще осталась возможность найти элемент 6, — это правое поддере­во. Продолжаем поиск в правом поддереве, переходя к вершине 8, и т.д.

Общий метод поиска в двоичном справочнике состоит в следующем:

Для того чтобы найти элемент Х в справочнике Д, необходимо:
• если Х — это корень справочника Д, то счи­тать, что Х уже найден, иначе

• если Х меньше, чем корень, то искать Х в левом поддереве, иначе

• искать Х в правом поддереве;

• если справочник Д пуст, то поиск терпит не­удачу.


Эти правила запрограммированы в виде следующей процедуры:
внутри ( X, tree ( _, X, _ )).

внутри ( X, tree ( Лев, Корень, Прав )):-

больше ( Корень, Х ), % Корень больше, чем Х

внутри ( X, Лев ). % Поиск в левом поддереве
внутри ( X, tree ( Лев, Корень, Прав )):-

больше ( Х, Корень ), % Х больше, чем корень

внутри ( X, Прав ). % Поиск в правом поддереве

Отношение больше ( Х, Y ), означает, что Х больше, чем Y. Если элементы, хранимые в дереве, — это числа, то под «больше, чем» имеется в виду просто Х >Y. Сделаем несколько замечаний отно­сительно эффективности поиска в справочниках. Во­обще говоря, поиск элемента в справочнике эффек­тивнее, чем поиск в списке. Но насколько? Пусть n число элементов множества. Если множество пред­ставлено списком, то ожидаемое время поиска будет пропорционально его длине n. В среднем нам придет­ся просмотреть примерно половину списка. Если мно­жество представлено двоичным деревом, то время по­иска будет пропорционально глубине дерева. Глубина дерева — это длина самого длинного пути между кор­нем и листом дерева. Однако следует помнить, что глубина дерева зависит от его формы

Говорят, что дерево (приближенно) сбаланси­ровано, если для каждой вершины дерева соответ­ствующие два поддерева содержат примерно равное число элементов. Если дерево хорошо сбалансирова­но, то его глубина пропорциональна log n. В этом случае говорят, что дерево имеет логарифмичес­кую сложность. Сбалансированный справочник лучше списка настолько же, насколько log n меньше n. К сожалению, это верно только для приближенно сба­лансированного дерева. Если происходит разбаланси­ровка дерева, то производительность падает. В слу­чае полностью разбалансированных деревьев, дерево фактически превращается в список. Глубина дерева в этом случае равна n, а производительность поиска оказывается столь же низкой, как и в случае спис­ка.

Добавление и удаление элемента в двоичном дереве

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


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

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

удалить( S, Х, S1 ) % Удалить Х из S, результат - S1.
Определим отношение добавить. Простейший спо­соб: ввести новый элемент на самый нижний уровень дерева, так что он станет его листом. Место, на которое помещается новый элемент, выбрать таким образом, чтобы не нарушить упорядоченность дерева. На рис. 4 показано, какие изменения претерпевает дерево в процессе введения в него новых элементов. Назовем такой метод вставки элемента во мно­жество доб_лист ( Д, Х, Д1)
Д1 Д2

Д3




Д4

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

добавить (Д1,6,Д2), добавить (Д2,7,Д3), добавить ( Д3, 4, Д4)
Правила добавления элемента на уровне листьев таковы:

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

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

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

Соответствующая программа имеет вид:
доб_лист ( empty, Х, tree ( empty, Х, empty ) ).

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

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

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

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

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

доб_лист ( Прав, Х, Прав1 ).
Теперь рассмотрим операцию удалить. Лист дерева удалить легко, однако удалить какую—либо внутрен­нюю вершину — дело не простое. К сожалению, если Х — это внутренняя вершина, то возникает проблема, иллюстрацией к которой служит рис. 5. Вершина Х имеет два поддерева Лев и Прав. После удаления вершины Х в дереве образуется «дыра», и поддеревья Лев и Прав теряют свою связь с осталь­ной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способ­на принять только одно из них.


Удалить Х
?

Лев Прав Лев Прав

Рис. 5. Удаление Х из двоичного справочника. Возникает проблема наложения «заплаты» на место удаленного элемента Х.


Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева не пусты, то можно использовать следующую идею (рис. 6): если самую левую вершину Y поддерева Прав перемес­тить из ее текущего положения вверх и заполнить ею пробел, оставшийся после Х, то упорядоченность дерева не нарушится. Разумеется, та же идея срабо­тает и в симметричном случае, когда перемещается самая правая вершина поддерева Лев.

удалить Х переместить

Y


Y

Лев Прав Лев Прав Лев Прав1
Рис. 6. Заполнение пустого места после удаления Х.
Программа, реализующая операцию удаления элементов в соответствии с изложенными выше соображениями, имеет вид:
уд ( tree ( empty, Х, Прав ), Х, Прав ).
уд ( tree ( Лев, Х, empty ), X, Лев ).
уд ( tree ( Лев, Х, Прав ), Х, tree ( Лев, Y, Правl ) ) :-

уд_мин ( Прав, Y, Правl ).

уд ( tree ( Лев, Кор, Прав ), Х, tree ( Лев1, Кор, Прав ) ):-

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

уд ( Лев, X, Лев1 ).
уд ( tree ( Лев, Кор, Прав ), Х, tree ( Лев, Кор, Прав1 ) ) :-

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

уд ( Прав, Х, Правl ).
уд_мин ( tree ( empty, Y, Прав ), Y, Прав ).
уд_мин ( tree ( Лев, Кор, Прав), Y, tree ( Лев1, Кор, Прав ) ) : -

уд_мин ( Лев, Y, Лев1 ).
Основную работу по перемещению самой левой вершины выполняет отноше­ние
уд_мин ( Дер, Y, Дер1 )
Здесь Y — минимальная (т.е. самая левая) вершина дерева Дер, а Дерl — то, во что превращается дере­во Дер после удаления вершины Y.

Отображение деревьев

Так же, как и любые объекты данных в Прологе, двоичное дерево Т может быть непосредственно выве­дено на печать при помощи встроенной процедуры write. Однако цель



write( T)

хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа — пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случа­ях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.

Существует простой способ это сде­лать. Уловка состоит в том, чтобы изображать дере­во растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким обра­зом, чтобы корень стал его крайним слева элемен­том, а листья сдвинулись вправо (рис.7).
а) б)

9

8 7



6

5


4

3

1



Рис. 7. (а) Обычное изображение дерева. (б) То же дерево, отпечатанное процедурой draw (дуги добавлены для ясности).

Определим процедуру



draw ( Т)

так, чтобы она отображала дерево в форме, показан­ной на рис. 7. Принцип работы этой процедуры:

Для того, чтобы отобразить непустое дерево Т, необходимо:


  1. отобразить правое поддерево дерева отступом вправо на расстояние Н;

  2. отпечатать корень дерева Т;

  3. отобразить левое поддерево дерева Т отступом вправо на расстояние Н.

Величина отступа Н, которую можно выбирать по же­ланию, — это дополнительный параметр при отображе­нии деревьев. Введем процедуру


draw2( Т, Н)
печатающую дерево Т с отступом на Н пробелов от левого края листа. Связь между процедурами draw и draw2 такова:
draw ( Т) :— draw2( Т, 0).

Программа отображения имеет вид: (в этой программе предусмотрен сдвиг на 2 позиции для каж­дого уровня дерева )


draw ( Т):- draw2 ( Т, 0 ).
draw2 ( empty, _ ).

draw2 ( tree ( L, X, R ), Oтcтyп ):-

Отступ2 = Отступ + 2,

draw2 ( R, Отступ2 ),

tab ( Отступ), write( X), nl,

draw2 ( L, Отступ2).
В программе использован встроенный оператор nl – перевод строки. Процедуру tab, выполняющую табуляцию на заданное число позиций легко определить.

Задания на лабораторную работу

С помощью процедур работы с деревьями, приведенными в тексте, построить дерево. Отобразить это дерево на экране с помощью процедуры draw, определив предварительно процедуру tab. Выполнить одно из ниже приведенных заданий по указанию преподавателя.

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

глубина ( Дерево, Глубина)
вычисляющую глубину двоичного дерева в пред­положении, что глубина пустого дерева равна 0, а глубина одноэлементного дерева равна 1.
2. Определите отношение

линеаризация ( Дерево, Список)
соответствующее «выстраиванию» всех вершин дерева в список.

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



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

внутри ( Элемент, Справочник)
добавив в нее третий аргумент Путь таким обра­зом, чтобы можно было бы получить путь между корнем справочника и указанным элементом.
5. Определите отношение

min_element ( D, Element )


таким образом, чтобы переменная Element приняла значение наименьшего из элементов дерева D.

Содержание отчета


  1. Наименование и цель выполняемой работы.

  2. Формулировка задания на лабораторную работу.

  3. Текст программы на Turbo Prolog.

  4. Примеры запросов к программе и результаты их выполнения.



Контрольные вопросы




  1. Что представляет собой двоичное дерево?

  2. Что определяет запись tree( L, X, R) ?

  3. Из элементов какого типа состоит двоичное дерево?

  4. Каким образом элементы упорядочены в двоичном дереве?





База данных защищена авторским правом ©refedu.ru 2016
обратиться к администрации

    Главная страница