Усовершенствованные структуры данных

Петер Брасс

Усовершенствованные 
структуры данных

Advanced Data Structures

PETER BRASS

City College of New York

Москва, 2023

ПЕТЕР БРАСС

Нью-Йоркский городской колледж

Усовершенствованные 
структуры данных

УДК   004.422.63
ББК   32.973.05
Б87

Б87  Петер Брасс

Усовершенствованные структуры данных / пер. с англ. Е. В. Борисова, С. В.Чугунова, А. Н. Киселева. – М.: ДМК Пресс, 2023. – 426 с.: ил.

            ISBN 978-5-97060-873-9

В книге приводится всесторонний анализ идей и деталей реализации 
структур данных как важнейшей составляющей прикладных алгоритмов. 
Обсуждаются не только эффективные способы реализации операций над 
множествами чисел, интервалов или строк, представленных в виде различных поисковых структур данных – деревьев, множеств интервалов, 
кусочно-постоянных функций, прямоугольных областей, непересекающихся подмножеств, куч, хеш-таблиц, но и динамизация и персистентность (сохраняемость) структур.
Структуры данных впервые рассматриваются не просто как вспомогательный материал для иллюстрации методологии объектно ориентированного программирования, а как ключевой вопрос разработки алгоритмов. Многочисленные примеры кода на языке C и более 500 ссылок на 
первоисточники делают книгу исключительно ценной.

 УДК  004.422.63
 ББК  32.973.05

Copyright Original English language edition published by Cambridge University 
Press is part of the University of Cambridge. Russian language edition copyright 
© 2023 by DMK Press. All rights reserved.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без 
письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку 
вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи 
с этим издательство не несет ответственности за возможные ошибки, связанные 
с использованием книги.

ISBN 978-0-52188-037-4 (англ.) 
 © Peter Brass, 2008 
ISBN 978-5-97060-873-9 (рус.)  
 © Оформление, перевод на русский язык,  

 издание, ДМК Пресс, 2023

Посвящается моим родителям

Гизелле и Хельмуту Брассам

Оглавление

От авторов перевода .............................................................................................................8
Предисловие .........................................................................................................................10

Основные понятия .........................................................................................................12
Примеры кода .................................................................................................................14

Глава 1. Элементарные структуры ....................................................................................16

1.1. Стек ...........................................................................................................................16
1.2. Очередь ....................................................................................................................23
1.3. Двусторонняя очередь .............................................................................................30
1.4. Динамическое выделение памяти для элементов ................................................30
1.5. Теневые копии структур в массиве ........................................................................32

Глава 2. Деревья поиска .....................................................................................................37

2.1. Две модели деревьев поиска ..................................................................................37
2.2. Общие свойства и преобразования ........................................................................40
2.3. Высота дерева поиска ..............................................................................................43
2.4. Основные операции: поиск, добавление, удаление ..............................................44
2.5. Возврат от листа к корню ........................................................................................49
2.6. Повторяющиеся ключи ...........................................................................................50
2.7. Интервалы ключей ...................................................................................................51
2.8. Построение оптимальных деревьев поиска ..........................................................53
2.9. Преобразование деревьев в списки .......................................................................59
2.10. Удаление деревьев .................................................................................................60

Глава 3. Выровненные деревья поиска ............................................................................62

3.1. Выровненные по высоте деревья ...........................................................................62
3.2. Выровненные по весу деревья ................................................................................72
3.3. (a, b)- и B-деревья ....................................................................................................82
3.4. Красно-черные деревья и деревья почти оптимальной высоты .........................96
3.5. Нисходящее выравнивание красно-черных деревьев ........................................107
3.6. Деревья с постоянным временем обновления в заранее известном месте ......116
3.7. Пальцевые деревья и поуровневое связывание ..................................................118
3.8. Деревья с частичной перестройкой: средняя оценка сложности ......................123
3.9. Дерево с всплывающими узлами: изменяемая структура данных ....................126
3.10. Списки с пропуском элементов: вероятностные структуры данных ..............137
3.11. Соединение и разделение выровненных деревьев поиска ..............................144

