Алгоритмы и структуры данных · 4

Деревья, кучи и префиксные деревья

Обходы, деревья поиска и балансировка, B-деревья в базах данных, кучи и очереди с приоритетом, trie. Как они устроены, где живут в ОС, базах и стандартных библиотеках и как узнать их в задаче на собеседовании.

Листайте стрелками ← →, свайпом или кнопками внизу. В схемах нажимайте кнопки и узлы деревьев.

Деревья повсюду

Дерево — иерархия без циклов: один корень, у каждого узла ровно один родитель. DOM, AST, файловая система, JSON, оргструктура, план SQL-запроса — всё деревья.

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

Обходы: в глубину и в ширину

  • Pre-order — узел, потом дети: копирование, сериализация, find.
  • In-order — левое, узел, правое. Только для двоичных; в дереве поиска даёт ключи по возрастанию.
  • Post-order — дети, потом узел: du, rm -r, вычисление выражений, освобождение памяти.
  • BFS — по уровням через очередь: «ближайшие сначала», «все на глубине k».

DFS хранит путь от корня — стек глубиной h. BFS хранит фронт — очередь шириной до n/2 узлов. Выберите порядок и жмите «Шаг».

Рекурсия — это тоже стек

Рекурсивный обход использует системный стек: кадр на уровень. У сбалансированного дерева глубина ~log₂ n, у вырожденного — n, и стек кончается. Явный стек живёт в куче и ограничен только памятью.

# рекурсия: глубина ограничена стеком
def dfs(node):
    if node:
        yield node.val
        yield from dfs(node.left)
        yield from dfs(node.right)

# явный стек: глубина любая
def dfs_iter(root):
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        yield node.val
        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)

Лимиты: CPython — 1000 кадров (sys.getrecursionlimit()), Node.js — ~10 тыс., Java — от тысяч до десятков тысяч при стеке 512 КБ–1 МБ, у горутины Go стек растёт до 1 ГБ. Подробнее — в «Стеке и куче».

В двоичное дерево поиска вставили 5000 ключей по возрастанию (id из базы). Что сделает рекурсивный dfs на CPython?

Ключи по возрастанию превращают дерево в цепочку глубиной 5000, а лимит — 1000 кадров. sys.setrecursionlimit(10**6) спасает не всегда: кончится уже стек потока на C, и тогда действительно будет segfault. Надёжно — явный стек или сбалансированное дерево.

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

Слева от узла — меньшие ключи, справа — большие. Поиск, вставка и удаление идут по одному пути от корня — O(h). В сбалансированном дереве h ≈ log₂ n: 20 шагов на миллион ключей.

  • В отличие от хеш-таблицы, дерево хранит порядок: минимум, «следующий после x», диапазон [a, b] — тоже O(log n).
  • Удаление узла с двумя детьми: его место занимает следующий по порядку ключ — самый левый в правом поддереве.

Повороты

Поворот поднимает узел на место родителя и перевешивает одно поддерево. Порядок ключей не меняется, а высота — меняется. Все самобалансирующиеся деревья держат форму только поворотами — за O(1) каждый.

Нажмите на узел, чтобы поднять его над родителем. Превратите цепочку 1…7 в дерево высоты 3. Подсказка: начните с середины.

Отсортированный вход и балансировка

Ключи по возрастанию — самый частый вход в жизни: автоинкрементные id, время, имена из отсортированного файла. Обычное дерево поиска превращается в список, и все операции — O(n).

  • АВЛ: высоты поддеревьев любого узла отличаются не больше чем на 1, h ≤ 1,44·log₂ n. Строже — быстрее поиск.
  • Красно-чёрное: никакой путь от корня до листа не длиннее другого вдвое, h ≤ 2·log₂ n. Не больше 2 поворотов на вставку и 3 на удаление — поэтому его любят библиотеки и ядро.

Где живут сбалансированные деревья

Java · C++

TreeMap, TreeSet, std::map, std::set — красно-чёрные деревья. floorKey, ceilingKey, subMap, lower_bound — поиск соседей и диапазонов за O(log n).

Java HashMap

Если в одной корзине набралось 8 коллизий (и таблица не меньше 64), цепочка превращается в красно-чёрное дерево — защита от атаки подобранными ключами.

Linux

Планировщик CFS и сменивший его в 6.6 EEVDF держат готовые задачи в КЧ-дереве — следующая берётся с левого края. В КЧ-деревьях лежат дескрипторы epoll и таймеры hrtimer.

Linux 6.1+

Области памяти процесса (VMA) переехали из КЧ-дерева в maple tree — разновидность B-дерева: меньше промахов кэша. Об этих областях — в «Виртуальной памяти».

nginx · сети

Таймеры соединений в nginx — КЧ-дерево: ближайший таймаут — самый левый узел.

Python · Go · JS

