Разреженное дерево в массиве: как хранить неполные и динамические структуры

Полное двоичное дерево укладывается в массив без единого пропуска: потомки узла с индексом i лежат в 2i+1 и 2i+2, родитель в (i-1)/2. Пока уровни заполнены целиком, это самый экономный вариант по памяти и самый быстрый по доступу: ни указателей, ни хеширования, один сплошной блок данных.

Разреженное дерево ломает эту схему. Если занято 30% узлов при глубине 15, массиву нужно 32 768 ячеек под 10 000 реальных элементов. Если дерево выродилось в левую цепочку глубины 20, под 20 узлов резервируется 1 048 576 ячеек.

Ниже разбираем три способа хранить неполное и растущее дерево: индексы-заполнители (sentinel), словарь по индексам или путям, динамический массив с явными ссылками на потомков. Для каждого даём оценки памяти и момент, когда подход пора менять.

Почему обычное массивное хранение дерева ломается на неполных данных

Классическая схема: корень в индексе 0, потомки узла i в 2i+1 и 2i+2. Дерево из 7 узлов занимает ровно ячейки 0...6, ни одной лишней.

Дерево из 5 узлов, вытянутое в левую цепочку, занимает индексы 0, 1, 3, 7 и 15. Под пять значений нужен массив на 16 ячеек, заполнение 31%. Формула не меняется, плотность хранения падает втрое.

Как выглядит полное дерево в массиве и где появляются дыры

Пропуск в массиве это не только null. Это любое значение-заполнитель, которое приходится проверять при каждом обходе: -1, None, null, объект-маркер или запись в битовой карте занятости. Обход получает лишнюю проверку на каждом узле и на каждом шаге спуска.

Потери считаются просто. Число ячеек равно 2^(h+1) - 1, где h это максимальная глубина. Для сбалансированного дерева из 1000 узлов глубина около 10, массив на 2047 ячеек заполнен наполовину. Для вырожденной цепочки из тех же 1000 узлов глубина 1000, и массив такого размера не построить ни в какой разумной памяти.

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

Три сценария, где массивное представление перестаёт работать

1. Дерево решений с редкими ветками. Конфигурация Nginx, разобранная в дерево: http, вложенные server, необязательные location, if, upstream. Ветки заполнены неравномерно: у одного виртуального хоста 12 локаций, у другого одна. При глубине 10 массив по 2i+1 занимает 1023 ячейки, а реальных директив около 150, заполнение 15%.
2. Динамическое дерево задач в планировщике. Узлы добавляются и удаляются в рантайме. Удаление произвольного узла рвёт свойство полноты: чтобы вернуть плотность, приходится переносить последний элемент на место удалённого и заново связывать потомков. Индексация 2i+1 такую операцию не поддерживает без ручной перекладки.
3. Дерево зависимостей пакетов. Большая часть узлов имеет одного потомка, ветвление редкое. Доля пустых ячеек стабильно выше 80%, массив тратит память на уровни, которых в графе зависимостей нет.

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

Индексы-заполнители: просто, но не всегда экономно

Подход: массив фиксированного размера на всю возможную глубину, пустые узлы помечены sentinel-значением. Индексация остаётся арифметической, переход к потомку стоит одну операцию 2i+1.

Что получаете: O(1) на переход к потомку и родителю, сплошной блок памяти, отсутствие указателей, предсказуемый обход без разыменований. Что платите: память выделена под все ячейки, включая пустые. Дерево с 10 000 узлов и глубиной 15 требует массива на 32 768 ячеек при заполнении 30%. Это 22 768 пустых слотов.

Как выбрать sentinel-значение и не сломать логику

Вариантов три, и выбор зависит от типа данных.

