Индексация бинарного дерева в массиве: формулы переходов и граничные случаи без off-by-one

При нумерации с нуля формулы индексации такие: родитель узла i — это floor((i - 1) / 2) с целочисленным делением, левый потомок — 2i + 1, правый — 2i + 2. При нумерации с единицы формулы отличаются от случая с корнем в индексе 0: родитель i / 2, левый 2i, правый 2i + 1.

Существование узла проверяется сравнением с фактическим числом элементов n: для нумерации с нуля левый потомок есть при 2i + 1 < n, правый — при 2i + 2 < n. Для нумерации с единицы условия меняются на 2i <= n и 2i + 1 <= n. Разница в одном знаке сравнения — самая частая причина off-by-one, когда код проходит на полном дереве и падает на последнем неполном уровне.

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

Зачем вообще хранить бинарное дерево в массиве

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

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

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

Где это применяется на практике

Формулы 2i + 1 и 2i + 2 лежат в основе структур, с которыми инженер встречается ежедневно:

• binary heap в очередях с приоритетом: heapq в Python, std::priority_queue поверх std::push_heap и std::pop_heap в C++, java.util.PriorityQueue в Java;
• куча в планировщиках задач и таймерах: узлы упорядочены по времени срабатывания, извлечение минимума идёт за O(log n);
• сегментное дерево для запросов на отрезке: сумма, минимум, максимум на диапазоне за O(log n);
• дерево турнира (tournament tree) для выбора победителя в группах и в алгоритмах сортировки слиянием;
• Fenwick tree (BIT) как родственная структура: индексация там другая, через младший установленный бит, но принцип хранения в плоском массиве тот же.

Во всех случаях переходы между узлами — фундамент для sift-up и sift-down. Ошибка в формуле не ломает компиляцию, она ломает порядок элементов.

Детали внутренней нумерации конкретных библиотек сверяйте с документацией своей версии: реализации менялись между релизами, и код, скопированный из старого ответа на форуме, может опираться на другую схему. Из подтверждённого: heapq в Python явно использует нумерацию с нуля и хранит min-кучу как список, элементы которого считаются с нуля (документация heapq). Для std::priority_queue, std::push_heap, std::pop_heap и java.util.PriorityQueue в проверенных источниках прямого подтверждения формул 2i + 1 и 2i + 2 нет — считайте это ожидаемым поведением, но сверяйтесь с документацией вашей версии.

Формулы переходов: нумерация с нуля

Схема, где корень занимает индекс 0, задаётся тремя выражениями:

• родитель: parent = floor((i - 1) / 2), деление целочисленное;
• левый потомок: left = 2i + 1;
• правый потомок: right = 2i + 2.

Проверим на полном дереве из семи узлов A, B, C, D, E, F, G с индексами 0..6:

У индексов 7..14 в массиве из семи элементов ячеек нет, поэтому переход к потомкам узлов последнего уровня требует проверки границы.

Узел 0 — корень, родителя у него не существует. Выражение floor((0 - 1) / 2) даёт -1, и это значение нельзя использовать как индекс. Поэтому переход к родителю всегда защищают условием i > 0. Отдельно стоит помнить про Python: деление с округлением вниз округляет к следующему меньшему числу, а не к меньшему по абсолютной величине, поэтому отрицательные значения ведут себя не так, как ожидается при переносе кода из C-подобных языков. Обращение к a[-1] в Python не падает, а молча отдаёт последний элемент массива. Обмен с чужим узлом не даёт ни исключения, ни явного сбоя, ошибка всплывает позже и в другом месте.

Почему формулы работают именно так

Полное бинарное дерево укладывается в массив по уровням. Уровень 0 содержит 2^0 = 1 узел, уровень 1 содержит 2^1 = 2 узла, уровень k содержит 2^k узлов. Перед уровнем k лежат все предыдущие уровни, их суммарный размер равен 2^k - 1, поэтому первый индекс уровня k — это 2^k - 1. Для уровня 0 получаем 2^0 - 1 = 0, для уровня 1 — 1, для уровня 2 — 3: таблица выше это подтверждает.

Пусть узел i стоит на уровне k и занимает в нём позицию p, тогда i = 2^k - 1 + p, где p меняется от 0 до 2^k - 1. Левый потомок этого узла — первый узел уровня k + 1, сдвинутый на 2p позиций: 2^(k + 1) - 1 + 2p. Подставим i: 2^(k + 1) - 1 + 2p = 2 * (2^k + p) - 1 = 2 * (2^k - 1 + p) + 1 = 2i + 1. Правый потомок стоит на позицию дальше: 2i + 2. Обратный переход: i = 2 * parent + 1 или i = 2 * parent + 2, отсюда parent = floor((i - 1) / 2). Выводить формулы заново не придётся, но понимание вывода помогает поймать ошибку в момент, когда она появляется.

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

