Массив [1, 2, 3, 4, 5, 6, 7] уже содержит бинарное дерево с тремя уровнями: корень лежит в ячейке 0, левый потомок узла i занимает ячейку 2i+1, правый — 2i+2, родитель — (i-1)/2. Указатели не нужны, лишних ячеек нет, переход к потомку стоит одно умножение со сложением и одно чтение памяти.
Представление работает, пока дерево полное: все уровни, кроме последнего, заполнены целиком, а последний занят слева направо без дыр. Отсутствие дыр делает нумерацию узлов по уровням сплошной. Если обходить дерево сверху вниз и слева направо, каждый следующий узел получает индекс на единицу больше предыдущего. Появляется пропуск в структуре — появляется ячейка-заполнитель в массиве, и экономия памяти исчезает.
Терминологическая тонкость: в русскоязычных текстах «полное бинарное дерево» чаще всего означает complete binary tree, то есть дерево с заполненными уровнями и последним уровнем слева направо. Дерево, у которого заняты вообще все уровни, называют «совершенным» (perfect). Дальше речь идёт про первый случай.
Ниже выводим формулы переходов, показываем построение массива из дерева и обратно, разбираем три классических обхода в рекурсивной и итеративной форме и определяем границы применимости: где массив выигрывает по памяти и кэшу, а где без ссылок не обойтись.
Почему полное бинарное дерево укладывается в массив без пропусков
Причина в геометрии уровней. На уровне k помещается ровно 2^k узлов, и при сплошной нумерации первый узел этого уровня получает индекс 1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1. Значит, индексы уровня k занимают диапазон от 2^k - 1 до 2^(k+1) - 2 без единого разрыва.
Связь между уровнем узла и его индексом
Дерево с уровнями 0, 1, 2 (семь узлов) занимает индексы 0..6. Дерево с уровнями 0..3 (пятнадцать узлов) — индексы 0..14. Общее число узлов в дереве из h+1 уровней равно 2^(h+1) - 1, последний индекс равен 2^(h+1) - 2, и каждое промежуточное значение занято.
Отсюда же выводится высота. Для полного дерева с n узлами высота в рёбрах равна floor(log2 n): при n = 7 это 2, при n = 1 000 000 это 19. Это утверждение опирается на стандартный результат о высоте полного бинарного дерева; доказательство по индукции разобрано в обсуждении на Math Stack Exchange. Высота задаёт глубину рекурсии и максимальный размер стека при обходе, поэтому логарифм здесь имеет прямую практическую цену.
Неполное дерево ведёт себя иначе. Если у узла с индексом 2 есть левый потомок, но нет правого, а следующий уровень продолжается, в массиве появляются ячейки без значений. Их заполняют маркером (null, -1, отдельный бит присутствия) и проверяют при каждом обходе. Массив остаётся корректным, но перестаёт быть плотным, а свойство кучи, на котором держатся очереди с приоритетом, требует непрерывной укладки уровней.
Формулы переходов: потомки и родитель
Выведем формулу левого потомка. Узел i стоит на уровне k = floor(log2(i + 1)) и занимает на своём уровне позицию p = i - (2^k - 1). Уровень k+1 начинается с индекса 2^(k+1) - 1, а потомки узла стоят на позициях 2p и 2p + 1. Отсюда:
left(i) = 2^(k+1) - 1 + 2p = 2i + 1 right(i) = 2^(k+1) - 1 + 2p + 1 = 2i + 2 parent(i) = (i - 1) / 2 # целочисленное деление, для i > 0
Проверка на массиве [1, 2, 3, 4, 5, 6, 7]: для i = 2 (значение 3) левый потомок получает индекс 5 (значение 6), правый — индекс 6 (значение 7), родитель — индекс 0 (значение 1).
Границы проверяйте до обращения к массиву. Левый потомок существует при 2i + 1 < n, правый при 2i + 2 < n. Если нумерация с единицы, формулы меняются на left = 2i, right = 2i + 1, parent = i / 2, и смешивать эти два варианта нельзя: ошибка off-by-one даёт чтение чужого поддерева.
Построение бинарного дерева из массива и обратно
Отдельная структура для дерева не нужна: массив уже есть дерево. Достаточно функций навигации, которые считают индекс и проверяют границу.
Псевдокод для навигации по массиву
# a - массив значений, n - a.length
left_child(a, i):
j = 2 * i + 1
return j < n ? j : -1
right_child(a, i):
j = 2 * i + 2
return j < n ? j : -1
parent(i):
return i > 0 ? (i - 1) / 2 : -1
Вызов left_child(a, 2) для массива из семи элементов вернёт 5, right_child(a, 2) вернёт 6, parent(6) вернёт 2. Возврат -1 вместо исключения позволяет обходить дерево циклом без обработчиков ошибок.
Генерация массива из дерева через BFS
Обратная задача встречается при сериализации: дерево построено на узлах со ссылками, нужно получить плоский массив. Порядок заполнения совпадает с обходом в ширину.
to_array(root, height):
n = 2^(height + 1) - 1
a = массив размера n, заполненный null
queue = [ (root, 0) ]
while queue не пуста:
(node, i) = queue.pop_front()
if node == null: continue
a[i] = node.value
queue.push_back( (node.left, 2*i + 1) )
queue.push_back( (node.right, 2*i + 2) )
return a
Для полного дерева массив заполнится целиком. Для неполного останутся null-ячейки, их число равно 2^(h+1) - 1 - n, где h — высота дерева. При h = 20 и n = 1000 это больше двух миллионов пустых ячеек на тысячу значений, поэтому для разреженных деревьев формат не подходит.
Обходы бинарного дерева в массиве: прямой, симметричный, обратный
Все три обхода отличаются только порядком трёх действий: посетить узел, уйти в левое поддерево, уйти в правое. В массивном представлении вместо разыменования ссылки подставляется индекс 2i+1 или 2i+2, поэтому код короче и не требует полей-указателей. Единственное условие выхода — i >= n: оно закрывает и отсутствие правого потомка, и выход за границу массива.
Прямой обход (preorder) без указателей
preorder(a, i, n, out):
if i >= n: return
out.push(a[i])
preorder(a, 2*i + 1, n, out)
preorder(a, 2*i + 2, n, out)
Для [1, 2, 3, 4, 5, 6, 7] результат: 1, 2, 4, 5, 3, 6, 7. Порядок: корень, левое поддерево, правое поддерево.
Симметричный обход (inorder) без указателей
inorder(a, i, n, out):
if i >= n: return
inorder(a, 2*i + 1, n, out)
out.push(a[i])
inorder(a, 2*i + 2, n, out)
Результат для того же массива: 4, 2, 5, 1, 6, 3, 7. Если ключи уложены по правилу дерева поиска, обход даёт возрастающую последовательность, и это самый дешёвый способ проверить корректность индексации после любой правки кода.
Обратный обход (postorder) без указателей
postorder(a, i, n, out):
if i >= n: return
postorder(a, 2*i + 1, n, out)
postorder(a, 2*i + 2, n, out)
out.push(a[i])
Результат: 4, 5, 2, 6, 7, 3, 1. Обход применяется там, где потомки нужны раньше родителя: освобождение памяти, вычисление выражений, подсчёт размеров поддеревьев.
Итеративные обходы без указателей: стек и индексы
Рекурсия на полном дереве безопасна: глубина равна floor(log2 n), то есть 19 кадров для миллиона узлов. Если рекурсия нежелательна из-за лимита стека потока, обход переписывается на явный стек индексов. Указатели не нужны ни в одном варианте.
Итеративный preorder с одним стеком
preorder_iter(a, n):
out = []
if n == 0: return out
stack = [0]
while stack не пуст:
i = stack.pop()
out.push(a[i])
if 2*i + 2 < n: stack.push(2*i + 2)
if 2*i + 1 < n: stack.push(2*i + 1)
return out
Правый потомок кладётся первым, чтобы левый оказался на вершине стека и обработался раньше. Порядок совпадает с рекурсивной версией: 1, 2, 4, 5, 3, 6, 7. Размер стека не превышает высоту дерева плюс один элемент.
Итеративный inorder: левый-корень-правый
inorder_iter(a, n):
out = []
stack = []
i = 0
while stack не пуст or i < n:
while i < n:
stack.push(i)
i = 2*i + 1
i = stack.pop()
out.push(a[i])
i = 2*i + 2
return out
Внутренний цикл уходит влево до первого пустого места, складывая индексы в стек. Затем индекс снимается со стека, значение выводится, и обход переходит в правое поддерево. Память ограничена h+1 индексами.
Итеративный postorder через два стека
postorder_iter(a, n):
out = []
if n == 0: return out
stack1 = [0]
stack2 = []
while stack1 не пуст:
i = stack1.pop()
stack2.push(i)
if 2*i + 1 < n: stack1.push(2*i + 1)
if 2*i + 2 < n: stack1.push(2*i + 2)
while stack2 не пуст:
out.push(a[stack2.pop()])
return out
Первый стек даёт порядок «корень, правый, левый», второй разворачивает его в «левый, правый, корень»: 4, 5, 2, 6, 7, 3, 1. Альтернатива без второго стека — хранить пару (индекс, признак посещения), но тогда на каждый узел тратится вдвое больше памяти.
Все три версии дают O(n) по времени: каждый индекс попадает в стек ровно один раз. Память под стек — O(h), для полного дерева это O(log n).
Вычислительная сложность и сравнение с указательным представлением
Память: массив против указателей
Расчёт для n узлов. Массив: n * sizeof(value) плюс O(1) на заголовок. Узлы со ссылками: n * (sizeof(value) + 2 * sizeof(pointer)) плюс заголовок объекта и выравнивание. На 64-битной платформе указатель занимает 8 байт, значение int — 4 байта. Точный размер узла зависит от ABI и порядка полей: структуры выравниваются по самому строгому требованию среди своих членов, и между полями могут появляться байты-заполнители. Это правило зафиксировано в System V ABI: каждый член размещается по наименьшему доступному смещению с подходящим выравниванием. Например, для структуры с int, int и указателем на 64-битной платформе компилятор добавляет заполнитель, и sizeof такой структуры равен 24 байтам, а не 16 — такой разбор приведён в обсуждении Structure padding clarification for 32-bit and 64-bit architecture. Поэтому узел со связями на практике занимает заметно больше, чем 4 байта на элемент массива, хотя конкретные цифры зависят от компилятора и целевой платформы.
| Показатель | Массив (полное дерево) | Узлы с указателями |
|---|---|---|
| Память на n узлов | n * sizeof(value) | n * (sizeof(value) + 2 * указатель + заполнители) |
| 1 000 000 узлов, int и 64-битные указатели | около 4 МБ данных | существенно больше; точный объём зависит от ABI и выравнивания |
| Переход к потомку | арифметика 2i+1 или 2i+2 | разыменование указателя |
| Расположение в памяти | один непрерывный блок | узлы разбросаны по куче |
| Вставка и удаление | O(n) на сдвиг либо пропуски | O(1) при известном месте |
| Обход | O(n) время, O(h) стек | O(n) время, O(h) стек |
Для неполного дерева картина разворачивается: массив может занять до 2^(h+1) - 1 ячеек, и при большом числе пропусков он проигрывает связному представлению по памяти. Пороговые значения, при которых плотный формат ещё выгоден, разбираются в статье про плотное и разрежённое хранение массивов.
Скорость и кэш-локальность
Доступ к потомку в массиве — это сложение и чтение по адресу вида база + индекс * sizeof(value). Соседние индексы лежат рядом, поэтому при обходе уровня процессор подтягивает в кэш сразу несколько значений одной кэш-линией. В руководстве Intel по оптимизации размер кэш-линии указан как 64 байта, то есть при 4-байтовом int в одну линию помещается 16 значений (см. Intel 64 and IA-32 Architectures Optimization Reference Manual). В связном представлении узлы разбросаны по куче в порядке аллокаций, и каждый переход к потомку может уйти в промах кэша.
Насколько велика разница, зависит от размера дерева и архитектуры: пока структура целиком помещается в L2 или L3, разрыв мал, а на десятках миллионов узлов выигрыш массива растёт. Устройство непрерывного блока и адресную арифметику мы разбирали в материале как массивы хранятся в оперативной памяти, а методика сравнения расчётного и фактического объёма с инструментами профилирования собрана в статье про измерение памяти под массивы.
Практические примеры и подводные камни
Пример: обход кучи, хранящейся в массиве
Массив [10, 20, 30, 40, 50, 60, 70] — минимальная куча: каждый родитель не больше своих потомков (10 < 20, 10 < 30, 20 < 40, 20 < 50, 30 < 60, 30 < 70). Три обхода дают:
- preorder: 10, 20, 40, 50, 30, 60, 70;
- inorder: 40, 20, 50, 10, 60, 30, 70;
- postorder: 40, 50, 20, 60, 70, 30, 10.
Извлечение минимума использует те же формулы индексации:
extract_min(a, n):
if n == 0: return null
result = a[0]
n = n - 1
a[0] = a[n]
i = 0
while true:
l = 2*i + 1
r = 2*i + 2
m = i
if l < n and a[l] < a[m]: m = l
if r < n and a[r] < a[m]: m = r
if m == i: break
swap(a[i], a[m])
i = m
return result
Просеивание вниз идёт по одной ветви, поэтому стоит O(log n), а весь цикл n извлечений даёт O(n log n). По этой же схеме работают пирамидальная сортировка и стандартные очереди с приоритетом. В частности, модуль heapq из стандартной библиотеки Python реализует минимальную кучу на списках с нулевой индексацией: наименьший элемент всегда находится в корне, а сама куча представлена плоским списком, а не узлами со ссылками — это описано в документации heapq и разобрано в статье The Python heapq Module. Аналогичный подход применяется и в других языках, где очередь с приоритетом строится поверх массива или среза.
Ограничения и как их обойти
- Неполные деревья с большими пропусками. Расход памяти упирается в 2^(h+1) - 1 ячеек: при h = 20 это больше двух миллионов ячеек независимо от того, сколько узлов реально занято. Для разреженных случаев берите словарь «индекс — узел» или связное представление.
- Частые вставки и удаления в середине. Сдвиг элементов стоит O(n), а если держать дыры, растёт память. Цену копирования при росте буфера разбирали в статье про динамические массивы и реаллокацию.
- Переполнение индекса. Значение 2i+2 для последнего узла может выйти за пределы 32-битного знакового int при больших n. В C++ переполнение знакового целого — неопределённое поведение, что прямо зафиксировано в cppreference, поэтому полагаться на «естественное» переполнение нельзя. Храните индексы в size_t, long или другом 64-битном типе, либо проверяйте i <= (n - 2) / 2 до вычисления потомков.
- Путаница нумерации. Варианты с нуля (2i+1, 2i+2, (i-1)/2) и с единицы (2i, 2i+1, i/2) несовместимы; смешивание даёт обход чужого поддерева без единой ошибки в компиляторе.
- Маркеры и проверки. Для неполного дерева каждая граница превращается в связку «граница плюс маркер», и рекурсивный код теряет лаконичность.
Чек-лист перед внедрением
- Убедитесь, что дерево полное, и оцените долю пропусков до выбора массива.
- Зафиксируйте нумерацию: с нуля или с единицы, и пропишите её в комментарии к функциям навигации.
- Проверяйте границы до чтения: 2i + 1 < n, 2i + 2 < n.
- Держите индексы в 64-битном типе, если n больше 10^9.
- Для обхода без рекурсии используйте стек индексов: его глубина не превысит log2 n + 1.
Самый быстрый способ проверить корректность индексации на своём массиве — вызвать inorder от корня и убедиться, что значения идут по возрастанию. Если порядок сбился, ищите ошибку в формулах перехода, а не в логике обхода: на полном дереве обе рекурсивные версии, итеративные варианты и обход в ширину обязаны давать одну и ту же последовательность.