CS Notes

binary-tree

4 min read

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

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

Дерево допускает произвольное число детей у каждого узла. Но многие задачи естественно сводятся к выбору из двух вариантов. Арифметическое выражение (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 в виде бинарного дерева:

       *
      / \
     +   2
    / \
   3   5

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

Дерево хранит данные, но чтобы эти данные использовать — вычислить результат выражения, сериализовать дерево для передачи по сети, собрать все значения — нужно обойти узлы. Для деревьев хватает очереди; для графов к этому почти всегда добавляется visited, чтобы не зациклиться на циклах.

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

Depth — глубина. Идём вглубь, пока можем, потом возвращаемся. Использует стек (или рекурсию — call stack).

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

       *
      / \
     +   2
    / \
   3   5
ОбходПорядок для узлаРезультатЗадача
Pre-orderузел → левое → правое*, +, 3, 5, 2Сериализация: первый элемент — корень, дерево восстанавливается рекурсивно
In-orderлевое → узел → правое3, +, 5, *, 2Для дерева поиска даёт элементы в отсортированном порядке
Post-orderлевое → правое → узел3, 5, +, 2, *Стековый калькулятор: операнды кладутся на стек, оператор снимает два верхних и вычисляет результат

Pre-order используют для сериализации дерева: если записать узлы в порядке «корень, левое, правое», при чтении первый элемент — всегда корень, и дерево восстанавливается рекурсивно. Post-order обрабатывает детей до родителя — это нужно для удаления дерева (нельзя удалить узел, пока не удалены его дети), вычисления размера поддеревьев и стековых вычислителей: запись 3 5 + 2 * обрабатывается стеком как «положить 3, положить 5, применить + → 8, положить 2, применить * → 16».

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

Breadth — ширина. Обрабатываем все узлы на текущем уровне, прежде чем спускаться глубже. Использует очередь (FIFO). Для дерева выражения результат: *, +, 2, 3, 5 (по уровням).

Когда что использовать

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

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

Формы бинарного дерева

Обходы работают на любом бинарном дереве, но эффективность операций зависит от формы — насколько дерево заполнено и сбалансировано.

Полное (full) бинарное дерево — каждый узел имеет либо 0, либо 2 детей (нет узлов с одним ребёнком).

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

Совершенное (perfect) бинарное дерево — все уровни полностью заполнены. Содержит ровно 2ʰ⁺¹ − 1 узлов при высоте h.

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

Sources

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

Sources

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

Graph View

Backlinks