Формулы переходов: нумерация с единицы

Схема с корнем в индексе 1 встречается в учебниках и в описаниях алгоритмов на псевдокоде. Формулы выглядят короче:

• родитель: parent = i / 2, деление целочисленное;
• левый потомок: left = 2i;
• правый потомок: right = 2i + 1.

На уровне k первый индекс равен 2^(k - 1): уровень 1 начинается с индекса 1, уровень 2 — с 2, уровень 3 — с 4. То же дерево из семи узлов получает индексы 1..7:

Ячейка с индексом 0 остаётся пустой или хранит служебное значение. Массив занимает n + 1 позиций для n узлов, если не сдвигать данные влево при чтении и записи.

Оговорка по источникам: в проверенных материалах подтверждено только то, что формулы при корне в индексе 1 отличаются от случая с корнем в индексе 0. Конкретные выражения 2i, 2i + 1 и i / 2 приведены как стандартная учебная схема; при работе с конкретной библиотекой сверяйтесь с её документацией.

Сравнение двух схем: что выбрать

В продакшене берите нумерацию с нуля. Она совпадает с индексацией массивов в C, C++, Go, Rust, Java и Python, не требует пустой ячейки и работает с heapq напрямую, без пересчёта. Схема с единицы удобнее там, где компактность формул важнее расхода одной ячейки: в сегментном дереве с листьями в позициях n..2n - 1 переход left = 2i, right = 2i + 1 читается без вычитаний, а условие i / 2 для родителя не требует отдельной обработки нуля.

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

Граничные случаи: проверка существования узла

Проверки для нумерации с нуля, где n — фактическое число узлов:

• exists(i, n) = i >= 0 and i < n;
• has_left(i, n) = 2i + 1 < n;
• has_right(i, n) = 2i + 2 < n;
• has_parent(i) = i > 0.

Для нумерации с единицы при узлах 1..n условия сдвигаются на один:

• has_left(i, n) = 2i <= n;
• has_right(i, n) = 2i + 1 <= n;
• has_parent(i) = i > 1.

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

Неполные уровни бинарного дерева

Неполное дерево хранится без пропусков: узлы идут по уровням слева направо, в порядке обхода BFS. Частично заполнен только последний уровень, поэтому часть вычисленных индексов выходит за границу массива.

Массив [10, 20, 30, 40, 50], n = 5:

Узел 30 с индексом 2 остаётся без потомков: 2 * 2 + 1 = 5 не меньше 5. Узлы с индексами 5 и 6 отсутствуют. Добавьте шестой элемент, и узел с индексом 5 появится как левый потомок узла 2, а индекс 6 всё ещё будет за границей. Так выглядит неполный последний уровень: левый потомок есть, правого нет. Этот случай нужно обрабатывать отдельно, иначе sift-down обратится к a[2i + 2] и получит либо исключение, либо чужой элемент из следующей структуры в памяти.

Готовые функции-проверки

Псевдокод для нумерации с нуля, строки разделены переносом:

has_left(a, i):
return 2 * i + 1 < len(a)

has_right(a, i):
return 2 * i + 2 < len(a)

parent(i):
if i == 0: return none
return (i - 1) // 2

children(a, i):
l = 2 * i + 1
if l >= len(a): return []
r = l + 1
if r < len(a): return [l, r]
return [l]

Функция children возвращает одного потомка, если правого нет. Такой контракт удобнее для sift-down: цикл получает готовый список индексов и не пересчитывает границы повторно.

Порядок проверок в чек-листе: убедиться, что i >= 0 и i < n, вычислить индексы потомков, сравнить каждый с n, и только после этого читать элементы массива.

Типичные ошибки off-by-one при пересчёте индексов

1. Смешение схем нумерации. В коде с корнем в индексе 0 родитель считается как i / 2. Для узла 2 это даёт 1, хотя родитель — узел 0. Исправление: floor((i - 1) / 2).
2. Дробное деление в Python. Выражение (i - 1) / 2 возвращает 1.0 вместо 1, и a[1.0] выбрасывает TypeError. Пишите //. В C, C++, Go и Java деление значений целого типа уже отбрасывает остаток, но поведение на отрицательных значениях в проверенных источниках не подтверждено — не полагайтесь на него без проверки в вашем языке.
3. Перепутанные потомки. left = 2i + 2 и right = 2i + 1. Куча собирается и даже извлекает минимум, но порядок ломается на узлах с двумя потомками. Инвариант a[parent] <= a[i] на случайных данных ловит подмену за один прогон.
4. Неверное условие границы. left < n вместо left <= n в схеме с единицы. На полном дереве из семи узлов теряется узел 7, и куча сортирует шесть элементов из семи.
5. Забытая проверка i > 0 при подъёме. В Python parent для корня даёт -1, a[-1] возвращает последний элемент, обмен идёт с чужим узлом и не падает. В Go и C отрицательный индекс — паника или запись за границу массива.
6. Чтение правого потомка без проверки. Код берёт a[2i + 2] до сравнения с n. Сначала проверка right < n, иначе в качестве кандидата используется только left.
7. Переполнение при вычислении индекса. При очень больших n выражение 2i + 1 может выйти за диапазон 32-битного целого. Конкретный порог зависит от типа и платформы, поэтому держите индексы в size_t или int64 и выполняйте сравнение на 64-битных значениях.
8. Пересчёт на границе модулей. Обёртка над 1-based алгоритмом принимает 0-based индекс, и внутри добавляется лишняя единица. Пересчёт делайте ровно в одной точке кода, на входе и выходе API.

