Prolog
Шрифт:
доб_а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.
Рис. 10. 10. Вставление элемента в AVL-справочник. В этой
программе предусмотрено, что попытка повторного вставления
элемента терпит неудачу. По поводу процедуры соединить см.
рис. 10.9.
деревья представляйте в виде термов
д( Лев, Кор, Прав) или nil.
Посмотреть ответ
Резюме
2-3 деревья и AVL-деревья, представленные в настоящей главе, - это примеры сбалансированных
Сбалансированные или приближенно сбалансированные деревья гарантируют эффективное выполнение трех основных операций над деревьями: поиск, добавление и удаление элемента. Время выполнения этих операций пропорционально log n, где n– число вершин дерева.
Литература
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.]
Назад | Содержание | Вперёд
Назад | Содержание | Вперёд
Глава 11.
ОСНОВНЫЕ СТРАТЕГИИ РЕШЕНИЯ ЗАДАЧ
В данной главе мы сосредоточим свое внимание на одной общей схеме для представления задач, называемой пространством состояний. Пространство состояний - это граф, вершины которого соответствуют ситуациям, встречающимся в задаче ("проблемные ситуации"), а решение задачи сводится к поиску пути в этом графе. Мы изучим на примерах, как формулируются задачи в терминах пространства состояний, а также обсудим общие методы решения задач, представленных в рамках этого формализма. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. В этой главе будут представлены две основные стратегии перебора альтернатив, а именно поиск в глубину и поиск в ширину.