Читаем Prolog полностью

9. 15.    Рассмотрите остовные деревья в случае, когда каждому ребру графа приписана его стоимость. Пусть стоимость остовного дерева определена как сумма стоимостей составляющих его ребер. Напишите программу построения для заданного графа его остовного дерева минимальной стоимости.

Резюме

В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе

Списки:

        варианты представления списков

        сортировка списков:

                сортировка методом "пузырька"

                сортировка со вставками

                быстрая сортировка

                эффективность этих процедур

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

        поиск элемента в дереве

        добавление элемента

        удаление элемента

        добавление в качестве листа или корня

        сбалансированность деревьев и его связь с

                эффективностью этих операций

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

Графы:

        представление графов

        поиск пути в графе

        построение остовного дерева

Литература

В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в 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.

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

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

Глава 10

УСОВЕРШЕНСТВОВАННЫЕ МЕТОДЫ

ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ ДЕРЕВЬЯМИ

В данной главе мы рассмотрим усовершенствованные методы представления множеств при помощи деревьев. Основная идея состоит в том, чтобы поддерживать сбалансированности или приближенную сбалансированность дерева, с тем чтобы избежать вырождения его в список. Механизмы балансировки деревьев гарантируют, даже в худшем случае, относительно быстрый доступ к элементам данных, хранящихся в дереве, при логарифмическом порядке времени доступа. В этой главе изложено два таких механизма: двоично-троичные (кратко, 2-3) деревья и AVL-деревья. (Для изучения остальных глав понимание данной главы не обязательно.)

10. 1.    Двоично - троичные справочники

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

Рис. 10. 1.  Полностью разбалансированный двоичный справочник.

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

Перейти на страницу:

Похожие книги

Слово о полку Игореве
Слово о полку Игореве

Исследование выдающегося историка Древней Руси А. А. Зимина содержит оригинальную, отличную от общепризнанной, концепцию происхождения и времени создания «Слова о полку Игореве». В книге содержится ценный материал о соотношении текста «Слова» с русскими летописями, историческими повестями XV–XVI вв., неординарные решения ряда проблем «слововедения», а также обстоятельный обзор оценок «Слова» в русской и зарубежной науке XIX–XX вв.Не ознакомившись в полной мере с аргументацией А. А. Зимина, несомненно самого основательного из числа «скептиков», мы не можем продолжать изучение «Слова», в частности проблем его атрибуции и времени создания.Книга рассчитана не только на специалистов по древнерусской литературе, но и на всех, интересующихся спорными проблемами возникновения «Слова».

Александр Александрович Зимин

Древнерусская литература / Прочая старинная литература / Прочая научная литература / Древние книги / Литературоведение / Научная литература