Как отладить индексацию

Выведите дерево по уровням: для каждого уровня напечатайте индексы и значения, затем сравните с ожидаемой картинкой. Смещение на единицу видно сразу: узел, который должен стоять на месте 2, оказывается на месте 3, и всё поддерево сдвигается вместе с ним.

Покройте тестами граничные размеры n = 0, 1, 2, 3, 7, 8. При n = 0 массив пуст, ни одна проверка не проходит. При n = 1 у корня нет ни потомков, ни родителя. При n = 3 заполнены оба потомка корня, а сам корень остаётся единственным узлом с двумя детьми. При n = 7 дерево полное, последний уровень занимает индексы 3..6. При n = 8 добавляется узел с индексом 7 — левый потомок узла 3, а правого потомка у узла 3 нет.

Дальше прогоните инвариант: для каждого i, у которого есть левый потомок, должно выполняться parent(left(i)) == i, так же для правого. Один проход по всем i от 0 до n - 1 ловит ошибку формул целиком, без разбора отдельных случаев.

Практика: куча и сегментное дерево

В min-heap с нумерацией с нуля sift-up поднимает узел, пока он меньше родителя:

i = n - 1
while i > 0:
p = (i - 1) // 2
if a[i] >= a[p]: break
swap(a[i], a[p])
i = p

sift-down выбирает меньшего из двух потомков и меняет его местами с текущим узлом:

i = 0
while true:
l = 2 * i + 1
if l >= n: break
r = l + 1
m = l
if r < n and a[r] < a[l]: m = r
if a[i] <= a[m]: break
swap(a[i], a[m])
i = m

Проверка r < n стоит до сравнения значений. Без неё на неполном последнем уровне читается элемент за границей. Переменная l + 1 и есть правый потомок 2i + 2, отдельное имя нужно только для читаемости.

В сегментном дереве, представленном массивом, для узла с индексом i левый потомок находится по индексу 2i + 1, правый — по 2i + 2, а родитель — по floor((i - 1) / 2). Дерево строится на массиве из n элементов: листьев n, внутренних узлов n - 1, общее число узлов 2n - 1. Размер памяти, выделяемой под массив, составляет 2 * 2^ceil(log2 n) - 1. Такое представление позволяет отвечать на запросы по диапазону и модифицировать массив за O(log n). Этот массив остаётся непрерывным блоком, и адрес любого листа считается той же формулой base + i * size, что и для обычного массива: подробнее в статье Элементы массива лежат в непрерывной области памяти: base + i * size.

Схема с единичной нумерацией, где листья лежат в позициях n..2n - 1, а внутренние узлы занимают 1..n - 1, встречается в учебных описаниях, но в проверенных источниках она не подтверждена: там приведено 0-based представление с размером 2 * 2^ceil(log2 n) - 1. Если выбираете её, проверяйте границы по фактическому размеру массива.

Шпаргалка формул

Деление целочисленное. В Python это //, в C, C++, Go и Java деление значений целого типа уже отбрасывает остаток. n везде означает фактическое число узлов.

Чек-лист перед продакшеном

• схема нумерации выбрана одна и записана в комментарии к модулю;
• все переходы к родителю используют целочисленное деление;
• переход к родителю защищён условием i > 0, для 1-based — i > 1;
• проверки границ сравниваются с числом узлов n, а не с ёмкостью буфера;
• sift-down проверяет правый потомок до чтения элемента;
• тесты покрывают n = 0, 1, 2, 3, 7, 8 и неполный последний уровень;
• инвариант parent(left(i)) == i прогоняется по всем i от 0 до n - 1;
• индексы хранятся в типе, который не переполняется при 2i + 2;
• пересчёт между 0-based и 1-based происходит ровно в одной точке кода.

Сохраните таблицу формул рядом с кодом кучи или сегментного дерева и прогоните проверку инварианта на реальных размерах данных. Так off-by-one перестаёт быть ошибкой, которую ищут по логам ночью, и остаётся арифметикой из двух действий.