V Более сложные структуры данных

Введение

Как и в части III, в этой части мы рассмотрим структуры данных, которые хранят изменяющиеся множества - но их анализ будет несколько более сложным. В частности, в двух главах мы применяем технику амортизационного анализа (глава 18).

В главе 19 мы рассматриваем Б-деревья - сбалансированные деревья определённого вида, удобные для хранения информации на дисках. Специфика дисков в том, что важно не столько время вычислений, сколько число операций чтения/записи блоков. Число таких операций пропорционально высоте дерева, и потому высоту Б-деревьев важно поддерживать небольшой.

В главах 20 и 21 мы рассматриваем различные реализации сливаемых куч - структуры данных, которая поддерживает операции добавления элемента (Insert), отыскания минимума (Minimum), удаления минимального элемента (Extract-Min) и объединения (Union) двух куч. Помимо этих операций, могут быть эффективно реализованы также операции удаления элемента и уменьшения его ключа.

Биномиальные кучи (глава 20) выполняют каждую операцию (в худшем случае) за время О (lgra), где га - число элементов в куче (или в двух сливаемых кучах). Их преимущество (по сравнению с двоичными кучами) состоит в возможности быстрого слияния двух куч (для двоичных куч это требует времени в (га)).

Фибоначчиевы кучи (глава 21) ещё более эффективны (по крайней мере теоретически: имеют лучшую асимптотику). Правда, здесь речь идёт уже об учётной стоимости операций. Операции Insert, Minimum и Union имеет учётную (а также фактическую) стоимость 0(1). Операции Extract-Min и Delete имеют учётную стоимость О (lgra). Наиболее существенна возможность быстро выполнять операцию Decrease-Key (её учётная стоимость есть 0(1)). Именно благодаря этому многие (на сегодняшний

день) «рекордно» быстрые алгоритмы обработки графов используют фибоначчиевы кучи.

Наконец, в главе 22 мы рассматриваем структуры данных для хранения непересекающихся множеств (отношений эквивалентности). Мы имеем в виду следующее: имеется некоторое конечное множество, разбитое на классы. В начальный момент каждый класс содержит по одному элементу; затем их можно попарно объединять. В любой момент один из элементов класса считается его представителем; операция Find-Set (ж) даёт представитель класса, содержащего ж, операция Union (ж, у) объединяет два класса. Оказывается, что весьма простое представление этой информации в виде корневого дерева весьма эффективно: последовательность из т операций требует времени 0(та(т, га)), где а(т, га) - исключительно медленно растущая функция. Правда, доказать эту оценку весьма непросто (несмотря на простоту самой структуры данных), и мы ограничимся доказательство чуть менее сильной оценки.

Разумеется, этот раздел книги никак не претендует на полноту - множество интересных структур данных в него не вошли. Укажем некоторые из них:

•Структура данных, поддерживающая операции отыскания минимума, максимума, добавления и удаления элемента, поиска, удаления минимального и максимального элементов, поиск предыдущего и следующего элементов за время О (lg lg га) в худшем случае - в предположении, что все ключи являются целыми числами от 1 до га (ван Эмде Боас [194]).

•Динамические деревья (dynamic trees), которые предложили Слеатор и Тарьян [177] (см. также Тарьян [188]). Эта структура данных хранит лес из непересекающихся корневых деревьев. Каждое ребро каждого дерева имеет некоторый вещественную стоимость. Можно искать родителей, корни, стоимости рёбер, а также минимальную стоимость ребра на пути от данной вершины к корню. Можно удалять рёбра, менять стоимости рёбер на пути к корню, прививать корень дерева к другому дереву, а также делать заданную вершину корнем дерева, в котором она находится. Все эти операции можно реализовать с учётной стоимостью О (lgra); более сложная реализация гарантирует время работы О (lgra) и в худшем случае.

•Расширяющиеся деревья (splay trees) также предложили Слеатор и Тарьян [178] (см. также Тарьян [188]). Они представляют собой двоичные деревья с обычными для деревьев поиска операциями; их учётная стоимость составляет О (lgra) (за счёт того, что время от времени дерево подвергается балансировке). Расширяющиеся деревья можно применить при реализации динамических деревьев.

•Структуры данных с сохранением предыдущих версий (persis-