Встроенного упорядоченного словаря нет. Python — sortedcontainers (не дерево, а список списков с bisect), Go — google/btree, tidwall/btree. Часто хватает сортировки и bisect.

Проверьте себя

Атакующий отправил в Java-сервис 10 000 строковых ключей с одинаковым hashCode(), и все они легли в HashMap. Сколько стоит поиск одного ключа в Java 8+?

В Java 7 это была бы цепочка на 10 000 элементов — классическая DoS-атака на парсер параметров запроса. С Java 8 корзина длиннее 8 превращается в красно-чёрное дерево, а строки сравнимы — поиск за log₂ 10 000 ≈ 14 шагов. Python и Go защищаются иначе: случайной солью хеша при старте процесса. Подробнее о хеш-таблицах — в «Массивах и хешировании».

B-дерево: узел размером со страницу

Диск читает страницами по 4–16 КБ, и случайное чтение стоит как тысячи сравнений в памяти. Поэтому в узел B-дерева кладут сотни ключей: узел = страница, ветвление — сотни, высота — 3–4 даже для миллиардов строк.

Верхние уровни занимают мегабайты и всегда в кэше. Даже в RAM B-дерево обгоняет двоичное: узел — несколько кэш-линий подряд, а не промах на каждом шаге. Двигайте ползунки. B-дерево в Postgres — подробно в «PostgreSQL изнутри».

B+дерево: вставка и деление узлов

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

LSM-дерево (RocksDB, Cassandra) отвечает на другой вопрос — как быстрее писать: копит записи в памяти и сливает отсортированные файлы. О нём — в «Вероятностных структурах» вместе с фильтрами Блума.

Двоичная куча

Полное двоичное дерево, где родитель не больше детей. Хранится в массиве без указателей: дети i — 2i+1 и 2i+2, родитель — (i−1)//2. Минимум всегда в a[0].

  • push: в конец и просеивание вверх — O(log n).
  • pop: последний на место корня и просеивание вниз — O(log n).
  • heapify: просеять вниз все узлы от середины к началу — O(n), а не O(n log n).

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

Три приёма с кучей

  • Top-K: min-куча размера K. Новый элемент больше корня — заменяет его. O(n log K) времени и O(K) памяти, поток можно читать по одному элементу.
  • Слияние K отсортированных списков: куча из голов списков. Так работают heapq.merge, внешняя сортировка и слияние сегментов в LSM-базах.
  • Медиана потока: max-куча для меньшей половины, min-куча для большей; размеры отличаются не больше чем на 1.

Кучи на практике

  • Таймеры: в Go runtime — 4-арная куча на каждом P (time.Sleep, time.After, контексты с дедлайном). В libuv и Node.js — двоичная куча: цикл событий спит до срока a[0]. В asyncio call_later кладёт таймер в heapq.
  • Очереди с приоритетом и планировщики: PriorityQueue и DelayQueue в Java, отложенные задачи в очередях.
  • Графы: Дейкстра, A*, алгоритм Прима — подробнее в «Графах».

Удалить из кучи произвольный элемент дорого: сначала его нужно найти за O(n). Поэтому отменённые таймеры только помечают и выбрасывают при извлечении — так делают asyncio и Go runtime.

import heapq

tasks = []   # куча — это обычный list
# кортежи сравниваются по первому полю,
# seq разрешает ничьи и сохраняет порядок
heapq.heappush(tasks, (deadline, seq, job))
deadline, _, job = heapq.heappop(tasks)

heapq.heapify(data)          # O(n), на месте
heapq.nlargest(10, rows, key=lambda r: r.ms)
for line in heapq.merge(log1, log2, log3):
    ...                      # слияние за O(n log k)

# max-куча: кладите -x
# (в Python 3.14+ есть heapq.heappush_max)

Проверьте себя

Лог на 10 млрд строк читается потоком. Нужны 100 самых медленных запросов, памяти — несколько мегабайт. Какая структура?

В корне min-кучи — самый быстрый из 100 медленных, то есть первый кандидат на вылет. Новая строка медленнее корня — заменяем его за O(log 100), иначе отбрасываем за O(1). Итого O(n log K) и память на 100 элементов. Max-куча на 100 держала бы в корне не того: выкинуть пришлось бы минимум, а он не в корне. Это ровно heapq.nlargest(100, ...).

Префиксное дерево (trie)

Строки хранятся по символам: путь от корня — префикс, общие префиксы хранятся один раз. Найти слово или все слова с префиксом — O(длины префикса), сколько бы слов ни было в словаре.

  • Автодополнение: в узле можно хранить готовый топ подсказок.
  • HTTP-роутеры (httprouter и Gin, chi, Fastify) и Redis Streams — radix-дерево, сжатый trie: цепочки без ветвлений склеены в одно ребро.
  • Цена — память: узел на каждую букву плюс таблица переходов.

Печатайте в поле — подсказки обновляются на лету. Добавьте своё слово.