Глава 4. Древовидные структуры на множестве интервалов ................................... 149

4.1. Деревья пересекающихся отрезков ......................................................................149
4.2. Деревья полуоткрытых интервалов .....................................................................154
4.3. Деревья объединения интервалов .......................................................................161
4.4. Деревья сумм взвешенных интервалов ...............................................................168
4.5. Деревья поиска интервалов с ограниченной максимальной суммой весов .....173
4.6. Деревья прямоугольных областей ........................................................................178
4.7. Деревья многомерных интервалов ......................................................................190
4.8. Блочные структуры данных ..................................................................................193

Оглавление  7

4.9. Подсчет точек и модель полугруппы ....................................................................195
4.10. kd-деревья и связанные с ними структуры ........................................................197

Глава 5. Кучи ...................................................................................................................... 202

5.1. Куча как выровненное дерево ..............................................................................203
5.2. Куча в массиве........................................................................................................207
5.3. Куча как упорядоченное и полуупорядоченное дерево .....................................213
5.4. Левосторонние кучи ..............................................................................................218
5.5. Косые кучи .............................................................................................................225
5.6. Двоичные кучи ......................................................................................................228
5.7. Изменение ключей в кучах ...................................................................................236
5.8. Кучи Фибоначчи ....................................................................................................238
5.9. Кучи оптимальной сложности ..............................................................................248
5.10. Двусторонние и многомерные кучи ..................................................................253
5.11. Связанные с кучей и постоянным временем обновления структуры .............257

Глава 6. Системы непересекающихся множеств и связанные с ними структуры .. 263

6.1. Непересекающиеся множества: объединение классов разделов .......................264
6.2. Система непересекающихся множеств с поддержкой копирования 
и динамическими деревьями интервалов ..........................................................277

6.3. Разделение списка .................................................................................................287
6.4. Проблемы ориентированных корневых деревьев ..............................................291
6.5. Поддержание линейного порядка ........................................................................301

Глава 7. Преобразования структуры данных ................................................................ 305

7.1. Создание динамических структур ........................................................................305
7.2. Динамические структуры с сохранением истории .............................................314

Глава 8. Структуры данных для строк ........................................................................... 319

8.1. Проверки и сжимаемые проверки .......................................................................320
8.2. Словари, допускающие появление ошибок в запросах ......................................337
8.3. Суффиксные деревья .............................................................................................341
8.4. Суффиксные массивы ............................................................................................347

Глава 9. Хеш-таблицы ....................................................................................................... 355

9.1. Основные хеш-таблицы и разрешение конфликтов ...........................................355
9.2. Универсальные семейства хеш-функций ............................................................360
9.3. Идеальные хеш-функции ......................................................................................370
9.4. Хеш-деревья ...........................................................................................................375
9.5. Расширяемое хеширование ..................................................................................376
9.6. Проверка принадлежности ключей и фильтры Блума .......................................380

Глава 10. Приложение ...................................................................................................... 383

10.1. Ссылочная машина и другие модели вычислений ............................................383
10.2. Модели внешней памяти и алгоритмы без учета кеш-памяти ........................385
10.3. Названия структур данных .................................................................................386
10.4. Решение линейных рекуррентных соотношений .............................................386
10.5. Медленно растущие функции .............................................................................388

Глава 11. Список публикаций .......................................................................................... 390
Предметный указатель .................................................................................................... 423

От авторов перевода

