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

Description

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