Маршрутизация: самый длинный префикс

Маршрутизатор выбирает самый длинный подходящий префикс: 10.1.2.0/24 важнее 10.0.0.0/8, а 0.0.0.0/0 — маршрут по умолчанию. Это trie по битам адреса: идём от старшего бита и запоминаем последний совпавший маршрут.

В Linux маршруты IPv4 лежат в сжатом LC-trie (/proc/net/fib_trie), в аппаратных маршрутизаторах — в TCAM-памяти. Тот же поиск делают файрволы и GeoIP. Выберите адрес и жмите «Шаг».

Деревья отрезков и Фенвика

Нужна сумма или минимум на отрезке массива, который меняется. Префиксные суммы отвечают за O(1), но обновление стоит O(n). Дерево Фенвика и дерево отрезков делают и то и другое за O(log n).

  • Фенвик: 10 строк, ячейка i хранит сумму блока длиной в младший бит i. Для сумм и любых обратимых операций.
  • Дерево отрезков: min, max, НОД, «присвоить на отрезке» с ленивыми обновлениями.
  • В продакшене редки — рейтинг в Redis (ZRANK) держится на skip list. На собеседованиях — в задачах hard.
class Fenwick:                 # индексы с 1
    def __init__(self, n):
        self.t = [0] * (n + 1)

    def add(self, i, delta):   # a[i] += delta
        while i < len(self.t):
            self.t[i] += delta
            i += i & -i        # следующий блок с i

    def prefix(self, i):       # a[1] + … + a[i]
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i        # снять младший бит
        return s

# сумма на [l, r]: prefix(r) - prefix(l - 1)

На собеседовании: как узнать задачу

«по уровням», «правый вид», «минимальная глубина»BFS с очередью; размер уровня = len(q) в начале итерации
«проверить BST», «k-й наименьший», «отсортированный вывод»in-order; для проверки — границы (lo, hi)
«LCA», «диаметр», «путь с макс. суммой», «сбалансировано ли»post-order: функция возвращает из поддерева 1–2 значения
«сериализовать и восстановить дерево»pre-order с маркером пустого узла (#) или BFS
«k наибольших / ближайших», «слить k списков», «медиана потока»куча размера k или две кучи
«префикс», «словарь», «найти слова в сетке букв»trie (+ DFS по сетке)
«сумма на отрезке» с изменениямиФенвик или дерево отрезков

Сначала уточните: двоичное ли дерево, дерево ли поиска, бывают ли дубликаты, может ли оно быть пустым и насколько глубоким (рекурсия или стек). Сложность почти всегда O(n) по времени и O(h) по памяти — проговорите это.

Разбор: проверка BST, k-й, LCA

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

inf = float('inf')

def valid(node, lo=-inf, hi=inf):
    if not node:
        return True
    if not lo < node.val < hi:
        return False
    return (valid(node.left, lo, node.val) and
            valid(node.right, node.val, hi))

Переключайте задачи и жмите «Шаг»: первые две идут на дереве с ловушкой, две другие — на правильном BST.

Как увидеть у себя

  • Не пишите свою кучу и дерево — берите heapq, bisect, sortedcontainers, TreeMap, container/heap.
  • Обход чужих деревьев (JSON, AST, каталоги) — итеративно, если глубину задаёт пользователь.
  • Индекс по случайному UUID пишет в случайные листья B-дерева и делит страницы по всему индексу. UUIDv7 (по времени) вставляется в правый край.
# AST и байткод Python
echo 'x = a + b * 2' | python3 -m ast
echo 'x = a + b * 2' | python3 -m dis

# Linux: trie маршрутов и longest prefix match
head -30 /proc/net/fib_trie
ip route get 10.1.2.7

# очереди планировщика (КЧ-деревья задач)
sudo cat /sys/kernel/debug/sched/debug | less

# Postgres: высота B-дерева индекса
CREATE EXTENSION pageinspect;
SELECT level, fastroot FROM bt_metap('orders_pkey');

# DOM в консоли браузера: обход в глубину
document.querySelectorAll('*').length

Главное

  • Иерархия — это дерево, а работа с деревом — обход. Pre-order — родитель первым, post-order — ответ из детей, BFS — по уровням.
  • Рекурсия ограничена стеком: на вырожденных и чужих деревьях нужен явный стек.
  • Дерево поиска хранит порядок, но без балансировки вырождается на отсортированном входе. Балансируют поворотами: АВЛ, красно-чёрное.
  • На диске — B+деревья: узел = страница, ветвление в сотни, 3–4 уровня на миллиарды строк.
  • Куча — массив без указателей: минимум за O(1), вставка за O(log n). Таймеры, планировщики, top-K, слияние, Дейкстра.
  • Trie — для префиксов: автодополнение, роутеры, маршрутизация IP.

Видите иерархию — ищите обход. Видите «k лучших» — берите кучу. Видите префиксы — стройте trie.