Деревья: BST, AVL, RB, B-tree, Trie, Segment, Fenwick

Дерево — иерархическая структура без циклов, где у каждого узла один родитель (кроме корня) и произвольное число детей. Главная цель сбалансированных деревьев — высота O(log n), что даёт логарифмические операции поиска, вставки и удаления. Эта глава покрывает весь спектр: BST, AVL, Red-Black, B-tree, Trie, Segment Tree, Fenwick — структуры, на которых построены std::map, индексы PostgreSQL, автокомплит, файловые системы и алгоритмы на отрезках.

Когда применять / Мотивация

Задача	Структура
Упорядоченное in-memory хранение, частый поиск + range queries	Red-Black / AVL
Очень частый поиск, редкая модификация	AVL (строже сбалансировано)
Внешняя память, индексы БД, файловые системы	B-tree / B+tree
Автокомплит, словари, префиксный поиск, IP-роутинг	Trie
Range sum/min/max + point updates	Fenwick (если обратимо) или Segment
Range queries + range updates (lazy)	Segment Tree
Версионируемые структуры (snapshot/undo)	Persistent Segment Tree

Реальные применения:

std::map (C++), TreeMap (Java) — Red-Black tree.
Linux CFS scheduler, epoll — Red-Black.
PostgreSQL B-tree index, MySQL InnoDB, MongoDB, NTFS, ext4 — B+tree.
Network routing tables (Patricia/radix trie).
Compiler symbol tables — иногда trie или hash, реже tree.

Идея / Как работает

Binary Search Tree (BST)

Свойство: left subtree < node < right subtree (для всех узлов поддерева, не только прямых детей). In-order обход даёт отсортированный порядок. Поиск/вставка/удаление O(log n) в среднем, но при отсортированном вводе вырождается в связный список с O(n).

AVL (1962)

Каждый узел хранит высоту поддеревьев. Balance factor = height(left) - height(right) ∈ {-1, 0, 1}. При нарушении выполняется одна из 4 ротаций: LL, RR, LR, RL. Высота ≤ 1.44·log₂(n) — самое строгое балансирование.

Правая ротация (LL case):
       x                y
      / \      →       / \
     y   C            A   x
    / \                  / \
   A   B                B   C

Red-Black Tree

Ослабленная балансировка через цвета. Правила:

Каждый узел красный или чёрный.
Корень чёрный.
Все NIL-листья чёрные.
У красного узла оба ребёнка чёрные (нет двух красных подряд).
На любом пути от узла до листьев — одинаковое число чёрных узлов (black-height).

Гарантирует высоту ≤ 2·log₂(n+1) — хуже AVL, но меньше ротаций при модификации. Используется в std::map, TreeMap, Linux CFS.

B-tree / B+tree

Многопутевые деревья для внешней памяти. Узел содержит десятки/сотни ключей (размер = страница диска 4–16 KB). Глубина на миллиардах записей — 3–4 уровня → 3–4 disk seeks. B+tree хранит данные только в листьях (внутренние — лишь ключи навигации), листья связаны в doubly-linked list для эффективного range scan. Это основа индексов PostgreSQL, InnoDB, ext4.

Trie (префиксное дерево)

Узел = Map<char, TrieNode> + флаг isEnd. Поиск/вставка строки длины k — O(k), не зависит от количества строк. Эффективен при общих префиксах, но память: O(alphabet × total_length) в худшем случае. Применения: автокомплит, проверка префиксов, IP-роутинг (бинарный trie по битам), spell-check.

Segment Tree

Дерево над массивом для range queries (sum/min/max/gcd) и point updates за O(log n). Хранится в массиве длины 4n (узел v, дети 2v и 2v+1). С lazy propagation — также range updates за O(log n).

Fenwick Tree (BIT, Binary Indexed Tree)

Компактная альтернатива Segment Tree для обратимых операций (sum, XOR). Массив bit[n+1], каждая ячейка хранит сумму сегмента длины i & -i (lowbit). Префиксная сумма и point update за O(log n). В 2–4 раза быстрее Segment по константе, код в 5 раз короче, но не поддерживает range updates без хитростей и требует обратимой операции.

Реализация

