Двоичные справочники: добавление и удаление элемента
Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из него один из старых. В связи с этим набор основных операций, выполняемых над множеством S, таков:
внутри( X, S) % X содержится в S
добавить( S, X, S1) % Добавить X к S, результат - S1
удалить( S, X, S1) % Удалить X из S, результат - S1
Рис. 9.9. Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок: добавить( Д1, 6, Д2), добавить( Д2, 6, Д3), добавить( Д3, 6, Д4)
доблист( nil, X, дер( nil, X, nil) ).
доблист( дер( Лев, X, Прав), X, дер( Лев, X, Прав) ).
доблист( дер( Лев, Кор, Прав), X, дер( Лев1, Кор, Прав)) :-
больше( Кор, X),
доблист( Лев, X, Лев1)).
доблист( дер( Лев, Кор, Прав), X, дер( Лев, Кор, Прав1)) :-
больше( X, Кор),
доблист( Прав, X, Прав1).
Рис. 9.10. Вставление в двоичный справочник нового элемента в качестве листа.
Определим отношение добавить . Простейший способ: ввести новый элемент на самый нижний уровень дерева, так что он станет его листом. Место, на которое помещается новый элемент, выбрать таким образом, чтобы не нарушить упорядоченность дерева. На рис. 9.9 показано, какие изменения претерпевает дерево в процессе введения в него новых элементов. Назовем такой метод вставления элемента в множество
доблист( Д, X, Д1)
Правила добавления элемента на уровне листьев таковы:
|
|
|
• Результат добавления элемента X к пустому дереву есть дерево дер( nil, X, nil).
• Если X совпадает с корнем дерева Д, то Д1 = Д (в множестве не допускается дублирования элементов).
• Если корень дерева Д больше, чем X, то X вносится в левое поддерево дерева Д; если корень меньше, чем X, то X вносится в правое поддерево.
На рис. 9.10 показана соответствующая программа.
Теперь рассмотрим операцию удалить . Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину — дело не простое. Удаление листа можно на самом деле определить как операцию, обратную операции добавления листа:
удлист( Д1, X, Д2) :-
доблист( Д2, X, Д1).
Рис. 9.11. Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.
К сожалению, если X — это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит рис. 9.11. Вершина X имеет два поддерева Лев и Прав. После удаления вершины X в дереве образуется "дыра", и поддеревья Лев и Прав теряют свою связь с остальной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способна принять только одно из них.
Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты, то можно использовать следующую идею (рис. 9.12): если самую левую вершину Y поддерева Прав переместить из ее текущего положения вверх и заполнить ею пробел, оставшийся после X, то упорядоченность дерева не нарушится. Разумеется, та же идея сработает и в симметричном случае, когда перемещается самая правая вершина поддерева Лев.
|
|
|
Рис. 9. 2. Заполнение пустого места после удаления X.
На рис. 9.13 показана программа, реализующая операцию удаления элементов в соответствии с изложенными выше соображениями. Основную работу по перемещению самой левой вершины выполняет отношение
удмин( Дер, Y, Дер1)
Здесь Y — минимальная (т.е. самая левая) вершина дерева Дер, а Дер1 — то, во что превращается дерево Дер после удаления вершины Y.
Существует другой, элегантный способ реализация операции добавить и удалить . Отношение добавить можно сделать недетерминированным в том смысле, что новый элемент вводится на произвольный уровень дерева, а не только на уровень листьев. Правила таковы:
Для того, чтобы добавить X в двоичный справочник Д, необходимо одно из двух:
• добавить X на место корня дерева (так, что X станет новым корнем) или
|
|
|
• если корень больше, чем X, то внести X в левое поддерево, иначе — в правое поддерево.
уд( дер( nil, X, Прав), X, Прав).
уд( дер( Лев, X, nil), X, Лев).
уд( дер( Лев, 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. Удаление элемента из двоичного справочника.
Трудным моментом здесь является введение X на место корня. Сформулируем эту операций в виде отношения
добкор( Д, X, X1)
где X — новый элемент, вставляемый вместо корня в Д, а Д1 — новый справочник с корнем X. На рис. 9.14 показано, как соотносятся X, Д и Д1. Остается вопрос: что из себя представляют поддеревья L1 и L2 (или, соответственно, R1 и R2) на рис. 9.14?
Рис. 9.14. Внесение X в двоичный справочник в качестве корня.
Ответ мы получим, если учтем следующие ограничения на L1, L2:
• L1 и L2 — двоичные справочники;
• множество всех вершин, содержащихся как в L1, так и в L2, совпадает с множеством вершин справочника L;
|
|
|
• все вершины из L1 меньше, чем X; все вершены из L2 больше, чем X.
Отношение, которое способно наложить все эти ограничения на L1, L2, — это как раз и есть наше отношение добкор. Действительно, если бы мы вводили X в L на место корня, то поддеревьями результирующего дерева как раз и оказались бы L1 и L2. В терминах Пролога L1 и L2 должны быть такими, чтобы достигалась цель
добкор( L, X, дер( L1, X, L2) ).
Те же самые ограничения применимы к R1, R2:
добкор( R, X, дер( R1, X, R2) ).
На рис. 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справочник.
добавить( Д, X, Д1) :- % Добавить X на место корня
добкор( Д, X, Д1).
добавить( дер( L, Y, R), X, дер( L1, Y, R) ) :-
больше( Y, X), % Ввести X в левое поддерево
добавить( L, X, L1).
добавить( дер( L, Y, R), X, дер( L, Y, R1) ) :-
больше( X, Y), % Ввести X в правое поддерево
добавить( R, X, R1).
добкор( nil, X, дер( nil, X, nil) ). % Ввести X в пустое дерево
добкор( дер( L, Y, R), X, дер( L1, X, дер( 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. Внесение элемента на произвольный уровень двоичного справочника.
Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:
добавить( nil, 3, Д1), добавить( Д1, 5, Д2),
добавить( Д2, 1, Д3), добавить( Д3, 6, Д),
добавить( ДД, 5, Д).
Отображение деревьев
Так же, как и любые объекты данных в Прологе, двоичное дерево T может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель
write( T)
хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа — пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.
Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).
Рис. 9.16. (а) Обычное изображение дерева. (b) То же дерево, отпечатанное процедурой отобр (дуги добавлены для ясности).
Давайте определим процедуру
отобр( T)
так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:
Для того, чтобы отобразить непустое дерево T, необходимо:
(1) отобразить правое поддерево дерева T с отступом вправо на расстояние H;
(2) отпечатать корень дерева T;
(3) отобразить левое поддерево дерева T с отступом вправо на расстояние H.
Величина отступа H, которую можно выбирать по желанию, — это дополнительный параметр при отображении деревьев. Введем процедуру
отобр2( T, H)
печатающую дерево T с отступом на H пробелов от левого края листа. Связь между процедурами отобр и отобр2 такова:
отобр( T) :- отобр2( T, 0).
На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.
отобр( T) :-
отобр2( T, 0).
отобр2( nil, _ ).
отобр2( дер( L, X, R), Отступ) :-
Отступ2 is Отступ + 2,
отобр2( R, Отступ2),
tab( Отступ), write( X), nl,
отобр( L, Отступ2).
Рис. 9.17. Отображение двоичного дерева.
Упражнение
9.14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья — справа. Напишите (более сложную) процедуру для отображения дерева, ориентированного обычным образом, т.е. с корнем наверху и листьями внизу.
Графы
Представление графов
Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество вершин вместе с множеством ребер , причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами . Дуги задаются упорядоченными парами. Такие графы называются направленными . Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения. На рис. 9.18 показаны примеры графов.
В Прологе графы можно представлять различными способами. Один из них — каждое ребро записывать в виде отдельного предложения. Например, графы, показанные на рис. 9.18, можно представить в виде следующего множества предложений:
связь( а, b).
связь( b, с).
...
дуга( s, t, 3).
дуга( t, v, 1).
дуга( u, t, 2).
...
Другой способ — весь граф представлять как один объект. В этом случае графу соответствует пара множеств — множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро — парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра — функтор p. Тогда (ненаправленный) граф рис. 9.18 примет вид:
G1 = граф( [a, b, c, d],
[p( а, b), p( b, d), p( b, с), p( c, d)] )
Рис. 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]]
Здесь символы '->' и '/' — инфиксные операторы.
Какой из способов представления окажется более удобным, зависит от конкретного приложения, а также от того, какие операции имеется в виду выполнять над графами. Вот типичные операции:
• найти путь между двумя заданными вершинами;
• найти подграф, обладающий некоторыми заданными свойствами.
Примером последней операции может служить построение основного дерева графа. В последующих разделах, мы рассмотрим некоторые простые программы для поиска пути в графе и построения основного дерева.
Поиск пути в графе
Пусть G — граф, а А и Z — две его вершины. Определим отношение
путь( А, Z, G, P)
где P — ациклический путь между А и Z в графе G. Если G — граф, показанный в левой части рис. 9.18, то верно:
путь( a, d, G, [a, b, d] )
путь( а, d, G, [a, b, c, d] )
Поскольку путь не должен содержать циклов, любая вершина может присутствовать в пути не более одного раза. Вот один из методов поиска пути:
Для того, чтобы найти ациклический путь P между А и Z в графе G, необходимо:
Если А = Z , то положить P = [А], иначе найти ациклический путь P1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из P1.
В этой формулировке неявно предполагается, что существует еще одно отношение, соответствующее поиску пути со следующий ограничением: путь не должен проходить через вершины из некоторого подмножества (в данном случае P1) множества всех вершин графа. В связи с этим мы определим ещё одну процедуру:
путь1( А, P1, G, P)
Аргументы в соответствии с рис. 9.19 имеют следующий смысл:
• А — некоторая вершина,
• G — граф,
• P1 — путь в G,
• P — ациклический путь в G, идущий из А в начальную вершину пути P1, а затем — вдоль пути P1 вплоть до его конца.
Pис. 9.19. Отношение путь1: Путь — это путь между А и Z, в своей заключительной части он перекрывается с Путь1.
Между путь и путь1 имеется следующее соотношение:
путь( А, Z, G, P) :- путь1( А, [Z], G, P).
На рис. 9.19 показана идея рекурсивного определения отношения путь1. Существует "граничный" случай, когда начальная вершина пути P1 (Y на рис. 9.19) совпадает с начальной вершиной А пути P. Если же начальные вершины этих двух путей не совпадают, то должна существовать такая вершина X, что
(1) Y — вершина, смежная с X,
(2) X не содержится в P1 и
(3) для P выполняется отношение путь1( А, [X | P1], G, P).
путь( A, Z, Граф, Путь) :-
путь1( А, [Z], Граф, Путь).
путь1( А, [А | Путь1, _, [А | Путь1] ).
путь1( А, [Y | Путь1], Граф, Путь) :-
смеж( X, Y, Граф),
принадлежит( X, Путь1), % Условие отсутствия цикла
путь1( А, [ X, Y | Путь1], Граф, Путь).
Рис. 9.20. Поиск в графе Граф ациклического пути Путь из А в Z.
На рис. 9.20 программа показана полностью. Здесь принадлежит — отношение принадлежности элемента списку. Отношение
смеж( X, Y, G)
означает, что в графе G существует дуга, ведущая из X в Y. Определение этого отношения зависит от способа представления графа. Если G представлен как пара множеств (вершин и ребер)
G = граф( Верш, Реб)
то
смеж( X, Y, граф( Верш, Реб) ) :-
принадлежит( p( X, Y), Реб);
принадлежит( p( Y, X), Реб).
Классическая задача на графах — поиск Гамильтонова цикла, т.е. ациклического пути, проходящего через все вершины графа. Используя отношение путь, эту задачу можно решить так:
гамильтон( Граф, Путь) :-
путь( _, _, Граф, Путь),
всевершины( Путь, Граф).
всевершины( Путь, Граф) :-
not (вершина( В, Граф),
not принадлежит( В, Путь) ).
Здесь вершина( В, Граф) означает: В — вершина графа Граф.
Каждому пути можно приписать его стоимость. Стоимость пути равна сумме стоимостей входящих в него дуг. Если дугам не приписаны стоимости, то тогда, вместо стоимости, говорят о длине пути.
Для того, чтобы наши отношения путь и путь1 могли работать со стоимостями, их нужно модифицировать, введя дополнительный аргумент для каждого пути:
путь( А, Z, G, P, С)
путь1( A, P1, C1, G, P, С)
Здесь С — стоимость пути P, a C1 — стоимость пути P1. В отношении смеж также появится дополнительный аргумент, стоимость дуги. На рис. 9.21 показана программа поиска пути, которая строит путь и вычисляет его стоимость.
путь( А, 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, Граф, Путь, Ст).
Рис. 9.21. Поиск пути в графе: Путь — путь между А и Z в графе Граф стоимостью Ст.
Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости между вершинами Верш1, Верш2 графа Граф, задав цели
путь( Bepш1, Верш2, Граф, МинПуть, МинСт),
not( путь( Верш1, Верш2, Граф, _, Ст), Ст<МинСт )
Аналогично можно среди всех путей между вершинами графа найти путь максимальной стоимости, задав цели
путь( _, _, Граф, МаксПуть, МаксСт),
not( путь( _, _, Граф, _, Ст), Ст > МаксСт)
Заметим, что приведенный способ поиска максимальных и минимальных путей крайне неэффективен, так как он предполагает просмотр всех возможных путей и потому не подходит для больших графов из-за своей высокой временной сложности. В искусственном интеллекте задача поиска пути возникает довольно часто. В главах 11 и 12 мы изучим более сложные методы нахождения оптимальных путей.
Построение остовного дерева
Граф называется связным , если между любыми двумя его вершинами существует путь. Пусть G = (V, E) — связный граф с множеством вершин V и множеством ребep E. Остовное дерево графа G — это связный граф T = ( V, E'), где E' — подмножество E такое, что
(1) T — связный граф,
(2) в T нет циклов.
Выполнение этих двух условий гарантирует то, что T — дерево. Для графа, изображенного в левой части рис. 9.18, существует три остовных дерева, соответствующих следующим трем спискам ребер:
Дер1 = [а-b, b-c, c-d]
Дер2 = [а-b, b-d, d-с]
Дер3 = [а-b, b-d, b-c]
Здесь каждый терм вида X-Y обозначает ребро, соединяющее вершины X и Y. В качестве корня можно взять любую из вершин, указанных в списке. Остовные деревья представляют интерес, например в задачах проектирования сетей связи, поскольку они позволяют, имея минимальное число линий, установить связь между любыми двумя узлами, соответствующими вершинам графа.
Определим процедуру
остдерево( G, T)
где T — остовное дерево графа G. Будем предполагать, что G — связный граф. Можно представить себе алгоритмический процесс построения остовного дерева следующим образом. Начать с пустого множества ребер и постепенно добавлять новые ребра, постоянно следя за тем, чтобы не образовывались циклы. Продолжать этот процесс до тех пор, пока не обнаружится, что нельзя присоединить ни одного ребра, поскольку любое новое ребро порождает цикл. Полученное множество ребер будет остовным деревом. Отсутствие циклов можно обеспечить, если придерживаться следующего простого правила: ребро присоединяется к дереву только в том случае, когда одна из его вершин уже содержится в строящемся дереве, а другая пока еще не включена в него. Программа, реализующая эту идею, показана на рис. 9.22. Основное отношение, используемое в этой программе, — это
расширить( Дер1, Дер, G)
Здесь все три аргумента — множества ребер. G — связный граф; Дер1 и Дер — два подмножества G, являющиеся деревьями. Дер — остовное дерево графа G, полученное добавлением некоторого (может быть пустого) множества ребер из G к Дер1. Можно сказать, что "Дер1 расширено до Дер".
% Построение остовного дерева графа
%
% Деревья и графы представлены списками
% своих ребер, например:
% Граф = [а-b, b-с, b-d, c-d]
остдерево( Граф, Дер) :- % Дер - остовное дерево Граф'а
принадлежит( Ребро, Граф),
расширить( [Ребро], Дер, Граф).
расширить( Дер1, Дер, Граф) :-
добребро( Дер1, Дер2, Граф),
расширить( Дер2, Дер, Граф).
расширить( Дер, Дер, Граф) :-
not добребро( Дер, _, Граф).
% Добавление любого ребра приводит к циклу
добребро( Дер, [А-В | Дер], Граф) :-
смеж( А, В, Граф), % А и В - смежные вершины
вершина( А, Дер). % А содержится в Дер
not вершина( В, Дер). % А-В не порождает цикла
смеж( А, В, Граф) :-
принадлежит ( А-В, Граф);
принадлежит ( В-А, Граф).
вершина( А, Граф) :- % А содержится в графе, если
смеж( А, _, Граф). % А смежна какой-нибудь вершине
Pис. 9.22. Построение остовного дерева: алгоритмический подход. Предполагается, что Граф — связный граф.
Интересно, что можно написать программу построения остовного дерева совершенно другим, полностью декларативным способом, просто формулируя на Прологе некоторые математические определения. Допустим, что как графы, так и деревья задаются списками своих ребер, как в программе рис. 9.22. Нам понадобятся следующие определения:
(1) T является остовным деревом графа G, если
• T — это подмножество графа G и
• T — дерево и
• T "накрывает" G, т.е. каждая вершина из G содержится также в T.
(2) Множество ребер T есть дерево, если
• T — связный граф и
• T не содержит циклов.
Эти определения можно сформулировать на Прологе (с использованием нашей программы путь из предыдущего раздела) так, как показано на рис. 9.23. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.
% Построение остовного дерева
% Графы и деревья представлены списками ребер.
остдерево( Граф, Дер) :-
подмнож( Граф, Дер),
дерево( Дер),
накрывает( Дер, Граф).
дерево( Дер) :-
связи( Дер),
not имеетцикл( Дер).
связи( Дер) :-
not ( вершина( А, Дер), вершина( В, Дер),
not путь( А, А, Дер, _ ) ).
имеетцикл( Дер) :-
смеж( А, В, Дер),
путь( А, В, Дер, [А, X, Y | _ ). % Длина пути > 1
накрывает( Дер, Граф) :-
not ( вершина( А, Граф), not вершина( А, Дер) ).
подмнож( [], []).
подмнож( [ X | L], S) :-
подмнож( L, L1),
( S = L1; S = [ X | L1] ).
Рис. 9.23. Построение остовного дерева: "декларативный подход".
Отношения вершина и смеж см. на рис. 9. 22.
Упражнение
9.15. Рассмотрите остовные деревья в случае, когда каждому ребру графа приписана его стоимость. Пусть стоимость остовного дерева определена как сумма стоимостей составляющих его ребер. Напишите программу построения для заданного графа его остовного дерева минимальной стоимости.
Резюме
В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе
• Списки:
варианты представления списков
сортировка списков:
сортировка методом "пузырька"
сортировка со вставками
быстрая сортировка
эффективность этих процедур
• Представление множеств двоичными деревьями и двоичными справочниками:
поиск элемента в дереве
добавление элемента
удаление элемента
добавление в качестве листа или корня
сбалансированность деревьев и его связь с эффективностью этих операций
отображение деревьев
• Графы:
представление графов
поиск пути в графе
построение остовного дерева
Литература
В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. Хороший и краткий обзор соответствующих алгоритмов и результатов их математического анализа можно найти в Gonnet (1984).
Прологовская программа для внесения нового элемента на произвольный уровень дерева (раздел 9.3) была впервые показана автору М. Ван Эмденом (при личном общении).
Aho А. V., Hopcroft J. E. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. — М.: Мир, 1979.]
Aho А. V., Hopcroft J. E. 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.
Глава 10
Дата добавления: 2018-05-01; просмотров: 392; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!