Замечания в некоторых альтернативных способах представления списков
9. 1. 1. Замечания в некоторых альтернативных способах представления списков
В главе 3 была введена специальная система обозначений для списков (специальная прологовская нотация), которую мы и использовали в последующем изложении. Разумеется, это был всего лишь один из способов представления списков на Прологе. Список - это, в самом общем смысле, структура, которая либо пуста, либо состоит из головы и хвоста, причем хвост должен быть сам списком.
Поэтому для представления этой структуры нам необходимо иметь всего лишь два языковых средства: специальный символ, обозначающий пустой список, и функтор для соединения головы с хвостом. Мы могли бы, например, выбрать
ничего_не_делать
в качестве символа, обозначающего пустой список, и атом
затем
в качестве инфиксного оператора для построения списка по заданным голове и хвосту. Этот оператор мы можем объявить в программе, например, так:
:- ор( 500, xfy, затем).
Список
[ войти, сесть, поужинать]
можно было бы тогда записать как
войти затем сесть затем поужинать
затем ничего_не_делать
Важно заметить, что на соответствующем уровне абстракции специальная прологовская нотация и всевозможные альтернативные способы обозначения списков сводятся, фактически, к одному и тому же представлению. В связи с этим типовые операции над списками, такие как
принадлежит ( X, L)
конк( L1, L2, L3)
удалить( X, L1, L2)
запрограммированные нами в специальной прологовской нотации, легко поддаются перепрограммированию в различные системы обозначений, выбранные пользователем. Например, отношение конк транслируется на язык "затем - ничего_не_делать" следующим образом. Определение, которое мы использовали до сих пор, имеет вид
конк( [ ], L, L).
конк( [X | L1], L2, [X | L3] ) :-
конк( L1, L2, L3).
В новой системе обозначений оно превращается в
конк( ничего_не_делать, L, L).
конк( Х затем L1, L2, Х затем L3) :-
конк(L1, L2, L3).
Этот пример показывает, как легко наши определения отношений над списками обобщаются на весь класс структур этого типа. Решение о том, какой именно способ записи списков будет использоваться в той или иной программе, следует принимать в соответствии с тем смыслом, который мы придаем списку в каждом конкретном случае. Если, например, список - это просто множество элементов, то наиболее удобна обычная прологовская нотация, поскольку в ней непосредственно выражается то, что программист имел в виду. С другой стороны, некоторые типы выражений также можно трактовать как своего рода списки. Например, для конъюнктов в исчислении высказываний подошло бы следующее спископодобное представление:
истина соответствует пустому списку,
& - оператор для соединения головы с хвостом, определяемый, например, как
:- ор( 300, xfy, &)
Конъюнкция членов а, b, и с выглядела бы тогда как
а & b & с & истина
Все приведенные примеры базируются, по существу, на одной и той же структуре, представляющей список. Однако в гл. 8 мы рассмотрели существенно другой способ, влияющий на эффективность вычислений. Уловка состояла в том, что список представлялся в виде пары списков, являясь их "разностью". Было показано, что такое представление приводит к очень эффективной реализации отношения конкатенации.
Материал настоящего раздела проливает свет и на то различие, которое существует между применением операторов в математике и применением их в Прологе. В математике с каждым оператором всегда связано некоторое действие, в то время как в Прологе операторы используются просто для представления структур.
Сортировка списков
9. 1. 2. Сортировка списков
Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядка
больше( X, Y)
означающее, что Х больше, чем Y, независимо от того, что мы в действительности понимаем под "больше, чем". Если элементами списка являются числа, то отношение больше будет, вероятно, определено как
больше( X, Y) := Х > Y.
Если же элементы списка - атомы, то отношение больше может соответствовать алфавитному порядку между ними.
Пусть
сорт( Спис, УпорСпис)
обозначает отношение, в котором Спис - некоторый список, а УпорСпис - это список, составленный из тех же элементов, но упорядоченный по возрастанию в соответствия с отношением больше. Мы построим три определения этого отношения на Прологе, основанные на трех различных идеях о механизме сортировки. Вот первая идея:
line();Для того, чтобы упорядочить список Спис, необходимо: Найти в Спис два смежных элемента Х и Y, таких, что больше( X, Y), и поменять Х и Y местами, получив тем самым новый список Спис1; затем отсортировать Спис1. Если в Спис нет ни одной пары смежных элементов Х и Y, таких, что больше( X, Y), то считать, что Спис уже отсортирован. line();
Мы переставили местами 2 элемента X и Y, расположенные в списке "не в том порядке", с целью приблизить список к своему упорядоченному состоянию. Имеется в виду, что после достаточно большого числа перестановок все элементы списка будут расположены в правильном порядке. Описанный принцип сортировки принято называть методом пузырька, поэтому соответствующая прологовская процедура будет называться пузырек.
пузырек( Спис, УпорСпис) :-
перест( Спис, Спис1), !,
% Полезная перестановка ?
пузырек( Спис1, УпорСпис).
пузырек( УпорСпис, УпорСпис).
% Если нет, то список уже упорядочен
перест( [Х, Y | Остаток], [Y, Х ) Остаток] ):-
% Перестановка первых двух элементов
больше( X, Y).
перест( [Z | Остаток], [Z | Остаток1] ):-
перест( Остаток, Остаток1). % Перестановка в хвосте
Еще один простой алгоритм сортировки называется сортировкой со вставками. Он основан на следующей идее:
line();Для того, чтобы упорядочить непустой список L = [X | Хв], необходимо:
(1) Упорядочить хвост Хв списка L.
(2) Вставить голову Х списка L в упорядоченный хвост, поместив ее в такое место, чтобы получившийся список остался упорядоченным. Список отсортирован.
line();Этот алгоритм транслируется в следующую процедуру вставсорт на Прологе:
вставсорт([ ], [ ]).
вставсорт( [X | Хв], УпорСпис) :-
вставсорт( Хв, УпорХв),
% Сортировка хвоста
встав( X, УпорХв, УпорСпис).
% Вставить Х на нужное место
Представление списков Сортировка
9. 1. Представление списков. Сортировка
Представление множеств двоичными деревьями
9. 2. Представление множеств двоичными деревьями
Списки часто применяют для представления множеств. Такое использование списков имеет тот недостаток, что проверка принадлежности элемента множеству оказывается довольно неэффективной. Обычно предикат принадлежит( X, L) для проверки принадлежности Х к L программируют так:
принадлежит X, [X | L] ).
принадлежит X, [ Y | L] ) :-
принадлежит( X, L).
Для того, чтобы найти Х в списке L, эта процедура последовательно просматривает список элемент за элементом, пока ей не встретится либо элемент X, либо конец списка. Для длинных списков такой способ крайне неэффективен.
Для облегчения более эффективной реализация отношения принадлежности применяют различные древовидные структуры. В настоящем разделе мы рассмотрим двоичные деревья.
Двоичное дерево либо пусто, либо состоит из следующих трех частей: корень левое поддерево правое поддерево
Корень может быть чем угодно, а поддеревья должны сами быть двоичными деревьями. На Рисунок 9.4 показано представление множества [а, b, с, d] двоичным деревом. Элементы множества хранятся в виде вершин дерева. Пустые поддеревья на Рисунок 9.4 не показаны. Например, вершина b имеет два поддерева, которые оба пусты.
Существует много способов представления двоичных деревьев на Прологе. Одна из простых возможностей - сделать корень главным функтором соответствующего терма, а поддеревья - его аргументами. Тогда дерево Рисунок 9.4 примет вид
а( b, с( d) )
Такое представление имеет среди прочих своих недостатков то слабое место, что для каждой вершины дерева нужен свой функтор. Это может привести к неприятностям, если вершины сами являются структурными объектами.
Двоичные справочники добавление и удаление элемента
9. 3. Двоичные справочники: добавление и удаление элемента
Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из него один из старых. В связи с этим набор основных операций, выполняемых над множеством S, таков:
внутри( X, S) % Х содержится в S
добавить( S, X, S1) % Добавить Х к S, результат - S1
удалить( S, X, S1) % Удалить Х из S, результат - S1
Отображение деревьев
9. 4. Отображение деревьев
Так же, как и любые объекты данных в Прологе, двоичное дерево Т может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель
write( Т)
хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа - пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.
Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (Рисунок 9.16).
Представление графов
9. 5. 1. Представление графов
Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество вершин вместе с множеством ребер, причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения. На Рисунок 6.18 показаны примеры графов.
В Прологе графы можно представлять различными способами. Один из них - каждое ребро записывать в виде отдельного предложения. Например, графы, показанные иа Рисунок 9.18, можно представить в виде следующего множества предложений:
связь( а, b).
связь( b, с).
. . .
дуга( s, t, 3).
дуга( t, v, 1).
дуга( u, t, 2).
. . .
Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро - парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра - функтор р. Тогда (ненаправленный) граф Рисунок 9.18 примет вид:
G1 = граф( [a, b, c, d],
[р( а, b), р( b, d), р( b, с), p( c, d)] )
Поиск пути в графе
9. 5. 2. Поиск пути в графе
Пусть G - граф, а А и Z - две его вершины. Определим отношение
путь( А, Z, G, Р)
где Р - ациклический путь между А и Z в графе G. Если G - граф, показанный в левой части Рисунок 9.18, то верно:
путь( a, d, G, [a, b, d] )
путь( а, d, G, [a, b, c, d] )
Поскольку путь не должен содержать циклов, любая вершина может присутствовать в пути не более одного раза. Вот один из методов поиска пути:
line();Для того, чтобы найти ациклический путь Р между А и Z в графе G, необходимо:
Если А = Z , то положить Р = [А], иначе найти ациклический путь Р1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из Р1.
line();В этой формулировке неявно предполагается, что существует еще одно отношение, соответствующее поиску пути со следующий ограничением: путь не должен проходить через вершины из некоторого подмножества (в данном случае Р1) множества всех вершин графа. В связи с этим мы определим ещё одну процедуру:
путь1( А, Р1, G, Р)
Аргументы в соответствии с Рисунок 9.19 имеют следующий смысл: А - некоторая вершина,
Построение остовного дерева
9. 5. 3. Построение остовного дерева
Граф называется связным, если между любыми двумя его вершинами существует путь. Пусть G = (V, Е) - связный граф с множеством вершин V и множеством ребep Е. Остовное дерево графа G - это связный граф Т = ( V, Е'), где Е' - подмножество Е такое, что
(1) Т - связный граф,
(2) в Т нет циклов.
Выполнение этих двух условий гарантирует то, что Т - дерево. Для графа, изображенного в левой части Рисунок 9.18, существует три остовных дерева, соответствующих следующим трем спискам ребер:
Дер1 = [а-b, b-c, c-d]
Дер2 = [а-b, b-d, d-с]
Дер3 = [а-b, b-d, b-c]
Здесь каждый терм вида X-Y обозначает ребро, соединяющее вершины Х и Y. В качестве корня можно взять любую из вершин, указанных в списке. Остовные деревья представляют интерес, например в задачах проектирования сетей связи, поскольку они позволяют, имея минимальное число линий, установить связь между любыми двумя узлами, соответствующими вершинам графа.
Определим процедуру
остдерево( G, Т)
где Т - остовное дерево графа G. Будем предполагать, что G - связный граф. Можно представить себе алгоритмический процесс построения остовного дерева следующим образом. Начать с пустого множества ребер и постепенно добавлять новые ребра, постоянно следя за тем, чтобы не образовывались циклы. Продолжать этот процесс до тех пор, пока не обнаружится, что нельзя присоединить ни одного ребра, поскольку любое новое ребро порождает цикл. Полученное множество ребер будет остовным деревом. Отсутствие циклов можно обеспечить, если придерживаться следующего простого правила: ребро присоединяется к дереву только в том случае, когда одна из его вершин уже содержится в строящемся дереве, а другая пока еще не включена в него. Программа, реализующая эту идею, показана на Рисунок 9.22. Основное отношение, используемое в этой программе, - это
расширить( Дер1, Дер, G)
Здесь все три аргумента - множества ребер. G -
line();% Построение остовного дерева графа
%
% Деревья и графы представлены списками
% своих ребер, например:
% Граф = [а-b, b-с, b-d, c-d]
остдерево( Граф, Дер) :-
% Дер - остовное дерево Граф'а
принадлежит( Ребро, Граф),
расширить( [Ребро], Дер, Граф).
расширить( Дер1, Дер, Граф) :-
добребро( Дер1, Дер2, Граф),
расширить( Дер2, Дер, Граф).
расширить( Дер, Дер, Граф) :-
not добребро( Дер, _, Граф).
% Добавление любого ребра приводит к циклу
добребро( Дер, [А-В | Дер], Граф) :-
смеж( А, В, Граф),
% А и В - смежные вершины
вершина( А, Дер).
% А содержится в Дер
не вершина( В, Дер).
% А-В не порождает цикла
смеж( А, В, Граф) :-
принадлежит ( А-В, Граф);
принадлежит ( В-А, Граф).
вершина( А, Граф) :-
% А содержится в графе, если
смеж( А, _, Граф).
% А смежна какой-нибудь вершине
Pис. 9. 22. Построение остовного дерева: алгоритмический подход.
Предполагается, что Граф - связный граф.
связный граф; Дер1 и Дер - два подмножества G, являющиеся деревьями. Дер - остовное дерево графа G, полученное добавлением некоторого (может быть пустого) множества ребер из G к Дер1. Можно сказать, что "Дер1 расширено до Дер".
Интересно, что можно написать программу построения остовного дерева совершенно другим, полностью декларативным способом, просто формулируя на Прологе некоторые математические определения. Допустим, что как графы, так и деревья задаются списками своих ребер, как в программе Рисунок 9.22. Нам понадобятся следующие определения:
(1) Т является остовным деревом графа G, если Т - это подмножество графа G и Т - дерево и Т "накрывает" G, т.е. каждая вершина из G содержится также в Т.
(2) Множество ребер Т есть дерево, если Т - связный граф и Т не содержит циклов.
Эти определения можно сформулировать на Прологе (с использованием нашей программы путь из предыдущего раздела) так, как показано на Рисунок 9.23. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.
line();% Построение остовного дерева
% Графы и деревья представлены списками ребер.
остдерево( Граф, Дер) :-
подмнож( Граф, Дер),
дерево( Дер),
накрывает( Дер, Граф).
дерево( Дер) :-
связи( Дер),
not имеетцикл( Дер).
связи( Дер) :-
not ( вершина( А, Дер), вершина( В, Дер),
not путь( А, А, Дер, _ ) ).
имеетцикл( Дер) :-
смеж( А, В, Дер),
путь( А, В, Дер, [А, X, Y | _ ).
% Длина пути > 1
накрывает( Дер, Граф) :-
not ( вершина( А, Граф), not вершина( А, Дер) ).
подмнож( [ ], [ ]).
подмнож( [ Х | L], S) :-
подмнож( L, L1),
( S = L1; S = [ Х | L1] ).
Графы
9. 5. Графы
Литература
Литература
В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. Хороший и краткий обзор соответствующих алгоритмов и результатов их математического анализа можно найти в Gonnet (1984).
Прологовская программа для внесения нового элемента на произвольный уровень дерева (раздел 9.3) была впервые показана автору М. Ван Эмденом (при личном общении).
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. - М-: Мир, 1979.]
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.
Baase S. (1978). Computer Algorithms. Addison-Wesley.
Gonnet G. H. (1984). Handbook of Algorithms and Data Structures. Addison-Wesley.
В данной главе мы изучали
Резюме
В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе Списки:
варианты представления списков
сортировка списков:
сортировка методом "пузырька"
сортировка со вставками
быстрая сортировка
эффективность этих процедур
Представление множеств двоичными деревьями и двоичными справочниками:
поиск элемента в дереве
добавление элемента
удаление элемента
добавление в качестве листа или корня
сбалансированность деревьев и его связь с
эффективностью этих операций
отображение деревьев
Графы:
представление графов
поиск пути в графе
построение остовного дерева
Сортировка списка процедурой быстрсорт
Рисунок 9. 1. Сортировка списка процедурой быстрсорт.
встав( X, [Y | УпорСпис], [Y | УпорСпис1]):-
больше( X, Y), !,
встав( X, УпорСпис, УпорСпис1).
встав( X, УпорСпис, [X | УпорСпис] ).
Процедуры сортировки пузырек и вставсорт просты, но не эффективны. Из этих двух процедур процедура со вставками более эффективна, однако среднее время, необходимое для сортировки списка длиной n процедурой вставсорт, возрастает с ростом n пропорционально n2. Поэтому для длинных списков значительно лучше работает алгоритм быстрой сортировки, основанный на следующей идее (Рисунок 9.1):
line();Для того, чтобы упорядочить непустой список L, необходимо:
(1) Удалить из списка L какой-нибудь элемент Х и разбить оставшуюся часть на два списка, называемые Меньш и Больш, следующим образом: все элементы большие, чем X, принадлежат списку Больш, остальные - списку Меньш.
(2) Отсортировать список Меньш, результат - список УпорМеньш.
(3) Отсортировать список Больш, результат - список УпорБольш.
(4) Получить результирующий упорядоченный список как конкатенацию списков УпорМеньш и [ Х | УпорБольш].
line();Заметим, что если исходный список пуст, то результатом сортировки также будет пустой список. Реализация быстрой сортировки на Прологе показана на Рисунок 9.2. Здесь в качестве элемента X, удаляемого из списка, всегда выбирается просто голова этого списка. Разбиение на два списка запрограммировано как отношение с четырьмя аргументами:
разбиение( X, L, Больш, Меньш).
Временная сложность нашего алгоритма зависит от того, насколько нам повезет при разбиении сортируемого списка. Если списки всегда разбиваются на два списка примерно равной длины, то процедура сортировки имеет временную сложность порядка nlogn, где n - длина исходного списка. Если же, наоборот, разбиение всегда приводит к тому, что один из списков оказывается значительно больше другого, то сложность будет порядка n2. Анализ показывает, что, к счастью, средняя производительность быстрой сортировки ближе к лучшему случаю, чем к худшему.
Программу, показанную на Рисунок 9.2, можно усовершенствовать, если реализовать операцию конкатенации более эффективно. Напомним, что конкатенация
line();быстрсорт( [ ], [ ] ).
быстрсорт( [X | Хвост], УпорСпис) :-
разбиение( X, Хвост, Меньш, Больш),
быстрсорт( Меньш, УпорМеньш),
быстрсорт( Больш, УпорБольш),
конк( УпорМеньш, [X | УпорБольш], УпорСпис).
разбиение( X, [ ], [ ], [ ] ).
разбиение( X, [Y | Хвост], [Y | Меньш], Больш ) :-
больше( X, Y), !,
разбиение( X, Хвост, Меньш, Больш).
разбиение( X, [Y | Хвост], Меньш, [Y | Больш] ) :-
разбиение( X, Хвост, Меньш, Больш).
конк( [ ], L, L).
конк( [X | L1], L2, [X | L3] ) :-
конк( L1, L2, L3 ).
Быстрая сортировка
Рисунок 9. 2. Быстрая сортировка.
становится тривиальной операцией после применения разностного представления списков, введенного в гл. 8. Для того, чтобы использовать эту идею в нашей процедуре сортировки, нужно представить встречающиеся в ней списки в форме пар вида A-Z следующим образом:
УпорМеньш
имеет вид A1-Z1
УпорБольш имеет вид A2-Z2
Тогда конкатенации списков
УпорМеньш и [ Х | УпорБольш]
будет соответствовать конкатенация пар
A1-Z1 и [ Х | A2]-Z2
В результате мы получим
А1-Z2, причем Z1 = [ Х | А2]
Пустой список представляется парой Z-Z. Систематически вводя изменения в программу Рисунок 9.2, мы получим более эффективный способ реализации процедуры быстрсорт, показанный на Рисунок 9.3 под именем
line(); быстрсорт( Спис, УпорСпис) :-
быстрсорт2( Спис, УпорСпис-[ ] ).
быстрсорт2( [ ], Z-Z).
быстрсорт2( [X | Хвост], A1-Z2) :-
разбиение( X, Хвост, Меньш, Больш),
быстрсорт2( Меньш, А1-[Х | A2] ),
быстрсорт2( Больш, A2-Z2).
Более эффективная
Рисунок 9. 3. Более эффективная реализация процедуры быстрсорт
с использованием разностного представления списков. Отношение
разбиение( Х, Спис, Меньш, Больш) определено, как на Рисунок 9.2.
быстрсорт2. Здесь, как и раньше, процедура быстрсорт использует обычное представление списков, но в действительности сортировку выполняет более эффективная процедура быстрсорт2, использующая разностное представление. Эти две процедуры связаны между собой, соотношением
быстрсорт( L, S) :-
быстрсорт2( L, S-[ ] ).
Двоичное дерево
Рисунок 9. 4. Двоичное дерево.
Существует более эффективный и более привычный способ представления двоичных деревьев: нам нужен специальный символ для обозначения пустого дерева и функтор для построения непустого дерева из трех компонент ( корня и двух поддеревьев). Относительно функтора и специального символа сделаем следующий выбор: Пусть атом nil представляет пустое дерево. В качестве функтора примем дер, так что дерево с корнем X, левым поддеревом L и правым поддеревом R будет иметь вид терма дер( L, X, R) (см. Рисунок 9.5).
В этом представлении дерево Рисунок 9.4 выглядит как
дер( дер( nil, b, nil), a,
дер( дер( nil, d, nil), с, nil) ).
Теперь рассмотрим отношение принадлежности, которое будем обозначать внутри. Цель
внутри( X, Т)
истинна, если Х есть вершина дерева Т. Отношение внутри можно определить при помощи следующих правил:
line();Х есть вершина дерева Т, если корень дерева Т совпадает с X, или Х - это вершина из левого поддерева, или Х - это вершина из правого поддерева. line();
Представление двоичных деревьев
Рисунок 9. 5. Представление двоичных деревьев.
Эти правила непосредственно транслируются на Пролог следующим образом:
внутри( X, дер( -, X, -) ).
внутри( X, дер( L, -, -) ) :-
внутри( X, L).
внутри( X, дер( -, -, R) ) :-
внутри( X, R).
Очевидно, что цель
внутри( X, nil)
терпит неудачу при любом X.
Посмотрим, как ведет себя наша процедура. Рассмотрим Рисунок 9.4. Цель
внутри( X, Т)
используя механизм возвратов, находит все элементы данных, содержащиеся в множестве, причем обнаруживает их в следующем порядке:
Х = а; Х = b; Х = с; X = d
Теперь рассмотрим вопрос об эффективности. Цель
внутри( а, Т)
достигается сразу же после применения первого предложения процедуры внутри. С другой стороны, цель
внутри( d, Т)
будет успешно достигнута только после нескольких рекурсивных обращений. Аналогично цель
внутри( е, Т)
потерпит неудачу только после того, как будет просмотрено все дерево в результате рекурсивного применения процедуры внутри ко всем поддеревьям дерева Т.
В этом последнем случае мы видим такую же неэффективность, как если бы мы представили множество просто списком. Положение можно улучшить, если между элементами множества существует отношение порядка. Тогда можно упорядочить данные в дереве слева направо в соответствии с этим отношением.
найден после прохода по
Рисунок 9. 6. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5-->8-->6.
Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если
(1) все вершины левого поддерева Лев меньше X;
(2) все вершины правого поддерева Прав больше X;
(3) оба поддерева упорядочены.
Будем называть такое двоичное дерево двоичным справочником. Пример показан на Рисунок 9.6.
Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в двоичном справочнике всегда достаточно просмотреть не более одного поддерева. Экономия при поиске объекта Х достигается за счет того, что, сравнив Х с корнем, мы можем сразу же отбросить одно из поддеревьев. Например, пусть мы ищем элемент 6 в дереве, изображенной на Рисунок 9.6. Мы начинаем с корня 5, сравниваем 6 с 5, получаем 6 > 5. Поскольку все элементы данных в левом поддереве должны быть меньше, чем 5, единственная область, в которой еще осталась возможность найти элемент 6, - это правое поддерево. Продолжаем поиск в правом поддереве, переходя к вершине 8, и т.д.
Общий метод поиска в двоичном справочнике состоит в следующем:
line(); Для того, чтобы найти элемент Х в справочнике Д, необходимо: если Х - это корень справочника Д, то считать, что Х уже найден, иначе если Х меньше, чем корень, то искать Х в левом поддереве, иначе искать Х в правом поддереве; если справочник Д пуст, то поиск терпит неудачу. line();
Эти правила запрограммированы в виде процедуры, показанной на Рисунок 9.7. Отношение больше( X, Y), означает, что Х больше, чем Y. Если элементы, хранимые в дереве, - это числа, то под "больше, чем" имеется в виду просто Х > Y.
Существует способ использовать процедуру внутри также и для построения двоичного справочника. Например, справочник Д, содержащий элементы 5, 3, 8, будет построен при помощи следующей последовательности целей:
?- внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).
Д = дер( дер( Д1, 3, Д2), 5, дер( Д3, 8, Д4) ).
Переменные Д1, Д2, Д3 и Д4 соответствуют четырем неопределенным поддеревьям. Какими бы они ни были, все равно дерево Д будет содержать заданные элементы 3, 5 и 8. Структура построенного дерева зависит от того порядка, в котором указываются цели (Рисунок 9.8).
line(); внутри( X, дер( _, X, _ ).
внутри( X, дер( Лев, Корень, Прав) ) :-
больше( Корень, X), % Корень больше, чем Х
внутри( X, Лев). % Поиск в левом поддереве
внутри( X, дер( Лев, Корень, Прав) ) :-
больше( X, Корень), % Х больше, чем корень
внутри( X, Прав). % Поиск в правом поддереве
line();
Поиск элемента Х в двоичном справочнике
Рисунок 9. 7. Поиск элемента Х в двоичном справочнике.
а) Дерево Д построенное
Рисунок 9. 8. (а) Дерево Д, построенное как результат достижения целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д). (b) Дерево, полученное при другом порядке целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).
Здесь уместно сделать несколько замечаний относительно эффективности поиска в справочниках. Вообще говоря, поиск элемента в справочнике эффективнее, чем поиск в списке. Но насколько? Пусть n - число элементов множества. Если множество представлено списком, то ожидаемое время поиска будет пропорционально его длине n. В среднем нам придется просмотреть примерно половину списка. Если множество представлено двоичным деревом, то время поиска будет пропорционально глубине дерева. Глубина дерева - это длина самого длинного пути между корнем и листом дерева. Однако следует помнить, что глубина дерева зависит от его формы.
Мы говорим, что дерево (приближенно) сбалансировано, если для каждой вершины дерева соответствующие два поддерева содержат примерно равное число элементов. Если дерево хорошо сбалансировано, то его глубина пропорциональна log n. В этом случае мы говорим, что дерево имеет логарифмическую сложность. Сбалансированный справочник лучше списка настолько же, насколько log n меньше n. К сожалению, это верно только для приближенно сбалансированного дерева. Если происходит разбалансировка дерева, то производительность падает. В случае полностью разбалансированных деревьев, дерево фактически превращается в список. Глубина дерева в этом случае равна n, а производительность поиска оказывается столь же низкой, как и в случае списка. В связи с этим мы всегда заинтересованы в том, чтобы справочники были сбалансированы. Методы достижения этой цели мы обсудим в гл. 10.
Введение в двоичный
Рисунок 9. 9. Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок:
добавить( Д1, 6, Д2), добавить( Д2, 6, Д3), добавить( Д3, 6, Д4)
line();
доблист( 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 показана соответствующая программа.
Теперь рассмотрим операцию удалить. Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину - дело не простое. Удаление листа можно на самом деле определить как операцию, обратную
Удаление X из двоичного
Рисунок 9. 11. Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.
операции добавления листа:
удлист( Д1, X, Д2) :-
доблист( Д2, X, Д1).
К сожалению, если Х - это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит Рисунок 9.11. Вершина Х имеет два поддерева Лев и Прав. После удаления вершины Х в дереве образуется "дыра", и поддеревья Лев и Прав теряют свою связь с остальной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способна принять только одно из них.
Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты,
Заполнение пустого места после удаления X
Рисунок 9. 12. Заполнение пустого места после удаления X.
то можно использовать следующую идею (Рисунок 9.12): если самую левую вершину Y поддерева Прав переместить из ее текущего положения вверх и заполнить ею пробел, оставшийся после X, то упорядоченность дерева не нарушится. Разумеется, та же идея сработает и в симметричном случае, когда перемещается самая правая вершина поддерева Лев.
На Рисунок 9.13 показана программа, реализующая операцию удаления элементов в соответствии с изложенными выше соображениями. Основную работу по перемещению самой левой вершины выполняет отношение
удмин( Дер, Y, Дер1)
Здесь Y - минимальная (т.е. самая левая) вершина дерева Дер, а Дер1 - то, во что превращается дерево Дер после удаления вершины Y.
Существует другой, элегантный способ реализация операции добавить и удалить. Отношение добавить можно сделать недетерминированным в том смысле, что новый элемент вводится на произвольный уровень дерева, а не только на уровень листьев. Правила таковы:
line();уд( дер( nil, X, Прав), X, Прав).
уд( дер( Лев, X, nil), X, Лев).
уд( дер( Лев, Х, Прав), X, дер( Лев,Y, Прав1) ) :-
удмин( Прав, Y, Прав1).
уд( дер( Лев, Кор, Прав), X, дер( Лев1, Кор, Прав) ) :-
больше( Кор, X),
уд( Лев, X, Лев1).
уд( дер( Лев, Кор, Прав), X, дер( Лев, Кор, Прав1) ) :-
больше( X, Кор),
уд( Прав, X, Прав1).
удмин( дер( nil, Y, Прав), Y, Прав).
удмин( дер( Лев, Кор, Прав), Y, дер( Лев1, Кор, Прав) ) :-
удмин( Лев, Y, Лев1).
Удаление элемента из двоичного справочника
Рисунок 9. 13. Удаление элемента из двоичного справочника.
line();
Для того, чтобы добавить Х в двоичный справочник Д, необходимо одно из двух: добавить Х на место корня дерева (так, что Х станет новым корнем) или если корень больше, чем X, то внести Х в левое поддерево, иначе - в правое поддерево. line();
Трудным моментом здесь является введение Х на место корня. Сформулируем эту операций в виде отношения
добкор( Д, X, X1)
где Х - новый элемент, вставляемый вместо корня в Д, а Д1 - новый справочник с корнем Х. На Рисунок 9.14 показано, как соотносятся X, Д и Д1. Остается вопрос: что из себя представляют поддеревья L1 и L2 (или, соответственно, R1 и R2) на Рисунок 9.14?
Внесение Х в двоичный справочник в качестве корня
Рисунок 9. 14. Внесение Х в двоичный справочник в качестве корня.
Ответ мы получим, если учтем следующие ограничения на L1, L2: L1 и L2 - двоичные справочники; множество всех вершин, содержащихся как в L1, так и в L2, совпадает с множеством вершин справочника L; все вершины из L1 меньше, чем X; все вершены из L2 больше, чем X.
Отношение, которое способно наложить все эти ограничения на L1, L2, - это как раз и есть наше отношение добкор. Действительно, если бы мы вводили Х в L на место корня, то поддеревьями результирующего дерева как раз и оказались бы L1 и L2. В терминах Пролога L1 и L2 должны быть такими, чтобы достигалась цель
добкор( L, X, дер( L1, X, L2) ).
Те же самые ограничения применимы к R1, R2:
добкор( R, X, дер( R1, X, R2) ).
line(); добавить( Д, X, Д1) :-
% Добавить Х на место корня
добкор( Д, X, Д1).
добавить( дер( L, Y, R), X, дер( L1, Y, R) ) :-
больше( Y, X),
% Ввести Х в левое поддерево
добавить( L, X, L1).
добавить( дер( L, Y, R), X, дер( L, Y, R1) ) :-
больше( X, Y),
% Ввести Х в правое поддерево
добавить( R, X, R1).
добкор( nil, X, дер( nil, X, nil) ). % Ввести Х в пустое дерево
добкор( дер( L, Y, R), Х, дер( L1, Х, дер( L2, Y, R) )) :-
больше( Y, X),
добкор( L, X, дер( L1, X, L2) ).
добкор( дep( L, Y, R), X, дep( дep( L, Y, R1), X, R2) ) :-
больше( X, Y),
добкор( R, X, дер( R1, X, R2) ).
Внесение элемента на произвольный уровень двоичного справочника
Рисунок 9. 15. Внесение элемента на произвольный уровень двоичного справочника.
На Рисунок 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справочник.
Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:
добавить( nil, 3, Д1), добавить( Д1, 5, Д2),
добавить( Д2, 1, Д3), добавить( Д3, 6, Д),
добавить( ДД, 5, Д).
а) Обычное изображение
Рисунок 9. 16. (а) Обычное изображение дерева. (b) То же дерево,
отпечатанное процедурой отобр (дуги добавлены для ясности).
Давайте определим процедуру
отобр( Т)
так, чтобы она отображала дерево в форме, показанной на Рисунок 9.16. Принцип работы этой процедуры:
line();Для того, чтобы отобразить непустое дерево Т, необходимо:
(1) отобразить правое поддерево дерева Т с отступом вправо на расстояние Н;
(2) отпечатать корень дерева Т;
(3) отобразить левое поддерево дерева Т с отступом вправо на расстояние Н.
line();Величина отступа Н, которую можно выбирать по желанию, - это дополнительный параметр при отображении деревьев. Введем процедуру
отобр2( Т, Н)
печатающую дерево Т с отступом на Н пробелов от левого края листа. Связь между процедурами отобр и отобр2 такова:
отобр( Т) :- отобр2( Т, 0).
На Рисунок 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.
line(); отобр( Т) :-
отобр2( Т, 0).
отобр2( nil, _ ).
отобр2( дер( L, X, R), Отступ) :-
Отступ2 is Отступ + 2,
отобр2( R, Отступ2),
tab( Отступ), write( X), nl,
отобр( L, Отступ2).
Отображение двоичного дерева
Рисунок 9. 17. Отображение двоичного дерева.
а) Граф (b) Направленный граф Каждой дуге приписана ее стоимость
Рисунок 9. 18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.
Для представления направленного графа (Рисунок 9.18), применив функторы диграф и д (для дуг), получим
G2 = диграф( [s, t, u, v],
[д( s, t, 3), д( t, v, 1), д( t, u, 5), д( u, t, 2),
д( v, u, 2) ] )
Если каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер.
Еще один способ представления графа - связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности. Наши графы (Рисунок 9.18), например, можно представить как
G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ]
G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]]
Здесь символы '->' и '/' - инфиксные операторы.
Какой из способов представления окажется более удобным, зависит от конкретного приложения, а также от того, какие операции имеется в виду выполнять над графами. Вот типичные операции: найти путь между двумя заданными вершинами; найти подграф, обладающий некоторыми заданными свойствами.
Примером последней операции может служить построение основного дерева графа. В последующих разделах, мы рассмотрим некоторые простые программы для поиска пути в графе и построения основного дерева.
Поиск в графе Граф ациклического пути Путь из А в Z
Рисунок 9. 20. Поиск в графе Граф ациклического пути Путь из А в Z.
На Рисунок 9.20 программа показана полностью. Здесь принадлежит - отношение принадлежности элемента списку. Отношение
смеж( X, Y, G)
означает, что в графе G существует дуга, ведущая из Х в Y. Определение этого отношения зависит от способа представления графа. Если G представлен как пара множеств (вершин и ребер)
G = граф( Верш, Реб)
то
смеж( X, Y, граф( Верш, Реб) ) :-
принадлежит( р( X, Y), Реб);
принадлежит( р( Y, X), Реб).
Классическая задача на графах - поиск Гамильтонова цикла, т.е. ациклического пути, проходящего через все вершины графа. Используя отношение путь, эту задачу можно решить так:
гамильтон( Граф, Путь) :-
путь( _, _, Граф, Путь),
всевершины( Путь, Граф).
всевершины( Путь, Граф) :-
not (вершина( В, Граф),
not принадлежит( В, Путь) ).
Здесь вершина( В, Граф) означает: В - вершина графа Граф.
Каждому пути можно приписать его стоимость. Стоимость пути равна сумме стоимостей входящих в него дуг. Если дугам не приписаны стоимости, то тогда, вместо стоимости, говорят о длине пути.
Для того, чтобы наши отношения путь и путь1 могли работать со стоимостями, их нужно модифицировать, введя дополнительный аргумент для каждого пути:
путь( А, Z, G, Р, С)
путь1( A, P1, C1, G, Р, С)
Здесь С - стоимость пути Р, a C1 - стоимость пути Р1. В отношении смеж также появится дополнительный аргумент, стоимость дуги. На Рисунок 9.21 показана программа поиска пути, которая строит путь и вычисляет его стоимость.
line(); путь( А, Z, Граф, Путь, Ст) :-
путь1( A, [Z], 0, Граф, Путь, Ст).
путь1( А, [А | Путь1], Ст1, Граф, [А | Путь1], Ст).
путь1( А, [Y | Путь1], Ст1, Граф, Путь, Ст) :-
смеж( X, Y, СтXY, Граф),
not принадлежит( X, Путь1),
Ст2 is Ст1 + СтXY,
путь1( А, [ X, Y | Путь1], Ст2, Граф, Путь, Ст).
Поиск пути в графе Путь путь между А и Z в графе Граф стоимостью Ст
Рисунок 9. 21. Поиск пути в графе: Путь - путь между А и Z в графе Граф стоимостью Ст.
Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости между вершинами Верш1, Верш2 графа Граф, задав цели
путь( Bepш1, Верш2, Граф, МинПуть, МинСт),
not ( путь( Верш1, Верш2, Граф, _, Ст), Ст<МинСт )
Аналогично можно среди всех путей между вершинами графа найти путь максимальной стоимости, задав цели
путь( _, _, Граф, МаксПуть, МаксСт),
not ( путь( _, _, Граф, _, Ст), Ст > МаксСт)
Заметим, что приведенный способ поиска максимальных и минимальных путей крайне неэффективен, так как он предполагает просмотр всех возможных путей и потому не подходит для больших графов из-за своей высокой временной сложности. В искусственном интеллекте задача поиска пути возникает довольно часто. В главах 11 и 12 мы изучим более сложные методы нахождения оптимальных путей.
Построение остовного
Рисунок 9. 23. Построение остовного дерева: "декларативный подход".
Отношения вершина и смеж см. на Рисунок 9. 22.
Наша процедура изображает дерево, ориентируя
Упражнение
9. 14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья - справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.
Посмотреть ответ
в случае, когда каждому ребру
Упражнение
9. 15. Рассмотрите остовные деревья в случае, когда каждому ребру графа приписана его стоимость. Пусть стоимость остовного дерева определена как сумма стоимостей составляющих его ребер. Напишите программу построения для заданного графа его остовного дерева минимальной стоимости.
к списку, используя систему обозначений,
Упражнения
9. 1. Определите отношение
список( Объект)
для распознавания случаев, когда Объект является стандартным прологовским списком.
Посмотреть ответ
9. 2. Определите отношение принадлежности к списку, используя систему обозначений, введенную в этой разделе: "затем - ничего_не_делать".
Посмотреть ответ
9. 3. Определите отношение
преобр( СтандСпис, Спис)
для преобразования списков из стандартного представления в систему "затем-ничего_не_делать". Например:
преобр( [а, b], а затем b затем ничего_не_делать)
Посмотреть ответ
9. 4. Обобщите отношение преобр на случай произвольного альтернативного представления списков. Конкретное представление задается символом, обозначающим пустой список, и функтором для соединения головы с хвостом. В отношении преобр придется добавить два новых аргумента:
преобр( СтандСпис, Спис, Функтор, ПустСпис)
Примеры применения этого отношения:
?- пpeoбp( [а, b], L, затем, ничего_не_делать).
L = а затем b затем ничего_не_делать
?- преобр( [а, b, с], L, +, 0).
L = а+(b+(с+0) )
Посмотреть ответ
Упражнения
9. 5. Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:
?- слить( [2, 5, 6, 6, 8], [1, 3, 5, 9], L).
L = [1, 2, 3, 5, 5, 6, 6, 8, 9]
9. 6. Программы сортировки, показанные на Рисунок 9.2 и 9.3, отличаются друг от друга способом представления списков. Первая из них использует обычное представление, в то время как вторая - разностное представление. Преобразование из одного представления в другое очевидно и может быть автоматизировано. Введите в программу Рисунок 9.2 необходимые изменения, чтобы преобразовать ее в программу Рисунок 9.3.
9. 7. Наша программа быстрсорт в случае, когда исходный список уже упорядочен или почти упорядочен, работает очень неэффективно. Проанализируйте причины этого явления.
9. 8. Существует еще одна хорошая идея относительно механизма сортировки списков, позволяющая избавиться от недостатков программы быстрсорт, а именно: разбить список на два меньших списка, отсортировать их, а затем слить вместе. Итак, для того, чтобы отсортировать список L, необходимо разбить L на два списка L1 и L2 примерно одинаковой длины; произвести сортировку списков L1 и L2,получив списки S1 и S2; слить списки S1 и S2, завершив на этом сортировку списка L.
Реализуйте этот принцип сортировки и сравните его эффективность с эффективностью программы быстрсорт.
Посмотреть ответ
Упражнения
9. 9. Определите предикаты
двдерево( Объект)
справочник( Объект)
распознающие, является ли Объект
двоичным деревом или двоичным справочником соответственно. Используйте обозначения, введенные в данном разделе.
Посмотреть ответ
9. 10. Определите процедуру
глубина( ДвДерево, Глубина)
вычисляющую глубину двоичного дерева в предположении, что глубина пустого дерева равна 0, а глубина одноэлементного дерева равна 1.
Посмотреть ответ
9. 11. Определите отношение
линеаризация( Дерево, Список)
соответствующее "выстраиванию" всех вершин дерева в список.
Посмотреть ответ
9. 12. Определите отношение
максэлемент( Д, Элемент)
таким образом, чтобы переменная Элемент
приняла значение наибольшего из элементов, хранящихся в дереве Д.
Посмотреть ответ
9. 13. Внесите изменения в процедуру
внутри( Элемент, ДвСправочник)
добавив в нее третий аргумент Путь
таким образом, чтобы можно было бы получить путь между корнем справочника и указанным элементом.
Посмотреть ответ
Двоично троичные справочники
10. 1. Двоично - троичные справочники
Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину (или размер) и сами сбалансированы. Глубина сбалансированного дерева приближенно равна log n , где n - число вершин дерева. Время, необходимое для вычислений, производимых отношениями внутри, добавить и удалить над двоичными справочниками, пропорционально глубине дерева. Таким образом, в случае двоичных справочников это время имеет порядок log n. Логарифмический рост сложности алгоритма, проверяющего принадлежность элемента множеству, - это определенное достижение по сравнению со списковым представлением, поскольку в последнем случае мы имеем линейный рост сложности
AVL дерево приближенно сбалансированное дерево
10. 2. AVL - дерево: приближенно сбалансированное дерево
AVL-дерево - это дерево, обладающее следующими свойствами:
(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.
(2) Оба поддерева являются AVL-деревьями.
Деревья, удовлетворяющие этому определению, могут быть слегка разбалансированными. Однако можно показать, что даже в худшем случае глубина AVL-дерева примерно пропорциональна log n, где n - число вершин дерева. Таким образом гарантируется логарифмический порядок производительности операций внутри, добавить и удалить.
Операции над AVL-деревом работают по существу так же, как и над двоичным справочником. В них только сделаны добавления, связанные с поддержанием приближенной сбалансированности дерева. Если после вставления или удаления дерево перестает быть приближенно сбалансированным, то специальные механизмы возвращают ему требуемую степень сбалансированности. Для того, чтобы эффективно реализовать этот механизм, нам придется сохранять некоторую дополнительную информацию относительно степени сбалансированности дерева. На самом деле, нам нужно знать только разность между глубинами поддеревьев, которая может принимать значения -1, 0 или +1. Тем не менее для простоты мы предпочтем сохранять сами величины глубин поддеревьев, а не разности между ними.
Мы определим отношение вставления элемента как
доб_avl( Дер, X, НовДер)
где оба дерева Дер и НовДер - это AVL-деревья, причем НовДер получено из Дер вставлением элемента X. AVL-деревья будем представлять как термы вида
д( Лев, А, Прав)/Глуб
где А - корень, Лев и Прав - поддеревья, а Глуб -
Иллюстрирует описанный принцип
Рисунок 10.3 иллюстрирует описанный принцип.
Литература
Литература
2-3 деревья детально описаны, например, в Aho, Hopcroft and Ullman (1974, 1983). В книге этих авторов, вышедшей в 1983 г., дается также реализация соответствующих алгоритмов на языке Паскаль. Н.Вирт (см. Wirth (1976)) приводит программу на Паскале для работы с AVL-деревьями. 2-3 деревья являются частным случаем более общего понятия В-деревьев. В-деревья, а также несколько других вариантов структур данных, имеющих отношение к 2-3 деревьям в AVL-деревьям, рассматриваются в книге Gonnet (1984). В этой книге, кроме того, даны результаты анализа поведения этих структур.
Программа вставления элемента в AVL-дерево, использующая только величину "перекоса" дерева (т.е. значение разности глубин поддеревьев, равной -1, 0 или 1, вместо самой глубины) опубликована ван Эмденом (1981).
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. - М.: Мир, 1979.]
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.
Gonnet G. H. (1984). Handbook of Algorithms + Data Structures. Addison-Wesley.
van Emden M. (1981). Logic Programming Newsletter 2.
Wirth N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. [Имеется перевод: Вирт H. Алгоритмы + структуры данных = программы. - M.: Мир, 1985.]
Сбалансированные или приближенно сбалансированные деревья
Резюме
2-3 деревья и AVL-деревья, представленные в настоящей главе, - это примеры сбалансированных деревьев. Сбалансированные или приближенно сбалансированные деревья гарантируют эффективное выполнение трех основных операций над деревьями: поиск, добавление и удаление элемента. Время выполнения этих операций пропорционально log n, где n - число вершин дерева.
Полностью разбалансированный
Рисунок 10. 1. Полностью разбалансированный двоичный справочник.
Производительность его та же, что и у списка.
с ростом размера множества. Однако плохая сбалансированность дерева ведет к деградации производительности алгоритмов, работающие со справочником. В крайнем случае, двоичный справочник вырождается в список, как показано на Рисунок 10. l. Форма справочника зависит от той последовательности, а которой в всего записываются элементы данных. В лучшей случае мы получаем хорошую балансировку и производительность порядка log n, а в худшем - производительность будет порядка n. Анализ показывает, что в среднем сложность алгоритмов внутри, добавить и удалить сохраняет порядок log n в допущении, что все возможные входные последовательности равновероятны. Таким образом, средняя производительность, к счастью, оказывается ближе к лучшему случаю, чек к худшему. Существует, однако, несколько довольно простых механизмов, которые поддерживают хорошую сбалансированность дерева, вне зависимости от входной последовательности, формирующей дерево. Эти механизмы гарантируют производительность алгоритмов внутри, добавить и удалить порядка log n даже в худшем случае. Один из этих механизмов - двоично-троичные деревья (кратко, 2-3 деревья), а другой - AVL-деревья.
2-3 дерево определяется следующим образом: оно или пусто, или состоит из единственной вершины, или удовлетворяет следующим условиям: каждая внутренняя вершина имеет две или три дочерних вершины, и все листья дерева находятся на одном и том же уровне.
Двоично-троичным (2-3) справочником называется 2-3 дерево, все элементы данных которого хранятся в листьях и упорядочены слева направо. На Рисунок 10.2 показан пример. Внутренние вершины содержат метки, равные минимальным элементам тех или иных своих поддеревьев, в соответствии со следующими правилами: если внутренняя вершина имеет два поддерева, то она содержит минимальный элемент второго из них; если внутренняя вершина имеет три поддерева, то она содержит минимальные элементы второго и третьего поддеревьев.
справочник. Отмеченный путь показывает
Рисунок 10. 2. 2- 3 справочник. Отмеченный путь показывает процесс поиска элемента 10.
При поиске элемента Х в 2-3 справочнике мы начинаем с корня и двигаемся в направлении самого нижнего уровня, руководствуясь при этом метками внутренних вершин дерева. Пусть корень содержит метки Ml и М2, тогда если Х < M1, то поиск продолжается в левом поддереве, иначе если Х < М2, то поиск продолжается в среднем поддереве, иначе - в правом поддереве.
Если в корне находится только одна метка М, то переходим к левому поддереву при Х < М и к правому поддереву - в противоположном случае. Продолжаем применять сформулированные выше правила, пока не окажемся на самом нижнем уровне дерева, где и выяснится, найден ли элемент X, или же поиск потерпел неудачу.
Так как все листья 2-3 дерева находятся на одном и том же уровне, 2-3 дерево идеально сбалансировано с точки зрения глубины составляющих его поддеревьев. Все пути от корня до листа, которые мы проходим при поиске, имеют одну и ту же длину порядка log n, где n - число элементов, хранящихся в дереве.
При добавлении нового элемента данных 2-3 дерево может расти не только в глубину, но и в ширину. Каждая внутренняя вершина, имеющая два поддерева, может приобрести новое поддерево, что приводит к росту вширь. Если же, с другой стороны, у вершины уже есть три поддерева, и она должна принять еще одно, то она расщепляется на две вершины, каждая из которых берет на себя по два из имеющихся четырех поддеревьев. Образовавшаяся при этом новая вершина передается вверх по дереву для присоединения к одной из выше расположенных вершин. Если же эта ситуация возникает на самом высоком уровне, то дерево вынуждено "вырасти" на один уровень вверх.
Вставление нового
Рисунок 10. 3. Вставление нового элемента в 2-3 справочник. Дерево
растет сначала вширь, а затем уже вглубь.
Включение нового элемента в 2-3 справочник мы запрограммируем как отношение
доб23( Дер, X, НовДер)
где дерево НовДер получено введением элемента Х в дерево Дер. Основную работу мы поручим двум дополнительным отношениям, которые мы назовем встав. Первое из них имеет три аргумента:
встав( Дер, X, НовДер).
Здесь НовДер - результат вставления элемента Х в Дер. Деревья Дер и НовДер имеют одну и ту же глубину. Разумеется, не всегда возможно сохранить ту же глубину дерева. Поэтому существует еще одно отношение с пятью аргументами специально для этого случая:
встав( Дер, X, НДа, Mб, НДб).
Имеется в виду, что при вставления Х в Дер дерево Дер разбивается на два дерева НДа и НДб, имеющих ту же глубину, что и Дер. Мб - это минимальный элемент из НДб. Пример показан на Рисунок 10.4.
Объекты показанные на рисунке удовлетворяют отношению встав( Дер 6 НДа Мб НДб)
Рисунок 10. 4. Объекты, показанные на рисунке, удовлетворяют отношению встав( Дер, 6, НДа, Мб, НДб).
2-3 деревья мы будем представлять в программе следующим образом: nil представляет пустое дерево; л( Х) представляет дерево, состоящее из одной вершины - листа с элементом X; в2( Д1, М, Д2) представляет дерево с двумя поддеревьями Д1 и Д2; М - минимальный элемент из Д2; в3( Д1, М2, Д2, М3, Д3) представляет дерево с тремя поддеревьями Д1, Д2 и Д3; М2 - минимальный элемент из Д2; М3 - минимальный элемент из Д3; Д1, Д2 и Д3 - 2-3 деревья.
Между доб23 и встав существует следующая связь: если после вставления нового элемента дерево не "вырастает", то
доб23( Дер, X, НовДер) :-
встав( Дер, X, НовДер).
Однако если после вставления элемента глубина дерева увеличивается, то встав порождает два поддерева Д1 и Д2, а затем составляет из них дерево большей глубины:
доб23( Дер, X, в2( Д1, М, Д2) ) :-
встав( Дер, X, Д1, М, Д2).
Отношение встав устроено более сложным образом, поскольку ему приходится иметь дело со многими случаями, а именно вставление в пустое дерево, в дерево, состоящее из одного листа, и в деревья типов в2 и в3. Возникают также дополнительные подслучаи, так как новый элемент можно вставить в первое, либо во второе, либо в третье поддерево. В связи с этим мы определим встав как набор правил таким образом, чтобы каждое предложение процедуры встав имело дело с одним из этих случаев. На Рисунок 10.5 показаны некоторые из возможных случаев. На Пролог они транслируются следующим образом:
Случай а
встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ) :-
больше( М, X),
% М больше, чем Х
встав( Д1, X, НД1).
Случай b
встав( в2( Д1, M, Д2), X, в3( НД1а, Мб, НД1б, M, Д2) ) :-
больше( М, X),
встав( Д1, X, НД1а, Мб, НД1б).
Случай с
встав( в3( Д1, М2, Д2, М3, Д3), X, в2( НД1а, Мб, НД1б), М2, в2(Д2, М3, Д3) ) :-
больше( М2, X),
встав( Д1, X, НД1а, Мб, НД1б).
Некоторые из случаев
Рисунок 10. 5. Некоторые из случаев работы отношения встав.
(a) встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) );
(b) встав( в2( Д1, М, Д2), X,
в3( НД1а, Мб, НД1б, М, Д2) );
(c) встав( в3( Д1, М2, Д2, М3, Д3), X,
в2( НД1а, Мб, НД1б), М2, в2( Д2, М3, Д3) ).
line();
% Вставление элемента в 2-3 справочник
доб23( Дер, X, Дер1) :-
% Вставить Х в Дер, получить Дер1
встав( Дер, X, Дер1).
% Дерево растет вширь
доб23( Дер, X, в2( Д1, М2, Д2) ) :-
встав( Дер, X, Д1, М2, Д2). % Дерево растет вглубь
доб23( nil, X, л( Х) ).
встав( л( А), X, л( А), X, л( Х) ) :-
больше( X, А).
встав( л( А), X, л( Х), А, л( А) ) :-
больше( А, X).
встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ) :-
больше( М, X),
встав( Д1, X, НД1).
встав( в2( Д1, М, Д2), Х, в3( НД1а, Мб, НД1б, М, Д2) ) :-
больше( М, X),
встав( Д1, X, НД1а, Мб, НД1б).
встав( в2( Д1, М, Д2), X, в2( Д1, М, НД2) ) :-
больше( X, М),
встав( Д2, X, НД2).
встав( в2( Д1, М, Д2), Х, в3( Д1, М, НД2а, Мб, НД2б) ) :-
больше( X, М),
встав( Д2, X, НД2а, Мб, НД2б).
встав( в3( Д1, М2, Д2, М3, Д3), Х, в3( НД1, М2, Д2, М3, Д3) :-
больше( М2, X),
встав( Д1, X, НД1).
встав( в3( Д1, М2, Д2, М3, Д3), X,
в2( НД1а, Мб, НД1б), М2, в2( Д2, М3, Д3) ) :-
больше( М2, X),
встав( Д1, X, НД1а, Мб, НД1б).
встав( в3( Д1, М2, Д2, М3, Д3), X,
в3( Д1, М2, НД2, М3, Д3) ) :-
больше( X, М2), больше( М3, X),
встав( Д2, X, НД2).
встав( в3( Д1, М2, Д2, М3, Д3), X,
в2( Д1, М2, НД2а), Мб, в2( НД2б, М3, Д3) ) :-
больше( X, М2), больше( М3, X),
встав( Д2, X, НД2а, Мб, НД2б).
встав( в3( Д1, М2, Д2, М3, Д3), X,
в3( Д1, М2, Д2, М3, НД3) ) :-
больше( X, М3),
встав( Д3, X, НД3).
встав( в3( Д1, М2, Д2, М3, Д3), X,
в2( Д1, М2, Д2), М3, в2( НД3а, Мб, НД3б) ) :-
больше( X, М3),
встав( Д3, X, НД3а, Мб, НД3б).
Вставление элемента
Рисунок 10. 6. Вставление элемента в 2-3 справочник. В этой
программе предусмотрено, что попытка повторного
вставления элемента терпит неудачу.
Программа для вставления нового элемента в 2-3 справочник показана полностью на Рисунок 10.6. На Рисунок 10.7 показана программа вывода на печать 2-3 деревьев.
Наша программа иногда выполняет лишние возвраты. Так, если встав с тремя аргументами терпит неудачу, то вызывается процедура встав с пятью аргументами, которая часть работы делает повторно. Можно устранить источник неэффективности, если, например, переопределить встав как
встав2( Дер, X, Деревья)
где Деревья - список, состоящий либо из одного, либо из трех аргументов:
Деревья = [ НовДер], если
встав( Дер, X, НовДер)
Деревья = [ НДа, Мб, НДб],
если встав( Дер, X, НДа, Мб, НДб)
Теперь отношение доб23 можно переопределить так:
доб23( Д, X, Д1) :-
встав( Д, X, Деревья),
соединить( Деревья, Д1).
Отношение соединить формирует одно дерево Д1 из деревьев, находящихся в списке Деревья.
а) Программа для
Рисунок 10. 7. (а) Программа для отображения 2-3 справочника.
(b) Справочник (см. Рисунок 10.2), отпечатанный этой программой.
Задача вставления
Рисунок 10. 8. Задача вставления элемента в AVL-справочник
(a) AVL-дерево перед вставлением Х, Х > А;
(b) AVL-дерево после вставления Х в R;
(с) составные части, из которых следует построить новое дерево.
глубина дерева. Пустое дерево изображается как nil/0. Теперь рассмотрим вставление элемента Х в непустой AVL-справочник
Дер = д( L, A, R)/H
Начнем со случая, когда Х больше А. Х необходимо вставить в R, поэтому имеем следующее отношение:
доб_аv1( R, X, д( R1, В, R2)/Hb)
На Рисунок 10.8 показаны составные части, из которых строится дерево НовДер:
L, А, R1, В, R2
Какова глубина деревьев L, R, R1 и R2? L и R могут отличаться по глубине не более, чем на 1. На Рисунок 10.8 видно, какую глубину могут иметь R1 и R2. Поскольку в R был добавлен только один элемент X, только одно из поддеревьев R1, R2 может иметь
Три правила построения нового AVLдepевa
Рисунок 10. 9. Три правила построения нового AVL-дepевa.
глубину h +1.
В случае, когда Х меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким образом, в любом случае мы должны построить дерево НовДер, используя три дерева (назовем их Дер1, Дер2 и Дер3) и два отдельных элемента А и В. Теперь рассмотрим вопрос: как соединить между собой эти пять составных частей, чтобы дерево НовДер было AVL-справочником? Ясно, что они должны располагаться внутри НовДер в следующем порядке (слева направо):
Дер1, А, Дер2, В, Дер3
Рассмотрим три случая:
(1) Среднее дерево Дер2 глубже остальных двух деревьев.
(2) Дер1 имеет глубину не меньше, чем Дер2 и Дер3.
(3) Дер3 имеет глубину не меньше, чем Дер2 и Дер1.
На Рисунок 10.9 видно, как можно построить дерево НовДер в каждом из этих трех случаев. Например, в случае 1 среднее дерево Дер2 следует разбить на два части, а затем включить их в состав НовДер. Три правила, показанные на pис.10.9, нетрудно запасать на Прологе в виде отношения
соединить( Дер, А, Дер2, В, Дер3, НовДер)
Последний аргумент НовДер - это AVL-дерево, построенное из пяти составных частей, пяти первых аргументов. Правило 1, например, принимает вид:
соединить( Д1/Н1, А, д( Д21, В, Д22)/Н2, С, Д3/Н3,
% Пять частей
д( д( Д1/Н1, А, Д21)/На, В, д( Д22, С, Д3/Н3)/Нс)/Нb) :-
% Результат
H2 > H1, H2 > Н3,
% Среднее дерево глубже остальных
На is Н1 + 1,
% Глубина левого поддерева
Нс is Н3 + 1,
% Глубина правого поддерева
Hb is На + 1,
% Глубина всего дерева
Программа доб_аvl, вычисляющая также глубину дерева и его поддеревьев, показана полностью на Рисунок 10.10.
Вставление элемента
Рисунок 10. 10. Вставление элемента в AVL-справочник. В этой
программе предусмотрено, что попытка повторного вставления
элемента терпит неудачу. По поводу процедуры соединить см.
Рисунок 10.9.
деревья представляйте в виде термов
д( Лев, Кор, Прав) или nil.
для проверки того, является ли
Упражнение
10. 3. Определите отношение
avl( Дер)
для проверки того, является ли Дер AVL-деревом, т.е. верно ли, что любые два его поддерева, подсоединенные к одной и той же вершине, отличаются по глубине не более чем на 1. Двоичные
line(); % Вставление элемента в AVL-справочник
доб_аvl( nil/0, X, д( nil/0, X, nil/0)/1).
% Добавить Х к пустому дереву
доб_аvl( д( L, Y, R)/Ну, X, НовДер) :-
% Добавить Х к непустому дереву
больше( Y, X),
доб_аvl( L, X, д( L1, Z, L2)/ _ ),
% Добавить к левому поддереву
соединить( L1, Z, L2, Y, R, НовДер).
% Сформировать новое дерево
доб_avl( д( L, Y, R)/Ну, X, НовДер) :-
больше( X, Y),
доб_avl( R, X, д( R1, Z, R2)/ _ ),
% Добавить к правому поддереву
соединить( L1, Y, Rl, Z, R2, НовДер).
соединить( Д1/Н1, А, д( Д21, В, Д22)/Н2, С, Д3/Н3,
д( д( Д1/Н1, А, Д21)/На, В, д( Д22, С, L3/Н3)/Нс)/Нb) :-
Н2 > H1, H2 > Н3, % Среднее дерево глубже остальных
На is H1 + 1,
Hс is Н3 + 1,
Нb is На + 1.
соединить( Д1/Н1, А, д( Д2/Н2, С, Д3/Н3,
д( Д1/Н1, А, д( Д2/Н2, С, Д3/Н3)/Нс)/На) :-
H1 >= H2, H1 >= Н3, % "Глубокое" левое дерево
max1( H2, Н3, Нс),
max1( H1, Нс, На).
соединить( Д1/Н1, А, Д2/Н2, С, Д3/Н3,
д( д( Д1/Н1, А, Д2/Н2)/На, С, Д3/Н3)/Нс) :-
Н3 >= H2, Н3 >= H1, % "Глубокое" правое дерево
max1( H1, H2, На),
max1( На, Н3, Нс).
max1( U, V, М) :-
U > V, !, М is U + 1; % М равно 1 плюс max( U,V)
М is V + 1.
line();
изменения для устранения лишних
Упражнения
10. 1. Определите отношение
внутри( Эдем, Дер)
для поиска элемента Элем в 2-3 справочнике Дер.
Посмотреть ответ
10. 2. Введите в программу Рисунок 10. 6 изменения для устранения лишних возвратов (определите отношения встав2 и соединить).
line(); % Отображение 2-3 справочников
отобр(Д) :- 15
отобр( Д, 0). --
отобр( nil, _ ). 15
отобр( л(А), Н) :- --
tab( H), write( A), nl. 13
отобр( в2( Д1, М, Д2), Н) :- --
H1 is H + 5 13
отобр( Д2, H1), --
tab( H), write( --), nl, 12
tab( H), write( M), nl, --
tab( H), write( --), nl, 12
отобр( Д1, H1). 10
отобр( в3( Д1, M2, Д2, М3, Д3), H) :- 10
H1 is H + 5 --
отобр( Д3, H1), 8
tab( H), write( --), nl, --
tab( H), write( M3), nl, 8
отобр( Д2, H1), --
tab( H), write( M2), nl, 7
tab( H), write( --), nl, --
отобр( Д1, H1). 7
--
(a) 5
-- 5
--
4
--
4
3
3
--
1
(б)
line();
