Деревья, кучи и графы

Что это такое

На вопрос «что лежит под этим ключом» отвечают плоские коллекции, а деревья, кучи и графы — на два других: что упорядочено и что с чем связано. Дерево связывает каждое значение с родителем и потомками, куча держит сверху самое важное значение, а граф позволяет любому узлу указывать на любой другой — из этих структур и состоят отсортированные индексы, очереди задач и поиск маршрутов.

Почему это важно

Именно на упорядоченных и связанных данных наивный код спотыкается первым: вставка в отсортированный массив порядок сохраняет, зато копирует хвост, а просьба к связному списку «дай наименьшее» оборачивается обходом всего списка. Сбалансированное дерево даёт вставку и поиск с одинаковой растущей стоимостью, поэтому индексы баз данных и упорядоченные отображения устроены как деревья, а куча выдаёт «следующую самую срочную задачу» за фиксированную стоимость, поэтому её берут планировщики и ограничители скорости. Графы описывают всё, у чего есть маршруты, зависимости или отношения, и неверный обход как раз и заставляет краулер зациклиться навсегда.

Ключевые идеи

Дерево упорядочивает структурой, а не позицией

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

        50
      /    \
    30      70
   /  \    /  \
  20   40 60   80

поиск 40: 40 < 50 -> влево; 40 > 30 -> вправо; найдено

Куча держит одно значение дешёвым

Куча — это дерево, хранимое в массиве, с одним правилом: каждый родитель главнее своих потомков. Это правило ставит минимум или максимум на нулевой индекс, а перестроение после добавления или извлечения стоит глубины дерева; остальное куча не сортирует — осмыслен только верх, — и как раз этого и требует очередь с приоритетом.

добавить 7 в [3, 5, 9, 8]: поставить в конец, затем менять
с родителем, пока меньше его.  извлечение: перенести последний
элемент в корень, затем менять вниз.  Оба стоят O(log n).

Графы — общий случай

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

visited = set()
queue = [start]
while queue not empty:
  node = queue.pop front
  if node in visited: continue
  visited.add(node)
  queue.extend(node.neighbours)

Форма данных решает обход

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

Практика

Постройте индекс вручную

Возьмите список из пятидесяти записей с числовым ключом. Храните их в сбалансированном двоичном дереве поиска, которое реализуете сами, и обеспечьте поиск и упорядоченный вывод.

Готово, когда: поиск задевает не больше нескольких узлов на запрос, а вывод обходит дерево по порядку.

Найдите кратчайший маршрут в небольшом графе

Смоделируйте пять остановок и связи между ними. Запустите поиск в ширину из одной остановки и напечатайте расстояние до каждой из остальных.

Готово, когда: расстояния верны, и вы можете объяснить, почему первый визит в узел — кратчайший.

Частые ошибки

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

Что читать дальше

Массивы, списки и хеш-таблицы (01-cs-fundamentals/02-data-structures/01-arrays-lists-and-hash-maps) — плоские структуры, из которых эти построены, и компромиссы, которые они тянут наверх.
Алгоритмы и Big-O (01-cs-fundamentals/14-algorithms-big-o) — почему здесь важно число высоты дерева, а не число элементов.
Внутреннее устройство баз данных (01-cs-fundamentals/04-database-internals) — то же дерево, на диске, за каждым индексом, который вы создаёте.