[ДМК] Усовершенствованные структуры данных [Брасс П.]

Посмотрел английский вариант. Книга представляет собой серьёзный алгоритмический курс как минимум для магистратуры. Для каждой из структур разобрана схема, в виде теорем математически доказаны характеристики (например, максимальная высота красно-черного дерева), и временная сложность основных алгоритмов (например, показано логарифмическое время поиска, вставки и удаления для красно-черного дерева). Все примеры действительно на C, идут прямо по тексту в виде кусков кода, а не полностью законченных программ. Т.е., функции main и выделения-освобождения памяти вы не увидите, поэтому код, больше похожий на псевдо-код, перед запуском необходимо дополнять нужными директивами препроцессора и недостающими функциями.
Перевёл гуглом содержание:

Спойлер: перевод содержания тут

1 Элементарные структуры 1
1.1 Стек 1
1.2 Очередь 8
1.3 Двусторонняя очередь 16
1.4 Динамическое размещение узлов 16
1.5 Теневые копии структур на основе массивов 18
2 Деревья поиска 23
2.1 Две модели деревьев поиска 23
2.2 Общие свойства и преобразования 26
2.3 Высота дерева поиска 29
2.4 Базовый поиск, вставка и удаление 31
2.5 Возврат из листа в корень 35
2.6 Работа с неуникальными ключами 37
2.7 Запросы ключей в интервале 38
2.8 Построение оптимальных деревьев поиска 40
2.9 Преобразование деревьев в списки 47
2.10 Удаление дерева 48
3 Сбалансированные деревья поиска 50
3.1 Деревья со сбалансированной высотой 50
3.2 Деревья со сбалансированным весом 61
3.3 (а, б)- и В-деревья 72
3.4 Красно-черные деревья и деревья почти оптимальной высоты 89
3.5 Перебалансировка сверху вниз для красно-черных деревьев 101
3.6 Деревья с постоянным временем обновления в известном местоположении 111
3.7 Деревья пальцев и связывание уровней 114
3.8 Деревья с частичной перестройкой: амортизированный анализ 119
3.9 Деревья расширения: адаптивные структуры данных 122
3.10 Списки пропуска: рандомизированные структуры данных 135
3.11 Объединение и разделение сбалансированных деревьев поиска 143
4. Древовидные структуры для наборов интервалов 148
4.1 Интервальные деревья 148
4.2 Деревья сегментов 154
4.3 Деревья для объединения интервалов 162
4.4 Деревья для сумм взвешенных интервалов 169
4.5 Деревья для запросов максимальной суммы с ограничением по интервалам 174
4.6 Ортогональные деревья диапазонов 182
4.7 Деревья сегментов более высокого измерения 196
4.8 Другие системы строительных блоков 199
4.9 Подсчет диапазонов и полугрупповая модель 202
4.10 kd-деревья и родственные структуры 204
5 Кучи 209
5.1 Сбалансированные деревья поиска как кучи 210
5.2 Кучи на основе массивов 214
5.3 Деревья с кучей порядка и деревья с полуупорядочением 221
5.4 Левые кучи 227
5.5 Косые кучи 235
5.6 Биномиальные кучи 239
5.7 Замена ключей в кучах 248
5.8 Кучи Фибоначчи 250
5.9 Кучи оптимальной сложности 262
5.10 Кучи с двусторонней структурой и многомерные кучи 267
5.11 Структуры, связанные с кучей, с постоянными обновлениями 271
6 Union-Find и родственные структуры 278
6.1 Union-Find: объединение классов раздела 279
6.2 Union-Find с копиями и деревьями динамических сегментов 293
6.3 Разделение списков 303
6.4. Задачи на деревьях, ориентированных на корни 306
6.5 Поддержание линейного порядка 317
7 Преобразования структур данных 321
7.1 Создание динамических структур 321
7.2 Обеспечение устойчивости структур 330
8 Структуры данных для строк 335
8.1 Tries и сжатые tries 336
8.2 Словари, допускающие ошибки в запросах 356
8.3 Деревья суффиксов 360
8.4 Массивы суффиксов 367
9 Хеш-таблицы 374
9.1 Основные хеш-таблицы и разрешение конфликтов 374
9.2 Универсальные семейства хеш-функций 380
9.3 Идеальные хеш-функции 391
9.4 Хэш-деревья 397
9.5 Расширяемое хеширование 398
9.6 Тестеры принадлежности и фильтры Блума 402
10 Приложение 406
10.1 Машина указателей и альтернативные вычисления
Модели 406
10.2 Модели внешней памяти и Cache-Oblivious
Алгоритмы 408
10.3 Именование структур данных 409
10.4 Решение линейных повторений 410
10.5 Очень медленно растущие функции 412
11 Ссылки 415
Индекс авторов 441
Тематический указатель 455