• -1 подходит только для неотрицательных чисел. Если в узлах бывают отрицательные значения (веса, температуры, дельты), минус единица столкнётся с реальными данными и обход начнёт считать занятые узлы пустыми.
• None или null удобно для объектов, но только когда сама полезная нагрузка не может быть пустой. Если узел законно хранит null, различить пустой слот и валидный узел не получится.
• Отдельная битовая карта занятости снимает проблему коллизий полностью. Один бит на ячейку: 32 768 ячеек это 4 КБ. Карта проверяется быстрее сравнения объектов и позволяет хранить в массиве любые значения.

Проверяйте два места: корень (индекс 0 всегда занят, иначе дерево пустое) и границы массива. Индекс 2i+2 может выйти за пределы выделенной ёмкости даже у неглубокого на вид дерева.

Пример: дерево конфигурации Nginx с необязательными блоками

Разберём директивы как узлы: корень это http, потомки это server, ниже location и вложенные блоки. Часть блоков отсутствует: у одного сервера только статика, у другого проксирование, TLS и ограничения по IP.

При глубине 7 массив занимает 127 ячеек, реальных директив около 80, заполнение 63%. Массив с sentinel выигрывает у словаря на 80 записей: обход идёт по сплошному блоку, процессор не ждёт промахов кэша при каждом поиске в хеш-таблице, кода меньше. Как только появляются хосты с 3-4 уровнями вложенности и редкими ветками, заполнение падает и выгода исчезает.

Рекомендация: массив с заполнителями держите при высокой плотности заполнения и глубине до 10-12 уровней. Для более глубоких или более разреженных деревьев считайте память до написания кода.

Словарь для хранения дерева: гибко, но дороже по памяти

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

Дерево на 1000 узлов и глубиной 20 в словаре занимает около 1000 записей. Тот же набор в массиве по формуле 2i+1 потребовал бы 1 048 576 ячеек. Разница почти в тысячу раз по числу слотов.

Накладные расходы хеш-таблицы по памяти значительны. При стандартном коэффициенте заполнения 0.75 для 1000 элементов следует ожидать примерно 1300-2700 бакетов, и каждый бакет существенно больше одной ячейки. По одной из оценок хеш-таблица может занимать примерно в 14 раз больше памяти, чем число реально используемых элементов в альтернативном массиве. Хеш-таблица теоретически может оказаться меньше массива только при очень низком коэффициенте заполнения массива: при доле занятых ячеек выше 0.1 она займёт больше памяти, при 0.03-0.10 обе структуры потребляют значительный объём, и лишь ниже 0.03 словарь выигрывает.

Как организовать ключи и связи между узлами в словаре

Два рабочих варианта.

• Ключ это целочисленный индекс. Логика совпадает с массивом: потомки вычисляются как 2i+1 и 2i+2, только в словаре лежат лишь занятые позиции. Проверка существования узла это поиск ключа. Так удобно переносить уже написанный алгоритм с массива.
• Ключ это путь: "root", "root.left", "root.left.right". Обход становится итеративным по префиксам, отладка проще: видно положение узла в дереве. Платите длиной строк и стоимостью хеширования от строк вместо чисел.

В обоих случаях храните явные ссылки на потомков или отдельные поля left и right. Если считать потомков арифметически, вы получите все минусы массива (раздутые индексы) плюс накладные расходы хеш-таблицы.

Когда словарь проигрывает массиву с заполнителями

Контрпример: дерево с заполнением 80% и глубиной 10. Массив занимает 1023 ячейки, из них 800 заняты. Словарь на 800 записей делает то же самое, но каждое обращение к узлу это вычисление хеша, поиск в бакете и разрешение коллизий. При обходе в глубину вы теряете кэш-локальность: словарь разбрасывает записи по памяти, процессор простаивает на промахах.

Порог: если заполнение высокое и дерево неглубокое, массив с sentinel-значениями быстрее и проще в коде. Словарь берите при низком заполнении или при частых вставках и удалениях, где перестройка массива дороже хеширования. Типичные готовые структуры: dict в Python, map в Go, HashMap в Java. В CPython словарь построен на открытой адресации, тогда как Java HashMap использует связные списки в бакетах; при невысоком коэффициенте заполнения открытая адресация обычно быстрее и итерирование по ней дешевле.

