Усовершенствованные структуры данных (5000,00 руб.)

Стр.5

Стр.7

Стр.8

УДК 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 (англ.) ISBN 978-5-97060-873-9 (рус.) © Peter Brass, 2008 © Оформление, перевод на русский язык, издание, ДМК Пресс, 2023

Стр.5

Оглавление От авторов перевода .............................................................................................................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

Оглавление  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

Стр.8