Что такое хранение дерева в массиве и зачем оно нужно
Дерево можно хранить в обычном массиве, если оно полное бинарное. Корень занимает ячейку с индексом 0, его потомки - ячейки 1 и 2, их потомки - 3, 4, 5, 6, и дальше по уровням слева направо. Указатели в такой структуре не нужны: связи вычисляются арифметикой по индексам, а формулы 2i+1 и 2i+2 дают левого и правого потомка при нумерации с нуля.
Выгода в двух вещах. Память: узел хранит только значение, а не два указателя на потомков. Скорость: все элементы лежат одним непрерывным блоком, и обход дерева превращается в предсказуемый проход по памяти. В связном представлении каждое обращение к потомку - прыжок в случайное место кучи.
Приём стал стандартом там, где форма дерева известна заранее: бинарная куча, приоритетная очередь, сегментное дерево, дерево Фенвика. Им нужен доступ к узлу по индексу за O(1), а не гибкая перестройка структуры. Если дерево меняется произвольно или содержит пропуски, массив проигрывает связному представлению.
Ключевая идея: уровни и индексы
Идея - уровневое представление: сначала корень (уровень 0), затем все узлы уровня 1, затем уровня 2 и так далее. На уровне k помещается 2^k узлов, поэтому длина массива для полного дерева высоты h равна 2^(h+1) - 1.
Дерево высоты 2 с семью узлами укладывается в массив из семи ячеек:
индекс: 0 1 2 3 4 5 6 значение: A B C D E F G уровень: 0 1 1 2 2 2 2
Переходы внутри такой раскладки считаются на месте. Из узла B (индекс 1) в левого потомка D: 2*1+1 = 3. В правого потомка E: 2*1+2 = 4. Из узла E обратно к родителю: (4-1)//2 = 1. Ни одного поля со ссылкой, только арифметика над индексом.
Как устроен непрерывный блок памяти и адресная арифметика внутри него, разбираем в статье как массивы хранятся в памяти.
Почему это экономит память и ускоряет доступ
Посчитаем на конфигурации, которая встречается чаще всего: значение int (4 байта) и два указателя по 8 байт на 64-битной платформе. Узел связного дерева занимает 20 байт, а с выравниванием по границе 8 байт - 24 байта. Узел в массиве int - 4 байта. На миллионе узлов это около 24 МБ против 4 МБ, то есть шестикратная разница только на служебных полях.
Кэш-локальность добавляет второй эффект. Процессор читает память не по одному байту, а кэш-линиями (обычно 64 байта), и последовательный доступ попадает в уже загруженную линию. Обход массива идёт по возрастающим индексам, поэтому промахов кэша заметно меньше, чем при переходах по указателям в разные концы кучи.
Третий фактор - аллокации. Массив выделяется одной операцией, а связное дерево требует отдельного выделения под каждый узел. Отсюда накладные расходы аллокатора, фрагментация кучи и дополнительная работа сборщика мусора в языках с GC. Точную разницу в скорости обхода измеряйте на своём профиле нагрузки: она зависит от размера узла, высоты дерева и порядка обхода.
Формулы индексов: как найти родителя и потомков
Обе системы нумерации дают одни и те же связи, отличаются только записью. Выберите одну и придерживайтесь её во всём коде.
Нумерация с 0: формулы и примеры
Родитель: (i - 1) // 2. Левый потомок: 2*i + 1. Правый потомок: 2*i + 2. Деление целочисленное.
| Узел i | Левый (2i+1) | Правый (2i+2) | Родитель ((i-1)//2) |
|---|---|---|---|
| 0 | 1 | 2 | нет |
| 1 | 3 | 4 | 0 |
| 2 | 5 | 6 | 0 |
| 3 | 7 | 8 | 1 |
| 4 | 9 | 10 | 2 |
Проверка на конкретном узле: для i = 3 левый потомок равен 7, правый 8, родитель 1. Для корня i = 0 родителя нет, поэтому любой подъём вверх начинается с проверки i > 0, иначе (0-1)//2 в Python даст -1 и чтение уйдёт за границу массива.
Такая нумерация удобна в C, C++, Python, Go и Java: массивы там индексируются с нуля, и не нужно тратить ячейку 0.
Нумерация с 1: формулы и примеры
Родитель: i // 2. Левый потомок: 2*i. Правый потомок: 2*i + 1.
| Узел i | Левый (2i) | Правый (2i+1) | Родитель (i//2) |
|---|---|---|---|
| 1 | 2 | 3 | нет |
| 2 | 4 | 5 | 1 |
| 3 | 6 | 7 | 1 |
| 4 | 8 | 9 | 2 |
| 5 | 10 | 11 | 2 |
Пример: для i = 4 левый потомок 8, правый 9, родитель 2. Формулы короче, нет вычитания единицы, корень стоит в ячейке 1, а нулевая ячейка остаётся пустой. Так удобно записывать алгоритмы в текстах про кучи. В языках с нулевой индексацией придётся либо держать массив на n+1 ячеек, либо сдвигать индексы вручную при каждом обращении.
Ключевое различие, на котором чаще всего ошибаются: при нумерации с нуля левый потомок - это 2i+1, при нумерации с единицы - 2i. Смешение двух систем даёт дерево, которое выглядит правдоподобно, но связи в нём перепутаны.
Почему формулы вообще работают. Уровень k начинается с индекса 2^k - 1 при нумерации с нуля и содержит ровно 2^k узлов, идущих подряд. Потомки узла с индексом i занимают позиции 2i+1 и 2i+2, то есть две первые позиции следующего уровня. Арифметика номеров уровней совпадает, поэтому связи не нужно хранить.
Условия корректности: когда массивное представление работает
Три условия выполняются одновременно: дерево полное бинарное, в раскладке нет пропусков, размер массива известен до начала работы. Нарушение любого из них либо ломает связи, либо приводит к перерасходу памяти.
Полное бинарное дерево: определение и проверка
Полное бинарное дерево: все уровни, кроме последнего, заполнены целиком, а последний уровень заполняется слева направо без пропусков. Именно такая форма даёт непрерывную нумерацию, в которой индексы потомков идут подряд.
Проверка по количеству узлов. Дерево высоты h (корень на уровне 0) содержит от 2^h до 2^(h+1) - 1 узлов. Если n не попадает в этот диапазон, дерево точно не полное и в массив без потерь не уложится.
Обратное неверно: попадание в диапазон не гарантирует полноту. Для h = 2 допустимы от 4 до 7 узлов, и n = 6 в диапазон входит. Но если у узла последнего уровня отсутствует левый потомок и присутствует правый, полнота нарушена, и позиции в массиве перестанут соответствовать уровням. Проверяйте не только число узлов, но и порядок заполнения последнего уровня.
В бинарной куче условие полноты выполняется по построению: и вставка, и извлечение поддерживают дерево полным. Это одна из причин, по которой куча живёт в массиве без оговорок.
Что делать с неполными деревьями
Вариант первый: хранить заполнители. На месте отсутствующего узла остаётся пустое значение (None, -1 или отдельный флаг), и массив растёт до 2^(h+1) - 1 ячеек при высоте h. Для редкого дерева большая часть памяти уходит на пустые слоты.
Пример: если у узла с индексом 1 есть только правый потомок, а левого нет, дерево уже не полное. Ему потребуется ячейка под пустышку на позиции 3, чтобы правый потомок остался на позиции 4. Убрать пустышку нельзя - связи вычисляются из индексов, а не хранятся.
Вариант второй: связное представление с указателями или ссылками. Вариант третий: список смежности, где для каждого узла хранится список его потомков; он удобен для деревьев произвольной арности. Вариант четвёртый: словарь, где ключ - индекс узла, а значение - его потомки; так работают с разреженными деревьями, когда важна структура, а не плотная упаковка.
Для деревьев, где пропуски составляют заметную долю, массив с заполнителями проигрывает и по памяти, и по времени: обход начинает разбирать пустые слоты. Оценки плотного и разреженного форматов разобраны ниже.
Сравнение с указателями: память, скорость, сложность
Память: сколько байт экономит массив
На 64-битной платформе указатель занимает 8 байт. Узел связного бинарного дерева с двумя потомками: 8 + 8 + значение. Для int это 20 байт, после выравнивания до кратного 8 - 24 байта. Тот же узел в массиве int - 4 байта. Экономия около 20 байт на узел, то есть примерно 20 МБ на миллион узлов.
Если значение крупное (скажем, структура на 64 байта), доля экономии падает: служебные 16-20 байт на фоне 64 байт полезных данных уже не так заметны. Выигрыш от массивного хранения максимален для мелких значений: индексов, счётчиков, ключей, сумм.
Дополнительные расходы связного представления: заголовки блоков у аллокатора, выравнивание каждого отдельного выделения, фрагментация кучи. Точные цифры зависят от аллокатора и платформы, но порядок такой: массив платит один раз за блок, связное дерево - за каждый узел.
Как считается адрес элемента внутри блока и почему размер элемента влияет на выравнивание, разобрано в статье про модели памяти и вычисление адреса по индексу.
Скорость: кэш-локальность и аллокации
Процессор работает с кэш-линиями по 64 байта. В массиве int одна линия вмещает 16 соседних узлов, поэтому переход к потомку часто попадает в уже загруженные данные. Обход в ширину идёт по возрастающим индексам почти линейно, а обход в глубину внутри поддерева остаётся в пределах участка массива, что тоже даёт попадания в кэш.
В связном представлении потомки лежат в разных местах кучи. Каждое обращение к ним - отдельный потенциальный промах кэша и, если данных нет в кэше, обращение к основной памяти. Чем больше дерево, тем выше вероятность промаха.
Аллокации добавляют вторую часть картины. Создание массива - одно выделение предсказуемого размера. Создание связного дерева на миллион узлов - миллион мелких выделений, каждое с накладными расходами, плюс работа сборщика мусора в управляемых языках на обходе миллиона объектов. Практический вывод: если дерево строится один раз и часто обходится, массив выигрывает. Разрыв сильно зависит от размера узла и профиля обращений, поэтому измеряйте на своём наборе данных. Как ведут себя аллокаторы и арены, разбираем в материале про массивы на стеке и в куче.
Где массивное хранение стало стандартом: кучи, сегментные деревья, статические структуры
Общее у этих структур одно: форма дерева известна и стабильна, а операции сводятся к перемещению по индексам. Указатели в них не дают ничего, кроме лишних байтов и промахов кэша.
Бинарная куча: почему массив - естественный выбор
Куча - полное бинарное дерево, где значение в каждом узле не больше (или не меньше) значений потомков. Полнота поддерживается автоматически: новый элемент добавляется в конец массива, то есть в первое свободное место последнего уровня.
Операции держатся на двух формулах. Просеивание вверх (sift-up) при вставке поднимает элемент к родителю (i-1)//2, пока порядок нарушен. Просеивание вниз (sift-down) при извлечении минимума сравнивает элемент с потомками 2i+1 и 2i+2 и опускает его. Обе операции стоят O(log n), а минимум или максимум всегда лежит в корне, то есть в ячейке 0, и читается за O(1).
В стандартной библиотеке Python модуль heapq работает именно с обычным списком: функции heappush и heappop принимают список и переставляют элементы по этим индексам. Пирамидальная сортировка (heapsort) укладывается в тот же массив без дополнительной памяти: после построения кучи максимум последовательно меняется местами с последним элементом. Приоритетная очередь на такой куче не хранит ни одного указателя.
Сегментное дерево: статическая структура на массиве
Сегментное дерево строят над фиксированным массивом, чтобы отвечать на запросы по отрезкам: сумма, минимум, максимум, НОД. Каждый узел соответствует отрезку исходного массива, корень - всему массиву, потомки - его половинам.
Под дерево выделяют массив размера 4n, где n - длина исходных данных. Запас нужен потому, что при делении отрезков пополам дерево не всегда получается идеально полным: рекурсивная нумерация с корнем в ячейке 1 и потомками 2v и 2v+1 даёт максимальный индекс меньше 4n. Для n = 8 хватает 32 ячеек, хотя реально используется 15. При нумерации с нуля те же переходы записываются как 2i+1 и 2i+2.
Построение занимает O(n), запрос и обновление одного элемента - O(log n). Массив тут уместен по той же причине, что и в куче: структура строится один раз, форма фиксирована, а переходы между узлами - арифметика по индексам.
Дерево Фенвика: массив как единственное представление
Дерево Фенвика (BIT) хранит префиксные суммы. В нём массив и есть структура, а не альтернатива связному представлению: ячейка с индексом i отвечает за диапазон, длина которого равна младшему установленному биту i. Переходы задаются выражением i & -i: прибавление этой величины идёт к следующему диапазону, вычитание - к предыдущему.
Памяти нужно ровно n+1 ячеек при нумерации с единицы (нулевая не используется), а обновление элемента и запрос префиксной суммы работают за O(log n). Ни одного указателя, ни одного объекта на узел, только целые числа.
Критерии выбора: чек-лист для быстрого решения
Чек-лист: 7 вопросов перед выбором
- Дерево полное бинарное? Если нет, массив потребует заполнителей или вовсе не подойдёт.
- Размер известен заранее и не меняется? Да - массив; нет - связное представление или динамический массив с ростом.
- Есть ли частые вставки и удаления в середине структуры? Да - указатели; массив потребует сдвигов и перевыделения.
- Важна ли экономия памяти на служебных полях? Да - массив, особенно при мелких значениях в узлах.
- Критична ли скорость обхода? Да - массив даёт лучшую кэш-локальность.
- Есть ли пропуски в узлах? Да - массив будет хранить пустые слоты, нужен список смежности или указатели.
- Планируется ли сериализация или передача по сети? Да - плоский массив упаковывается и распаковывается без обхода указателей.
Пример чтения ответов: полное дерево (да), размер известен (да), частых вставок нет (нет), экономия памяти важна (да), скорость обхода важна (да), пропусков нет (нет), сериализация нужна (да). Все семь ответов указывают на массив.
Матрица решений: массив vs указатели
| Сценарий | Выбор | Причина |
|---|---|---|
| Бинарная куча, приоритетная очередь | Массив | Дерево полное по построению, нужны индексы родителя и потомков |
| Сегментное дерево, дерево Фенвика | Массив | Статическая структура, запросы идут по индексам |
| Пирамидальная сортировка | Массив | Работает in-place без дополнительной памяти |
| Двоичное дерево поиска с вставками | Указатели | Форма меняется, сдвиги в массиве дороги |
| AVL, красно-чёрное дерево | Указатели | Балансировка перестраивает связи между узлами |
| B-дерево, индекс в СУБД | Указатели и страницы | Узел содержит переменное число ключей, дерево не бинарное |
| Разреженное дерево с пропусками | Список смежности, словарь | Пустые слоты в массиве съедают память |
| Статическое дерево для частого обхода | Массив | Непрерывная память и предсказуемый доступ |
Практическое правило: начинайте с массива, если структура данных позволяет, и переходите к указателям, когда появляются частые вставки и удаления или пропуски в узлах. Для кучи и сегментного дерева выбор очевиден.
Практические примеры и типичные ошибки
Пример на Python: куча на массиве
Минимальная куча на списке. Все переходы - по формулам нумерации с нуля.
class MinHeap:
def __init__(self):
self.a = []
def push(self, x):
self.a.append(x)
i = len(self.a) - 1
while i > 0:
p = (i - 1) // 2
if self.a[p] <= self.a[i]:
break
self.a[p], self.a[i] = self.a[i], self.a[p]
i = p
def pop(self):
top = self.a[0]
last = self.a.pop()
if self.a:
self.a[0] = last
n = len(self.a)
i = 0
while True:
left, right = 2 * i + 1, 2 * i + 2
m = i
if left < n and self.a[left] < self.a[m]:
m = left
if right < n and self.a[right] < self.a[m]:
m = right
if m == i:
break
self.a[i], self.a[m] = self.a[m], self.a[i]
i = m
return top
Проверка поведения: push(5), push(3), push(8) дают список [3, 5, 8], минимум в корне. pop() возвращает 3, после просеивания вниз в корне оказывается 5. Стандартный модуль heapq делает то же самое, только функции вызываются от списка: heapq.heappush(h, x) и heapq.heappop(h).
Пример на C++: сегментное дерево
Дерево сумм на статическом массиве. Нумерация с единицы: корень в t[1], потомки 2*v и 2*v+1.
const int MAXN = 100000;
int a[MAXN];
int t[4 * MAXN];
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
t[v] = t[2 * v] + t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) / 2;
return query(2 * v, tl, tm, l, min(r, tm))
+ query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
Пример: массив {1, 3, 5, 7, 9, 11}, запрос суммы на отрезке [1, 3] возвращает 15 (3 + 5 + 7). Запрос спускается по дереву и складывает значения тех узлов, чьи отрезки целиком попали в диапазон. Массив t берётся с запасом 4n: для n = 6 это 24 ячейки, хотя реально дерево занимает меньше.
Типичные ошибки и как их избежать
- Выход за границы массива. Перед чтением потомка проверяйте индекс: left < n, right < n. Для родителя проверяйте i > 0, иначе (i-1)//2 даст -1.
- Путаница нумерации с нуля и с единицы. Формулы 2i+1/2i+2 и 2i/2i+1 несовместимы в одном коде. Зафиксируйте систему в комментарии к структуре.
- Массив для неполного дерева. Если в раскладке есть пропуск, связи перестают соответствовать уровням. Проверьте полноту до того, как считать индексы.
- Переполнение индекса. Для дерева высоты 31 при нумерации с единицы максимальный индекс доходит до 2^32 - 1, и 32-битный знаковый int его не вмещает. Берите 64-битный тип или сверяйте высоту дерева заранее.
- Забытые пустые узлы. Если всё же храните неполное дерево в массиве, ставьте явное значение-заполнитель и проверяйте его при обходе, иначе пустая ячейка попадёт в вычисления.
- Неверный размер под сегментное дерево. Выделяйте 4n ячеек с запасом, а не ровно 2n: рекурсивное деление не всегда даёт идеально полное дерево.
Отладка на маленьких данных экономит часы. Возьмите дерево из 7 узлов, распечатайте массив, вручную выпишите для каждого узла родителя и потомков и сверьте с тем, что печатает код. Полезно добавить проверку инвариантов: для кучи - что значение в узле не больше значений потомков, для сегментного дерева - что значение узла равно сумме значений потомков.
Когда массив не подходит: ограничения и альтернативы
Динамические деревья: почему указатели лучше
Частые вставки и удаления ломают главное преимущество массива. Вставка нового узла в середину уровневой раскладки означает сдвиг элементов и, при нехватке места, перевыделение всего блока с копированием. Указатели дают другую стоимость: новый узел выделяется отдельно и привязывается к родителю за O(1) без перемещения существующих данных.
Балансировка добавляет аргумент. Красно-чёрное дерево, AVL-дерево, декартово дерево перестраивают связи при каждой вставке и удалении. Записывать такие перестройки в массив можно, но индексы перестают отражать структуру, и вы получаете массив с указателями внутри: и память тратится, и кэш-локальность теряется.
Структуры с произвольной арностью тоже плохо ложатся в простую раскладку. Формулы 2i+1 и 2i+2 заданы для бинарного дерева; для узла с переменным числом потомков нужна другая схема (например, представление «левый потомок - правый брат» или список смежности), и выигрыш уже не так очевиден.
Разреженные деревья: память против скорости
Разреженное дерево с пропусками заставляет массив хранить пустые слоты. Оценка простая: максимальный индекс при нумерации с единицей не превышает 2^(h+1) - 1, где h - высота. Дереву из 1000 узлов высотой 20 требуется массив до 2^21 - 1, то есть около 2,1 млн ячеек, из которых заполнена тысяча. Память уходит в пустоты.
Что использовать вместо массива: список смежности, где для каждого узла хранится список его потомков; словарь с ключом-индексом; связное представление с указателями. Все три хранят только существующие узлы. Оценки плотного и разреженного форматов, формулы расчёта памяти и порог, за которым разреженный формат выигрывает, разобраны в статье про плотное и разреженное хранение массивов.
Гибрид тоже встречается: статическая часть дерева лежит в массиве, а редкие динамические ветви вынесены в отдельные узлы со ссылками. Такой вариант усложняет обход и оправдан только тогда, когда профиль нагрузки известен и измерен.
Что сделать дальше: возьмите своё дерево и прогоните его по чек-листу из семи вопросов. Если дерево полное, размер фиксирован и обход частый, переводите его в массив: одна аллокация, формулы 2i+1 и 2i+2, никаких указателей. Если структура меняется каждый день, оставляйте связное представление и не тратьте время на переупаковку.