Динамическое расширение массива: как растить дерево без перевыделения

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

Важное отличие от схемы 2i+1: узлы лежат подряд, в порядке добавления, а связи хранятся явно (индексы потомков в полях узла или отдельный массив). Память тогда растёт как O(n), а не как O(2^h). При удвоении ёмкости суммарное число копирований при добавлении n элементов ограничено суммой геометрической прогрессии 1 + 2 + 4 + 8 + ... + n < 2n, то есть меньше двух копирований на элемент в среднем. С учётом самих вставок суммарная оценка T(n) ≤ 3n.

Цена: на каждом перевыделении копируются все элементы, и в момент копирования память занята и старым, и новым блоком. Разбор реаллокации и цены копирования с примерами на C++, Java и Go поможет оценить расходы под вашу нагрузку.

Выбор коэффициента роста: 1.5x или 2x?

Обе схемы дают амортизированную O(1), разница в пиковой памяти и числе копирований.

• 2x. Меньше перевыделений, но больше памяти в пике. Для 10 000 узлов ёмкость доходит до 20 000 ячеек. Часть этой памяти останется занятой впустую после серии удалений.
• 1.5x. Пиковая ёмкость около 15 000 ячеек, рост плавнее, копирований больше. Практическое преимущество: при коэффициенте 1.5 освобождённую при предыдущем перевыделении память можно переиспользовать уже при втором перераспределении, тогда как при 2x такого момента не наступает — образующаяся дыра никогда не окажется достаточно большой для следующей аллокации.

Выбор: 1.5x для памяти-критичных сервисов и длительно живущих структур, 2x когда важнее скорость и число аллокаций, а память дешёвая. Оба варианта лучше роста по +1 элементу, который даёт O(n) на вставку и O(n^2) на построение дерева из n узлов.

Как избежать ошибок при перевыделении

Типичные ошибки при росте массива.

• Ссылки на старый блок. После перевыделения указатели и итераторы на прежний массив недействительны. В C++ это обращение к освобождённой памяти, в Go незаметная работа с устаревшим срезом.
• Индексы, которые изменились. Если после удаления узлов вы сжимаете массив, сохранённые числовые индексы потомков указывают уже не туда. Держите стабильные идентификаторы и отдельную таблицу перевода.
• Потеря данных при копировании. Копирование только занятой части или неверный размер нового блока тихо обрезает дерево.
• Переполнение индекса. Даже при плотном хранении проверяйте, что индекс потомка меньше текущей ёмкости, а не только меньше логического размера дерева.

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

Сравнение подходов: память, скорость и сложность кода

Оценки даны для 1000 узлов и глубины 20, если не указано иное.

Таблица сравнения: память и скорость для 1000 узлов

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

Если данные не дерево, а разреженная матрица или граф, логика выбора похожа: критерии выбора между плотным и разреженным форматом дают формулы оценки памяти и порог доли ненулевых элементов.

Как выбрать подход за 2 минуты: чек-лист

1. Дерево статично или меняется в рантайме? Статичное: массив с sentinel при высокой плотности заполнения. Меняется: словарь или динамический массив.
2. Какая доля заполненных ячеек? Высокая: массив по 2i+1. Средняя: считайте память по обеим моделям. Низкая: словарь.
3. Какая максимальная глубина? До 10-12 уровней массив остаётся компактным. Глубже 15 при редком заполнении массив теряет смысл.
4. Как часто нужен доступ к родителю и потомкам? Часто и в горячем цикле: массив с арифметикой индексов. Редко: словарь.
5. Есть ли жёсткое ограничение по памяти? Если да, посчитайте 2^(h+1) - 1 ячеек для массива до написания кода и сравните с n записями словаря.

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

Когда разреженное дерево в массиве - не лучший выбор

Массив с индексами-заполнителями стоит отбросить в четырёх случаях: низкое заполнение при большой глубине, частые вставки и удаления в середине дерева, отсутствие иерархии в данных и потребность в приоритетном доступе.