Validate BST (передача границ)

Наивно сравнивать только с прямыми соседями нельзя — BST property глобальное. Пример контрпримера: [5, 1, 6, null, null, 4, 7] — узел 4 в правом поддереве 5, но 4 < 5.

Правильно: рекурсивно передаём диапазон [min, max] для текущего узла.

class TreeNode {
  constructor(
    public val: number,
    public left: TreeNode | null = null,
    public right: TreeNode | null = null,
  ) {}
}

function isValidBST(root: TreeNode | null): boolean {
  function validate(node: TreeNode | null, min: number, max: number): boolean {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val)
        && validate(node.right, node.val, max);
  }
  return validate(root, -Infinity, Infinity);
}

Trie

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) node.children.set(char, new TrieNode());
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }

  search(word: string): boolean {
    const node = this.traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this.traverse(prefix) !== null;
  }

  private traverse(s: string): TrieNode | null {
    let node = this.root;
    for (const char of s) {
      const next = node.children.get(char);
      if (!next) return null;
      node = next;
    }
    return node;
  }
}

Segment Tree (range sum + point update)

class SegmentTree {
  private tree: number[];
  constructor(private arr: number[]) {
    const n = arr.length;
    this.tree = new Array(4 * n).fill(0);
    this.build(1, 0, n - 1);
  }

  private build(v: number, tl: number, tr: number): void {
    if (tl === tr) { this.tree[v] = this.arr[tl]; return; }
    const tm = (tl + tr) >> 1;
    this.build(2 * v, tl, tm);
    this.build(2 * v + 1, tm + 1, tr);
    this.tree[v] = this.tree[2 * v] + this.tree[2 * v + 1];
  }

  query(l: number, r: number): number {
    return this.q(1, 0, this.arr.length - 1, l, r);
  }

  private q(v: number, tl: number, tr: number, l: number, r: number): number {
    if (l > r) return 0;
    if (l === tl && r === tr) return this.tree[v];
    const tm = (tl + tr) >> 1;
    return this.q(2 * v, tl, tm, l, Math.min(r, tm))
         + this.q(2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r);
  }

  update(pos: number, val: number): void {
    this.u(1, 0, this.arr.length - 1, pos, val);
  }

  private u(v: number, tl: number, tr: number, pos: number, val: number): void {
    if (tl === tr) { this.tree[v] = val; return; }
    const tm = (tl + tr) >> 1;
    if (pos <= tm) this.u(2 * v, tl, tm, pos, val);
    else           this.u(2 * v + 1, tm + 1, tr, pos, val);
    this.tree[v] = this.tree[2 * v] + this.tree[2 * v + 1];
  }
}

Fenwick Tree

class Fenwick {
  private bit: number[];
  constructor(n: number) {
    this.bit = new Array(n + 1).fill(0);
  }
  // Префиксная сумма [0..i]
  prefix(i: number): number {
    let sum = 0;
    for (i++; i > 0; i -= i & -i) sum += this.bit[i];
    return sum;
  }
  // Прибавить delta к позиции i
  update(i: number, delta: number): void {
    for (i++; i < this.bit.length; i += i & -i) this.bit[i] += delta;
  }
  // Сумма [l..r]
  range(l: number, r: number): number {
    return this.prefix(r) - (l > 0 ? this.prefix(l - 1) : 0);
  }
}

Трассировка isValidBST

Корректное BST [5, 3, 7, 1, 4, 6, 8]:

        5
       / \
      3   7
     / \ / \
    1  4 6  8

validate(5, -∞, +∞)        ✓
  validate(3, -∞, 5)       ✓
    validate(1, -∞, 3)     ✓
    validate(4, 3, 5)      ✓
  validate(7, 5, +∞)       ✓
    validate(6, 5, 7)      ✓
    validate(8, 7, +∞)     ✓
→ true

Невалидное [5, 1, 6, null, null, 4, 7] (узел 4 в правом поддереве 5):

        5
       / \
      1   6
         / \
        4   7

validate(5, -∞, +∞)        ✓
  validate(1, -∞, 5)       ✓
  validate(6, 5, +∞)       ✓
    validate(4, 5, 6)      ✗  (4 ≤ 5 — нарушение)