Это не первый наш опыт перевода книги, изданной много лет назад (Вирт, Гуткнехт). Но тем не менее мы взялись за перевод этой якобы старой книги, изданной 
14 лет назад, потому что она не потеряла своей ценности и по сей день представляет интерес не только для профессионалов, но и для студентов, поскольку в ней подробно описывается, как путем незначительных усовершенствований давно и хорошо известных программистам структур данных можно добиться существенной 
эффективности работы с ними, что автор подкрепляет еще и доказательствами.
В сущности, книга представляет собой обзор различных способов модернизации давно известных структур данных с целью повышения их производительности. Поскольку в книге по большей части речь идет об оценке времени вычисления 
алгоритмов, то в таких случаях она подразумевается неявно. В тех же случаях, когда 
речь идет об оценке затрат памяти алгоритма, это явно оговаривается.
В целом книга представляет собой довольно полный обзор различных методов и 
приемов, позволяющих в той или иной степени ускорить работу с традиционными 
структурами данных, приводя необходимые обоснования (доказательства) их эффективности и во многих случаях – алгоритмы их реализации на языке программирования C. К сожалению, автор нередко приводит вместо программной реализации алгоритмов их словесное описание, что несколько затрудняет их понимание.
Книга может послужить хорошим справочником для всех тех, кто хочет понять, 
за счет каких приемов и методов можно ускорить работу с общеизвестными структурами данных.
Большинство так называемых автором «теорем» – это не столько теоремы, сколько выводы из предшествующих этим «теоремам» рассуждений. Книга насыщена 
такими «теоремами», но без доказательств. Обоснования этих «теорем» не всегда 
точны и убедительны. Те читатели, кто не интересуются ими, могут довериться 
автору и просто пропустить их. Ну а тем, кто хочет разобраться в них досконально, придется приложить определенные усилия или обратиться к многочисленным 
первоисточникам.
Конечно, эта книга адресована не столько программистам-любителям, сколько 
профессионалам, включая преподавателей и студентов, а также другим специалистам, интересующимся этой темой. Нужно сказать, что эта книга не для всех, а 
только для тех, кто хочет понять, с помощью каких методов и приемов можно достичь значительного ускорения работы алгоритмов с давно и многим известными 
структурами данных большого объема, включая базы данных.
Эта книга придется не всем по зубам, но мы приложили максимум усилий для 
того, чтобы ее перевод на русский язык хотя бы немного расширил круг ее читателей, и все найдут в ней немало познавательного и полезного.
О переводе
В главе 10 автор совершенно справедливо говорит о том, что термины и понятия в 
оригинальных работах не всегда удачны. Поэтому при переводе мы, конечно же, старались придерживаться авторской терминологии и тех оригинальных работ, на которые он ссылается, но изредка позволяли себе употреблять более понятные, с нашей 
точки зрения, русскоязычные термины. Что из этого получилось, судить читателю.
Несмотря на то что книга может заинтересовать довольно узкий круг читателей, мы надеемся, что наш перевод несколько расширит этот круг. Оригинал книги 
представляет собой скорее конспект лекций, чем детально продуманную монографию. Мы постарались превратить ее в полноценную монографию и, надеемся, 
интересную книгу для более широкого круга читателей – от студентов и препо

От авторов перевода  9

давателей до профессиональных программистов (специалистов), которые, как мы 
думаем, не разочаруются в ней.
В предисловии к книге автор пишет, что она родилась из его набросков лекций 
по данной теме. И к сожалению, этот набросочный стиль изложения материала 
отчасти сохранился и в самой книге. Поэтому при переводе книги нам пришлось 
немало потрудиться, чтобы превратить авторские наброски в полноценную монографию, качество которой оценит наш читатель.
Несколько слов о том, что красной нитью проходит по всей книге, – это оценка пространственно-временнóй сложности алгоритмов. Для них обычно используются обозначения: O – верхняя асимптотическая оценка сложности для худшего случая, Ω – нижняя асимптотическая оценка для худшего случая и Θ – жесткая 
асимптотическая оценка, когда сложность алгоритма для худшего случая не может 
выходить за пределы определяемых ею границ. Кроме того, нередко в книге идет 
речь об амортизированной (amortized) оценке вычислений, которую мы называли 
средней или усредненной. Чаще всего речь в книге идет именно об асимптотической оценке временнóй сложности алгоритмов для худшего случая и лишь изредка 
оценивается нижняя, жесткая, средняя и пространственная сложность алгоритмов.
При переводе книги мы позволили себе ради ее улучшения, помимо прочих незначительных вольностей, пронумеровать все непронумерованные авторские рисунки, а также обширный список публикаций.

