Высота и глубина дерева: формулы и примеры

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

Определения: высота и глубина

Глубина узла $d(v)$ -- это длина пути от корня до узла $v$, то есть количество рёбер на этом пути. У корня глубина равна нулю: $d(\text{root}) = 0$. У детей корня $d = 1$, у их детей $d = 2$ и так далее. Формально:

$d(v) = \text{число рёбер на пути от корня до } v.$

Высота узла $h(v)$ -- длина наидлиннейшего пути от узла $v$ вниз до листа:

$h(v) = \max_{l \in \text{leaves}(v)} d(l, v),$

где $d(l, v)$ -- расстояние от $v$ до листа $l$ в поддереве под $v$. У листа высота равна нулю: $h(\text{leaf}) = 0$.

Высота дерева $H$ -- это высота корня:

$H = h(\text{root}) = \max_{l \in \text{leaves}} d(\text{root}, l).$

Иными словами, высота дерева -- длина наидлиннейшего пути от корня до любого листа.

Рассчитать для своей задачи

Формулы для полного двоичного дерева

Полное двоичное дерево -- структура, в которой каждый нелистовой узел имеет ровно двух потомков, а все листья находятся на одном уровне. Если дерево состоит из $n$ уровней (уровни $0, 1, \ldots, n-1$):

Эти соотношения легко проверить: на уровне 0 -- один корень ($2^0 = 1$), на уровне 1 -- два узла ($2^1 = 2$), на уровне 2 -- четыре ($2^2 = 4$) и так далее. Суммарно по геометрической прогрессии:

$\sum_{k=0}^{n-1} 2^k = 2^n - 1.$

Отсюда и обратная формула: если в полном двоичном дереве $N$ узлов, то его высота $H = \lfloor \log_2 N \rfloor$.

Рассчитать для своей задачи

Высота вырожденного дерева

Вырожденное (или патологическое) дерево -- это крайний случай: каждый нелистовой узел имеет ровно одного потомка. Такое дерево структурно эквивалентно связному списку. При $n$ узлах:

$H = n - 1, \quad \text{листьев} = 1.$

Алгоритм двоичного поиска в таком дереве деградирует до линейного: на каждом уровне одна ветвь, поэтому поиск элемента требует $O(n)$ шагов вместо $O(\log n)$ в сбалансированном дереве. Именно для предотвращения вырождения придуманы AVL-деревья и красно-чёрные деревья -- они гарантируют, что высота не превысит $O(\log n)$.

Рассмотрим пример: вставим ключи $1, 2, 3, 4, 5$ в BST без балансировки в порядке возрастания. Каждый новый ключ окажется правым потомком предыдущего, и дерево вытянется в прямую линию. Глубина узла со значением 5 будет равна 4, высота всего дерева тоже 4 -- хотя в полном двоичном дереве из 5 узлов $H = \lfloor \log_2 5 \rfloor = 2$. Это наглядно показывает, насколько важна очерёдность вставки для неавтобалансирующихся деревьев.

Рекурсивный алгоритм вычисления высоты

Высоту дерева можно найти рекурсивно: высота пустого дерева равна $-1$ (или $0$ в соглашении «считаем узлы»), высота листа -- $0$, высота нелистового узла -- максимум высот его поддеревьев плюс единица:

$h(v) = \begin{cases} -1, & v = \text{None} \\ 0, & v \text{ -- лист} \\ 1 + \max(h(v.\text{left}),\ h(v.\text{right})), & \text{иначе} \end{cases}$

Псевдокод:

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

Алгоритм обходит каждый узел ровно один раз, поэтому временная сложность -- $O(n)$, а пространственная -- $O(H)$ (глубина стека рекурсии).

Глубина узла считается иначе -- не рекурсией вниз, а обходом вверх (или сверху вниз с передачей текущей глубины):

def depth(node, target, d=0):
    if node is None:
        return -1
    if node == target:
        return d
    left = depth(node.left, target, d + 1)
    if left != -1:
        return left
    return depth(node.right, target, d + 1)

Связь между высотой и числом узлов

Для любого двоичного дерева с $N$ узлами высота удовлетворяет двусторонней оценке:

$\lfloor \log_2 N \rfloor \leq H \leq N - 1.$