→ false

Сложность

Структура	Поиск	Вставка	Память	Применение
BST (unbalanced)	O(log n) avg / O(n) worst	O(log n) avg / O(n) worst	O(n)	Простые задачи
AVL	O(log n)	O(log n)	O(n)	Read-heavy
Red-Black	O(log n)	O(log n)	O(n)	Общий случай (`std::map`)
B-tree / B+tree	O(log n)	O(log n)	O(n)	Диски, БД
Trie	O(k)	O(k)	O(alphabet · n)	Строки, префиксы
Segment Tree	O(log n)	O(log n)	O(4n)	Range queries + updates
Fenwick (BIT)	O(log n)	O(log n)	O(n)	Prefix sum, point update

isValidBST: время O(n) — каждый узел один раз; память O(h) — стек рекурсии = высота (O(log n) сбалансированное, O(n) вырожденное).

Типичные ошибки и подводные камни

BST с дубликатами: стандартное определение строгое (left < node < right). При допустимости дубликатов — определите консистентно (всегда влево или всегда вправо).
Validate BST через сравнение с детьми: типичная ошибка — проверка left.val < node.val < right.val локально не достаточна (см. контрпример выше). Передавайте границы.
Integer overflow в min/max: используйте Infinity/-Infinity в JS вместо Number.MIN_SAFE_INTEGER.
AVL ротации: 4 случая (LL, RR, LR, RL). LR = левая на детеноке, потом правая на узле. Путаница в направлении — частая ошибка на собесе.
Удаление из BST: 3 случая. Лист — просто удалить. Один ребёнок — заменить узел этим ребёнком. Два ребёнка — заменить значением inorder successor (минимум правого поддерева), затем удалить successor.
Trie память: при больших алфавитах и коротких строках overhead огромен. Используйте compressed trie (Patricia/radix tree) или Map вместо массива из 26 ячеек.
Segment Tree размер: 4n, не 2n (нужно округление до степени 2 + запас на нечётные разбиения).
Fenwick 0-based vs 1-based: классическая реализация 1-based, но удобно скрыть через i++ в API.
B-tree m order: означает максимум m детей у узла, т.е. m-1 ключей. Часто путают.

Follow-up вопросы интервьюера

Lowest Common Ancestor в BST. Используем порядок: если оба узла < корня → влево, оба > корня → вправо, иначе текущий узел — LCA. O(h).
Lowest Common Ancestor в произвольном дереве. Рекурсивный поиск: возвращает узел, если в поддереве нашли любого из двух. Если оба ребёнка вернули non-null — текущий узел LCA.
K-th Smallest in BST. In-order traversal до k-го элемента — O(k). Оптимизация: храните размер поддерева в каждом узле → O(h).
Range Sum Query Mutable. Segment Tree или Fenwick. Fenwick проще и быстрее для суммы.
Trie с wildcard (. как любой символ). DFS с перебором всех детей при .. O(n·m) worst case.
Persistent Segment Tree. Каждое обновление создаёт новые узлы только на пути обновления, остальные shared. O(log n) памяти/времени на версию. Используется в version control, range queries по historic snapshots.
B+tree vs Red-Black для индексов БД. B+tree оптимизирован для дисковых операций (широкие узлы = меньше seeks, листья в списке = быстрый range scan). RB-tree — для in-memory с произвольным доступом.
Serialize/Deserialize Binary Tree. Pre-order DFS с маркером null или BFS уровнями.
Diameter of Binary Tree. Для каждого узла = height(left) + height(right) + 1. Возвращаем глубину наверх, обновляем глобальный максимум.

Чеклист на собес

Знаю свойство BST глобально (через границы).
Помню 4 ротации AVL и 5 правил Red-Black.
Понимаю, почему B+tree используется в БД (диск, range scan).
Знаю Trie для префиксных задач, понимаю трейд-офф памяти.
Различаю Segment vs Fenwick (универсальность vs скорость).
Помню 4n для размера Segment Tree.
Знаю удаление из BST (3 случая, inorder successor).
Понимаю in-order = sorted порядок для BST.
Помню lazy propagation для range updates в Segment.