Терминология
Сложность алгоритма – это оценка его стоимости, цены и прочих затрат 
времени или памяти.
Временнáя сложность – это количество выполняемых операций или просто 
время их выполнения.
Пространственная сложность – это затраты памяти на выполнение операций.
Чаще всего автор имеет в виду временнýю сложность.

hieght balanced tree – выровненное по высоте дерево или равновысокое 
дерево.
weight balanced tree – уравновешенное или равновесное дерево.
rebalancing – выравнивание.

Формулы
Некоторые несложные «многоэтажные» математические формулы в виде 
дробей мы иногда заменяли строчной записью, конечно же, без потери их 
смысла.
Так, например, 

                                                              –1
–––––––––––––––––––––––––––––  log n
                                          (α log α + (1 – α)log(1 – α))

мы заменили на

–1/(α log α + (1 – α)log(1 – α)) log n.

Е. В. Борисов, С. В. Чугунов,
Март, 2021

Предисловие

Эта книга – учебник для слушателей курсов по структурам данных. Структура данных – это метод1 представления данных для выполнения над ними 
некоторого набора операций. Классический пример структуры данных – 
это множество распознаваемых по значению ключа элементов в виде пар 
(ключ, элемент), которые можно добавлять, удалять или искать в этом множестве по заданному ключу. Структура, поддерживающая такие операции, 
называется словарем (dictionary). Словари могут быть реализованы разными способами, с разной степенью сложности и разными дополнительными 
операциями. Во многих первоисточниках было предложено и исследовано 
множество видов словарей, и некоторые из них2 мы  рассмотрим в этой 
книге.
Вообще говоря, структура данных – это своего рода набор высокоуровневых операций некоторой виртуальной машины: если алгоритм многократно выполняет некоторые операции, можно определить, какие из них 
выполняются чаще всего и как их лучше реализовать. Таким образом, 
основная задача структур данных – как реализовать набор операций над 
ними, предполагаемый результат которых нам известен.
Сегодня нет недостатка в книгах, в названии которых есть словосочетание «структуры данных», но они лишь поверхностно касаются этой 
темы, затрагивая только простейшие структуры – стек, очередь и некоторые виды выровненных деревьев поиска с изрядным количеством пафоса 
(handwaving). Серьезный интерес к структурам данных начали проявлять в 
1970-х годах, а в первой половине 1980-х почти в каждом номере журнала 
Communications ACM была статья о них. Структуры данных стали центральной темой, отдельным пунктом в классификаторе информатики3 и стандартной частью учебных программ по информатике4. С выходом книги 
Вирта «Структуры данных + Алгоритмы = Программы» термин «алгоритмы 
и структуры данных» стал общепринятым в учебниках по этой теме. Правда, единственная монография Овермарса 1983 года [450], посвященная 
именно алгоритмическому аспекту структур данных, до сих пор находится в печати; это своего рода рекорд для серии книг LNCS (Lecture Notes in 
Computer Science). Структурам данных уделяется внимание во многих приложениях и прежде всего в базах данных как индексным структурам. В том 
же контексте в монографиях Самета [482, 483] были изучены структуры для 

1 
Эта книга не об объектно ориентированном программировании, поэтому термины «метод» и 
«объект» употребляются в ней в самом обычном смысле.
2 
 Наиболее интересные и значимые. – Прим. перев.
3 
Классификационный код E.1. «Структуры данных». К сожалению, Классификатор информатики 
слишком груб, чтобы быть полезным.
4 
ABET (Accreditation Board for Engineering and Technology, Inc. – Прим. перев.) по-прежнему 
причисляет их к одной из пяти основных тем: алгоритмы, структуры данных, разработка ПО, 
языки программирования и архитектура компьютеров.