Структуры данных простыми словами

Любая программа где-то хранит данные, и от того, как она это делает, зависит, что будет быстрым, а что медленным. Список из миллиона имён можно просматривать имя за именем, а можно упорядочить так, что любое имя найдётся за двадцать сравнений. Структуры данных — это такие способы упорядочивания: горстка идей, большинство из которых старше персонального компьютера, и они есть в каждой базе данных, операционной системе, браузере и игре.

Двоичное дерево поиска в красно-чёрной раскраске, стопка коробок, ряд хеш-корзин с цепочкой сталкивающихся ключей и стрелки, соединяющие узлы списка
Двоичное дерево поиска в красно-чёрной раскраске, стопка коробок, ряд хеш-корзин с цепочкой сталкивающихся ключей и стрелки, соединяющие узлы списка

Зачем нужна структура данных

Структуру данных выбирают по вопросам, на которые она должна отвечать. Журналу звонков в телефоне нужен сначала последний звонок, принтеру — сначала самое старое задание, словарю — значение одного слова из ста тысяч, навигатору — ближайший непосещённый перекрёсток. Каждая структура ускоряет одни операции ценой других, а О-большое описывает этот обмен: O(1) значит, что время не растёт с числом элементов n, O(log n) — что удвоение n добавляет один шаг, а O(n) — что время растёт пропорционально n.

Стеки, очереди и деки

Стек добавляет и удаляет с одного конца: последним пришёл — первым ушёл. История отмен, кнопка «Назад» и вызовы работающей программы — это стеки. Очередь добавляет в конец и удаляет из начала: первым пришёл — первым ушёл, как нажатия клавиш или очередь печати. Дек позволяет и то и другое с обоих концов. Все три выполняют операцию за постоянное время. Очередь часто хранят в кольцевом буфере — фиксированном массиве, в котором начало и конец после последней ячейки переходят к первой; когда он заполняется, элементы копируются в массив вдвое больше. Копирование стоит O(n), но случается так редко, что каждая операция всё равно стоит в среднем O(1) — это называют амортизированной оценкой.

Связные списки

Связный список хранит каждое значение в узле с указателем на следующий узел. Вставка или удаление меняет лишь один-два указателя, ничего не нужно сдвигать, но перепрыгнуть к десятому узлу нельзя: приходится идти по ссылкам от головы. Список, знающий только свою голову, доходит до хвоста за O(n) шагов; настоящие списки обычно хранят ещё и указатель на хвост, а двусвязные — указатель назад, и так устроены история браузера или LRU-кеш.

Двоичные деревья поиска

Двоичное дерево поиска в каждом узле держит меньшие значения в левом поддереве, а большие — в правом. Поиск сравнивает и идёт влево или вправо, а симметричный обход читает значения по порядку. Удалить лист — значит просто убрать его; узел с одним ребёнком заменяется этим ребёнком, а узел с двумя детьми — своим симметричным преемником, наименьшим значением в правом поддереве. Всё это занимает время, пропорциональное высоте дерева: около log n, когда дерево ветвистое, но n, когда значения приходят по порядку и дерево вырождается в список.

АВЛ- и красно-чёрные деревья

Самобалансирующиеся деревья чинят свою форму после каждого изменения. АВЛ-дерево, придуманное Адельсон-Вельским и Ландисом в 1962 году, держит высоты двух поддеревьев каждого узла в пределах единицы; когда показатель баланса узла достигает ±2, один поворот (случаи LL и RR) или два (LR и RL) восстанавливают равновесие. Красно-чёрное дерево раскрашивает узлы так, что корень чёрный, у красного узла нет красных детей и каждый путь вниз проходит через одинаковое число чёрных узлов; поэтому самый длинный путь не более чем вдвое длиннее самого короткого. Оно чинит себя перекраской и не более чем несколькими поворотами, и именно оно лежит внутри TreeMap в Java, std::map в C++ и планировщика Linux.

Кучи и очереди с приоритетом

Двоичная куча — это полное двоичное дерево, хранящееся в массиве без всяких указателей: дети позиции i находятся в 2i + 1 и 2i + 2. В min-куче каждый родитель не больше своих детей, поэтому наименьшее значение всегда в корне. Новое значение ставится в конец и всплывает мимо больших родителей; при извлечении корня последнее значение переносится наверх и тонет. Обе операции стоят O(log n), а целый массив превращается в кучу за O(n). Кучи приводят в движение очереди с приоритетом в алгоритме кратчайших путей Дейкстры, в моделировании событий и в планировщиках операционных систем, а ещё дают пирамидальную сортировку.

Хеш-таблицы

Хеш-таблица превращает ключ в индекс массива с помощью хеш-функции и идёт прямо туда. Разные ключи могут попасть на один индекс — это коллизия. Метод цепочек держит в каждой корзине маленький список; открытая адресация, например линейное пробирование, пробует следующие ячейки, пока не найдёт свободную, и при удалении ключа должна оставить надгробие, чтобы последующие поиски продолжали пробировать. С хорошей хеш-функцией и низким коэффициентом заполнения (ключей на корзину), который поддерживают ростом таблицы, вставка, поиск и удаление стоят в среднем O(1). Плохая функция, например сумма кодов символов слова, отправляет анаграммы в одну корзину. Хеш-таблицы стоят за dict в Python, объектами JavaScript и индексами баз данных.

Префиксные деревья и union-find

Префиксное дерево, или trie, хранит строки по одному символу на уровень, так что слова с одинаковым началом делят путь, а узел отмечает, где слово заканчивается. Найти слово длины L стоит L шагов, сколько бы слов ни хранилось, а все слова с данным префиксом лежат в одном поддереве — так работают автодополнение и проверка орфографии. Union-find держит элементы в непересекающихся множествах, каждое из которых — дерево, чей корень даёт имя множеству. Find идёт по ссылкам на родителя до корня; union подвешивает один корень под другой. С объединением по рангу и сжатием путей длинная серия операций стоит почти постоянное время на операцию — обратную функцию Аккермана α(n), которая для любого реального n не больше 4. На этом держится алгоритм Краскала для минимального остовного дерева.

Часто задаваемые вопросы

Чем массив отличается от связного списка?

Массив хранит элементы рядом в памяти, поэтому до любой позиции можно дойти сразу, но вставка в середину означает сдвиг всего, что идёт после. Связный список может вставлять куда угодно, меняя указатели, но чтобы дойти до позиции, нужно идти от головы. Кроме того, массивы гораздо лучше используют кеш процессора, поэтому на практике обычно быстрее.

Что значит амортизированное время?

Средняя стоимость одной операции в длинной серии, даже если отдельная операция иногда дорогая. Кольцевой буфер, который удваивается при заполнении, время от времени копирует все n элементов, но копии становятся всё реже по мере роста буфера, поэтому n добавлений стоят в сумме O(n), то есть в среднем O(1) за каждое.

Куча — это то же самое, что двоичное дерево поиска?

Нет. Двоичное дерево поиска ставит каждое левое поддерево перед своим узлом, а каждое правое — после, поэтому может перечислить все значения по порядку и быстро найти любое. Куча обещает лишь, что каждый родитель идёт раньше своих детей; этого хватает, чтобы сразу найти минимум или максимум, но не чтобы искать произвольное значение.

Как union-find узнаёт, связаны ли два элемента?

Он идёт от каждого элемента по ссылкам на родителя до корня его дерева. Если оба приходят к одному корню, они в одном множестве. Затем сжатие путей заставляет каждый узел на пути указывать прямо на корень, так что следующий вопрос о них занимает один шаг.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть визуализатор структур данных