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

Содержание книги "Усовершенствованные структуры данных "

От авторов перевода
Предисловие
Основные понятия
Примеры кода
Глава 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. Список публикаций
Предметный указатель