Бинарное дерево

Предпосылки: оценка сложности в O(…), бинарный поиск, рекурсия, дерево (корень, родитель, ребёнок, лист, глубина, высота), стек и очередь (LIFO/FIFO — используются для обходов), ссылки, базовое чтение Ruby (классы, методы, поля объекта).

← Дерево | далее: Двоичное дерево поиска · Куча →

Дерево допускает произвольное число детей у каждого узла. Но многие задачи естественно сводятся к выбору из двух вариантов. Возьмём арифметическое выражение (3 + 5) * 2. У каждого знака операции (+, *) ровно две стороны — то, что слева, и то, что справа. Если представить выражение деревом, где каждый узел — это либо знак операции, либо число, то у каждого знака операции получается ровно два ребёнка: левая сторона и правая сторона. Узел при этом хранит не само поддерево, а ссылку на корень левого ребёнка и ссылку на корень правого — поэтому спуститься от узла к нужной стороне можно за одно обращение по ссылке, за O(1), независимо от размера дерева. Дерево, у которого каждый узел ограничен двумя детьми с фиксированными ролями — левый и правый, — называется бинарным (от латинского binarius — «состоящий из двух»):

class Node
  attr_accessor :value, :left, :right
 
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

Выражение (3 + 5) * 2 в виде бинарного дерева:

Обходы деревьев

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

Поиск в глубину (Depth-First Search, DFS)

Depth — глубина. Идём вглубь, пока можем, потом возвращаемся к ближайшей развилке и спускаемся в ещё не пройденную ветку. Чтобы запомнить развилки, к которым надо вернуться, нужен стек (LIFO: последняя отложенная развилка обрабатывается первой). Стек можно держать явно, а можно положиться на рекурсию: каждый рекурсивный вызов для ребёнка автоматически откладывает возврат к родителю на стек вызовов — это и есть тот же стек, только встроенный в язык.

Для бинарного дерева есть три варианта порядка, и каждый решает свою задачу:

Обход	Порядок для узла	Результат	Когда нужен
Pre-order	узел → левое → правое	*, +, 3, 5, 2	Записать дерево в линейный список, чтобы потом восстановить его по этому списку
In-order	левое → узел → правое	3, +, 5, *, 2	Если узлы упорядочены (левее — меньше), даёт значения по возрастанию
Post-order	левое → правое → узел	3, 5, +, 2, *	Сначала обработать детей, потом родителя: вычислить выражение, удалить дерево