Левая граница достигается на полном дереве, правая -- на вырожденном. Это неравенство объясняет, почему инженеры так заботятся о балансировке: разница между $\log_2 N$ и $N - 1$ для больших $N$ огромна. Например, при $N = 1\,000\,000$: $H_{\min} = 19$ против $H_{\max} = 999\,999$.

Рассчитать для своей задачи

Высота в стандартных структурах данных

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

• Двоичное дерево поиска (BST). Без балансировки высота зависит от порядка вставки: при случайных ключах ожидаемая $H \approx 2 \ln N$, в худшем случае $H = N - 1$ (вставка уже отсортированного ряда).
• AVL-дерево. Гарантирует $H \leq 1{,}44 \log_2(N + 2)$. Балансировка выполняется поворотами при нарушении «баланс-фактора» ($|h(\text{left}) - h(\text{right})| \leq 1$ в каждом узле).
• Красно-чёрное дерево. Гарантирует $H \leq 2 \log_2(N + 1)$.
• Куча (heap). Хранится в массиве, логически образует полное дерево; высота $H = \lfloor \log_2 N \rfloor$.
• B-дерево. Используется в базах данных и файловых системах; каждый узел хранит от $t-1$ до $2t-1$ ключей (параметр $t$ -- минимальная степень). Высота B-дерева не превышает $\log_t \frac{N+1}{2}$, что позволяет существенно сократить число дисковых операций по сравнению с двоичными деревьями.

Зная высоту дерева в конкретной реализации, можно сразу оценить трудоёмкость операций. Например, в AVL-дереве с $N = 10^6$ узлов $H \leq 1{,}44 \cdot 20 \approx 29$ -- это означает не более 29 сравнений при поиске, независимо от того, в каком порядке вставлялись данные.

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

• Путаница «высота» и «глубина». Глубина -- свойство узла (расстояние от корня вниз), высота -- тоже свойство узла, но в обратном направлении (от него до листа). Высота дерева = высота корня. Новички нередко подставляют глубину туда, где нужна высота.
• Несогласованность соглашения о нумерации. В одних источниках высота листа равна 0, в других -- 1. Число уровней $n$ и высота $H$ тоже соотносятся по-разному ($H = n-1$ или $H = n$). Перед решением задачи уточни, какое соглашение принято.
• Неверная рекурсия для пустого поддерева. Если возвращать $h(\text{None}) = 0$, а не $-1$, листья получат высоту 1 вместо 0. Это сдвигает все значения на единицу.
• Смешение высоты дерева и максимальной глубины листа. Оба значения совпадают по определению, но при реализации через разные алгоритмы (сверху вниз и снизу вверх) легко получить расхождение из-за ошибки в базовом случае.
• Игнорирование вырождения при вставке. При вставке уже отсортированного массива в BST без балансировки дерево вырождается в список: высота становится $N - 1$ вместо $\log_2 N$.

FAQ

Чем отличается высота от глубины в дереве? Глубина узла -- расстояние от корня до этого узла (метрика сверху вниз). Высота узла -- длина самого длинного пути от этого узла до листа (метрика снизу вверх). У одного и того же узла глубина и высота обычно разные числа; совпадают только в вырожденных случаях.

Как посчитать высоту двоичного дерева с n узлами? Зависит от структуры дерева. Для полного двоичного дерева с $n$ уровнями $H = n - 1$. Для произвольного BST из $N$ узлов -- рекурсивно: $h(v) = 1 + \max(h(v.\text{left}), h(v.\text{right}))$, $h(\text{None}) = -1$. Нижняя оценка: $H \geq \lfloor \log_2 N \rfloor$.

Почему высота влияет на скорость операций в дереве? Операции поиска, вставки и удаления в BST занимают $O(H)$ шагов: на каждом шаге спускаемся на один уровень. При сбалансированном дереве $H = O(\log N)$ -- быстро. При вырождении $H = O(N)$ -- медленно, как линейный поиск. Поэтому балансировка деревьев так важна для производительности.

Коротко

Глубина узла -- расстояние от корня до узла, высота узла -- длина длиннейшего пути вниз до листа. Высота дерева $H$ -- это высота корня. Для полного двоичного дерева с $n$ уровнями: $H = n - 1$, на уровне $k$ ровно $2^k$ узлов, всего $2^n - 1$. Вырожденное дерево из $N$ узлов имеет $H = N - 1$ -- это нижний предел эффективности, который балансировка (AVL, красно-чёрное дерево) сводит к $O(\log N)$.