Альтернативы: сбалансированные деревья, кучи, хэш-таблицы

• Сбалансированные деревья (AVL, красно-чёрное, B-дерево). Память O(n), доступ и изменение за логарифмическое время без перестроек массива. Подходят, когда структура меняется постоянно, а обход нужен в отсортированном порядке.
• Куча. Двоичная куча хранится в одномерном массиве, где левый потомок вершины с индексом i находится по формуле 2i+1, а корень это элемент с индексом 0; высота кучи равна log₂ от количества элементов. Она позволяет за логарифмическое время добавлять элементы и извлекать элемент с максимальным приоритетом, проста в реализации и не требует дополнительной памяти. При извлечении максимального элемента на его место в корень ставится последний элемент массива, после чего выполняется просеивание вниз для восстановления свойства кучи.
• Хэш-таблица. Доступ O(1), порядок между элементами не поддерживается. Берите, если нужен только поиск узла по идентификатору.
• Графовые структуры и списки смежности. Уместны, когда у узла больше двух потомков или рёбра имеют веса и данные не сводятся к двоичному дереву. Сравнение массивов и связных списков по памяти и кэш-локальности собрано в отдельном разборе.

Пример: дерево зависимостей пакетов на 10 000 узлов с 90% пропусков. Массив по формуле 2i+1 тут не построить, словарь даёт доступ к узлу за одну операцию хеширования, а для топологической сортировки рядом хранится список смежности.

Практические примеры и типичные ошибки

Пример: дерево задач в планировщике с динамическим расширением. Задачи добавляются в очередь и удаляются после выполнения. Узлы лежат в динамическом массиве в порядке добавления, потомки связаны явными индексами, ёмкость растёт с коэффициентом 1.5x. При 10 000 задач и 1000 удалениях массив остаётся эффективным, если не сжимать его после каждого удаления: освободившиеся слоты помечаются и переиспользуются при следующей вставке. Сжатие запускайте по порогу, например когда занято меньше 40% ёмкости, иначе получите копирование на каждой второй операции.

Пример: дерево решений с sentinel-значениями. Глубина фиксирована, 6 уровней, максимум 63 узла, часть веток отсутствует. Массив на 64 ячейки, пустые позиции помечены -1, отдельная битовая карта на 64 бита отмечает занятость. Обход идёт по индексам, проверка занятости стоит одну битовую операцию.

Пример: словарь для сильно разреженного дерева. Узлы хранятся по строковым путям, потомки ссылаются на пути. Вставка и удаление не трогают остальные узлы, память пропорциональна числу реальных элементов. Плата: длинные ключи и потеря локальности при обходе.

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

• Неверный sentinel: -1 в дереве с отрицательными весами или null там, где null это валидное значение.
• Переполнение индекса: расчёт 2i+2 без проверки ёмкости массива.
• Утечки при перевыделении: старый блок не освобождён, временно заняты обе копии.
• Потеря ссылок: указатели на прежний массив после роста, устаревшие индексы после сжатия.
• Фрагментация: рост по +1 элементу раздувает число аллокаций и режет память на мелкие блоки.

Чек-лист перед выбором структуры.

1. Оцените долю заполненных узлов и максимальную глубину на реальных данных, а не на тестовом дереве из десяти элементов.
2. Посчитайте память для массива по формуле 2^(h+1) - 1 и для словаря как n записей плюс накладные расходы.
3. Определите профиль операций: чтение, вставка, удаление, обход. Что встречается чаще, то и определяет выбор.
4. Проверьте, нужен ли доступ по индексу в горячем цикле: кэш-локальность массива даёт выигрыш на обходах.
5. Зафиксируйте тип sentinel и закройте граничные тесты: пустое дерево, один узел, полная ёмкость, единственный элемент после удаления.
6. Прогоните нагрузочный тест на объёме, близком к продакшену: оценки из таблицы это ориентир, а не гарантия.

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