Author(s): Брасс П.
Publisher: ДМК
Year: 2023
Language: Russian
City: М.
От авторов перевода
Предисловие
Основные понятия
Примеры кода
Глава 1
Элементарные структуры
1.1. Стек
1.2. Очередь
1.3. Двусторонняя очередь
1.4. Динамическое выделение памяти для элементов
1.5. Теневые копии структур в массиве
Глава 2
Деревья поиска
2.1. Две модели деревьев поиска
2.2. Общие свойства и преобразования
2.3. Высота дерева поиска
2.4. Основные операции: поиск, добавление, удаление
2.5. Возврат от листа к корню
2.6. Повторяющиеся ключи
2.7. Интервалы ключей
2.8. Построение оптимальных деревьев поиска
2.9. Преобразование деревьев в списки
2.10. Удаление деревьев
Глава 3
Выровненные деревья поиска
3.1. Выровненные по высоте деревья
3.2. Выровненные по весу деревья
3.3. (a, b)- и B-деревья
3.4. Красно-черные деревья и деревья почти оптимальной высоты
3.5. Нисходящее выравнивание красно-черных деревьев
3.6. Деревья с постоянным временем обновления в заранее известном месте
3.7. Пальцевые деревья и поуровневое связывание
3.8. Деревья с частичной перестройкой: средняя оценка сложности
3.9. Дерево с всплывающими узлами: изменяемая структура данных
3.10. Списки с пропуском элементов: вероятностные структуры данных
3.11. Соединение и разделение выровненных деревьев поиска
Глава 4
Древовидные структуры на множестве интервалов
4.1. Деревья пересекающихся отрезков
4.2. Деревья полуоткрытых интервалов
4.3. Деревья объединения интервалов
4.4. Деревья сумм взвешенных интервалов
4.5. Деревья поиска интервалов с ограниченной максимальной суммой весов
4.6. Деревья прямоугольных областей
4.7. Деревья многомерных интервалов
4.8. Блочные структуры данных
4.9. Подсчет точек и модель полугруппы
4.10. kd-деревья и связанные с ними структуры
Глава 5
Кучи
5.1. Куча как выровненное дерево
5.2. Куча в массиве
5.3. Куча как упорядоченное и полуупорядоченное дерево
5.4. Левосторонние кучи
5.5. Косые кучи
5.6. Двоичные кучи
5.7. Изменение ключей в кучах
5.8. Кучи Фибоначчи
5.9. Кучи оптимальной сложности
5.10. Двусторонние и многомерные кучи
5.11. Связанные с кучей и постоянным временем обновления структуры
Глава 6
Системы непересекающихся множеств и связанные с ними структуры
6.1. Непересекающиеся множества: объединение классов разделов
6.2. Система непересекающихся множеств с поддержкой копирования и динамическими деревьями интервалов
6.3. Разделение списка
6.4. Проблемы ориентированных корневых деревьев
6.5. Поддержание линейного порядка
Глава 7
Преобразования структуры данных
7.1. Создание динамических структур
7.2. Динамические структуры с сохранением истории
Глава 8
Структуры данных для строк
8.1. Проверки и сжимаемые проверки
8.2. Словари, допускающие появление ошибок в запросах
8.3. Суффиксные деревья
8.4. Суффиксные массивы
Глава 9
Хеш-таблицы
9.1. Основные хеш-таблицы и разрешение конфликтов
9.2. Универсальные семейства хеш-функций
9.3. Идеальные хеш-функции
9.4. Хеш-деревья
9.5. Расширяемое хеширование
9.6. Проверка принадлежности ключей и фильтры Блума
Глава 10
Приложение
10.1. Ссылочная машина и другие модели вычислений
10.2. Модели внешней памяти и алгоритмы без учета кеш-памяти
10.3. Названия структур данных
10.4. Решение линейных рекуррентных соотношений
10.5. Медленно растущие функции
Глава 11
Список публикаций
Предметный указатель