Pre-order: записать и восстановить. Чтобы сохранить дерево в файл или передать его по сети, структуру надо превратить в плоский линейный список значений. Запишем узлы в порядке «сначала сам узел, потом всё левое поддерево, потом всё правое» — и отметим пустые места: там, где у узла нет ребёнка, в список идёт маркер пустоты (скажем, #). Без таких маркеров по одним значениям дерево не восстановить однозначно: список A B подходит и дереву, где B — левый ребёнок A, и дереву, где B — правый. С маркерами обратное чтение однозначно: первое значение — всегда корень; за ним тем же правилом читается левое поддерево (пока не закончится своими маркерами пустоты), потом правое — то есть рекурсивно. Фиксированный порядок «корень раньше детей» плюс маркеры пустоты и дают возможность понять, кто чей родитель.

Post-order: дети раньше родителя. Здесь узел обрабатывается последним, уже после обоих поддеревьев. Это нужно, когда результат для узла зависит от результатов его детей. Вычисление выражения (3 + 5) * 2 — ровно такой случай: чтобы применить *, нужны уже посчитанные значения его левого и правого поддеревьев. Post-order даёт запись 3 5 + 2 *, которую считает простой калькулятор на стеке: число кладётся на стек, знак операции снимает со стека два верхних числа, применяет операцию и кладёт результат обратно. По шагам: положить 3, положить 5, увидеть + → снять 3 и 5, положить 8; положить 2, увидеть * → снять 8 и 2, положить 16. На стеке остаётся ответ. По той же причине «дети раньше родителя» post-order используют, чтобы освободить узлы дерева: узел можно отпустить только после того, как отпущены оба его ребёнка, иначе ссылки на детей будут потеряны вместе с родителем, а сами дети останутся висеть в памяти.

Поиск в ширину (Breadth-First Search, BFS)

Breadth — ширина. Узлы на одной и той же глубине образуют уровень: корень — уровень 0, его дети — уровень 1, и так далее. BFS обрабатывает все узлы текущего уровня, прежде чем спуститься на следующий. Чтобы выдержать этот порядок, нужна очередь (FIFO: узлы выходят в том же порядке, в каком вошли) — посетив узел, кладём в очередь его детей, а сами берём из очереди следующий узел того же уровня. Для дерева выражения результат: *, +, 2, 3, 5 (по уровням сверху вниз).

DFS или BFS: порядок встречи и цена по памяти

Критерий	DFS	BFS
Структура данных	Стек	Очередь
Стратегия	Вглубь до упора	По уровням
Память	O(h), h — высота	O(w), w — ширина

Здесь ширина (w) — число узлов на самом многолюдном уровне; высота (h) — длина пути от корня до самого глубокого листа.

Выбор между ними определяет порядок, в котором узлы встречаются. BFS идёт уровень за уровнем, начиная с корня, поэтому он встречает узлы строго по возрастанию глубины: ни один узел глубины 2 не будет посещён раньше всех узлов глубины 1. Значит, если нужно найти ближайший к корню узел с заданным свойством, BFS наткнётся на него раньше любого более глубокого — первое же совпадение и есть ближайшее. DFS, наоборот, ныряет в одну ветку до самого низа, поэтому он выгоднее, когда искомое, скорее всего, лежит глубоко: незачем перебирать все верхние уровни, если ответ внизу.

Цена у каждого своя — по памяти. DFS в любой момент помнит только путь от корня до текущего узла, и этого пути не больше высоты дерева — O(h). BFS держит в очереди целый уровень, поэтому его расход определяется самым широким уровнем — O(w). Отсюда правило выбора по форме дерева: для узкого и глубокого (h велико, w мало) экономнее BFS, для широкого и неглубокого (w велико, h мало) — DFS.

Высота, форма и стоимость поиска

Обход посещает все узлы, поэтому найти нужное значение перебором стоит O(n) — столько, сколько узлов в дереве. Дерево из миллиона узлов — миллион сравнений на каждый поиск. Чтобы искать быстрее, спускаться надо не по всем узлам, а по одному пути от корня вниз, на каждом шаге отбрасывая целое поддерево. Длина такого пути — это высота дерева, поэтому стоимость поиска по дереву упирается в его высоту, а высота — в форму.

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

Три формы описывают, насколько дерево приблизилось к этому идеалу, по нарастающей строгости:

Полное (full) — у каждого узла либо двое детей, либо ни одного; узлов ровно с одним ребёнком нет. Это запрещает самые расточительные ветвления, но ещё не ограничивает высоту: цепочку из пар можно вытянуть как угодно длинно.

Завершённое (complete) — все уровни заполнены полностью, кроме, возможно, последнего, и последний заполняется слева направо без пропусков. Такая форма гарантирует минимальную высоту: дерево из n узлов имеет высоту ⌊log₂(n)⌋ (⌊ ⌋ — округление вниз). У завершённого дерева есть бонус: раз пропусков нет, узлы можно уложить подряд в массив по уровням и обойтись без ссылок на детей — позицию ребёнка вычисляют из позиции родителя арифметикой. На этом свойстве построена куча.

Совершенное (perfect) — заполнены вообще все уровни, включая последний; ни одного свободного места. Это предельный случай завершённого: при высоте h в нём ровно 2ʰ⁺¹ − 1 узлов.

Низкая высота — половина дела: чтобы поиск шёл по одному пути, на каждом узле нужно знать, в какого из двух детей спускаться. Для этого узлы должны быть упорядочены — например, в левом поддереве значения меньше, в правом больше. Тогда поиск работает как бинарный поиск — деление отсортированного диапазона пополам, O(log n): сравнили значение с узлом и отбросили половину дерева. Это правило размещения значений — и есть инвариант порядка двоичного дерева поиска.

Sources

Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (tree traversals, формы бинарных деревьев, связь высоты и сложности).

← Дерево | далее: Двоичное дерево поиска · Куча →

CS Notes

Explorer

binary-tree