Модуль 21 ⏱ ~18 мин чтения 📐 2 Mermaid диаграмм

1. Теория. DP на деревьях

«Дерево познается по плодам его, а корень черпает силу из скрытой глубины ветвей».
— Брайан Керниган

Переход от динамического программирования на линейных массивах и матрицах к DP на деревьях (Tree DP) — это качественный скачок в абстракции. На числовой оси или координатной сетке мы привыкли итерироваться простыми циклами, заполняя ячейки в предсказуемом порядке (Bottom-Up). В дереве линейный порядок невозможен: дерево — это иерархический направленный ациклический граф (DAG).

Единственный способ корректно вычислить состояние родительского узла — сначала получить оптимальные ответы для всех его поддеревьев. Поэтому динамическое программирование на деревьях всегда реализуется через обход в глубину в обратном порядке (Post-Order DFS): мы спускаемся до листьев (базовые случаи DP) и вычисляем переходы снизу вверх на этапе всплытия из рекурсии.

1. Архитектура состояний: Конечный автомат на узле

В задачах на деревьях состояние поддерева редко описывается единственным скалярным числом. Поскольку каждый узел топологически связан со своим родителем, решение, принятое в текущем узле (например, «включить этот узел в выборку»), накладывает жесткие ограничения на допустимые действия родителя.

Отсюда возникает паттерн конечного автомата на узле (FSM on Tree Node). Рекурсивная функция обхода возвращает кортеж состояний:

  1. take: оптимальный результат для поддерева при условии, что текущий узел включен (захвачен).
  2. skip: оптимальный результат для поддерева при условии, что текущий узел пропущен (свободен).
flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    Node["Текущий узел (Node)"]:::entry --> L["Левый потомок (Left)<br/>DFS возвращает: (take, skip)"]:::process
    Node --> R["Правый потомок (Right)<br/>DFS возвращает: (take, skip)"]:::process

    L & R --> Agg["Агрегация состояний потомков"]:::warning

    Agg --> CalcTake["take = Node.Val + L.skip + R.skip<br/>(Если берем узел, дети строго пропускаются)"]:::success
    Agg --> CalcSkip["skip = max(L.take, L.skip) + max(R.take, R.skip)<br/>(Если пропускаем узел, дети свободны)"]:::success

    CalcTake & CalcSkip --> Ret["Возврат (take, skip) родителю"]:::entry

Родительский узел, принимая пару (take, skip) от левого и правого потомков, агрегирует их за $O(1)$ операций и передает свой кортеж выше по дереву. В корне дерева глобальным ответом становится $\max(\text{rootTake}, \text{rootSkip})$.

2. Under the Hood: Стек горутины, отсутствие TCO и morestack

В языках с оптимизацией хвостовой рекурсии (TCO — Tail Call Optimization, таких как Haskell или компиляторы Scheme) глубокая рекурсия компилируется в плоский цикл.
В Go компилятор намеренно не выполняет TCO. Каждый рекурсивный вызов функции создает полноценный стек-фрейм (Stack Frame).

  1. Размер начального стека: Рантайм Go выделяет новой горутине стек размером всего 2 КБ – 4 КБ.
  2. Несбалансированные деревья: Если дерево вырождается в связный список глубиной $N = 100\,000$, глубина рекурсии достигнет 100 000 кадров.
  3. Механизм runtime.morestack: Когда стек переполняется, рантайм вызывает процедуру расширения:
    • Аллоцирует в куче новый блок памяти вдвое большего размера.
    • Копирует все стек-фреймы на новое место.
    • Корректирует указатели внутри кадров.

При миллионах рекурсивных шагов постоянный morestack порождает огромные задержки (Tail Latency Spikes). Для потенциально глубоких деревьев в продакшене Senior-разработчик реализует итеративный DFS с явным стеком []*TreeNode в куче.

3. Mechanical Sympathy: Pointer Chasing и почему СУБД отвергли BST

Бинарные деревья в памяти представляются через указатели:

Go 
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Это фундаментальная проблема для современных процессоров, известная как Pointer Chasing (погоня за указателями):

  • Каждый узел TreeNode выделяется аллокатором Go в произвольном фрагменте кучи.
  • Указатели Left и Right ссылаются на непредсказуемые адреса оперативной памяти.
  • При переходе node = node.Left процессор не может предсказать шаблон доступа. Аппаратный префетчер бессилен.
  • Каждый переход к дочернему узлу влечет за собой L1/L2 Cache Miss с ожиданием подгрузки строки памяти из RAM в течение 50–100 наносекунд.
flowchart LR
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc

    subgraph HeapMemory["Разрозненная куча (Pointer Chasing)"]
        N1["Node A (0x10A0)"]:::error -. "Cache Miss (~70 нс)" .-> N2["Node B (0x8F40)"]:::error
        N2 -. "Cache Miss (~70 нс)" .-> N3["Node C (0x0210)"]:::error
    end

    subgraph BTree["B-Tree Page (Непрерывный блок 4/8/16 КБ)"]
        K["[ Key 1 | Key 2 | Key 3 ... Key 100 ]"]:::success
    end

4. Идиоматичный Go: Множественный возврат в регистрах CPU (Zero-Alloc)

В Java или Python возврат двух значений из функции требует создания объекта-обертки Pair или кортежа, что порождает паразитные аллокации в куче на каждом узле дерева.

В Go множественные возвращаемые значения — часть сигнатуры функции. Благодаря внедрению ABIInternal (Register-based Calling Convention) в современных компиляторах Go:

  • Первое значение take возвращается непосредственно в регистре RAX (или R0 на ARM64).
  • Второе значение skip возвращается в регистре RDX (или R1 на ARM64).
Go 
// Идиоматичный шаблон Tree DP в Go: 0 аллокаций памяти!
func dfs(node *TreeNode) (take, skip int) {
    if node == nil {
        return 0, 0
    }

    leftTake, leftSkip := dfs(node.Left)
    rightTake, rightSkip := dfs(node.Right)

    // Переходы FSM:
    take = node.Val + leftSkip + rightSkip
    skip = max(leftTake, leftSkip) + max(rightTake, rightSkip) // Go 1.21+ встроенный max()

    return take, skip
}

Передача состояний происходит на уровне регистров CPU со скоростью 1 такт на операцию, создавая абсолютный ноль нагрузки на Garbage Collector.

5. System Design: Иерархические квоты и MapReduce

В распределенных файловых системах (Ceph, HDFS, Google Colossus) и системах разграничения прав (IAM, RBAC) структура данных представляет собой гигантское дерево каталогов или организационных юнитов (Org Units).

Расчет агрегированных метрик:

  • Подсчет суммарного дискового пространства каталога (du -sh).
  • Определение максимальной квоты CPU/RAM для дочерних неймспейсов в Kubernetes.
  • Применение политик безопасности с наследованием (Inherited Permissions).

Все эти задачи реализуются по модели Tree DP. В распределенной среде Post-order DFS распараллеливается: листья вычисляются параллельными воркерами (Map-фаза), а родительские узлы объединяют результаты (Reduce-фаза), формируя иерархический пайплайн агрегации данных.

6. Вопросы для собеседования

Итог

  1. Post-order — это Bottom-Up: DP на деревьях вычисляется на этапе возврата из рекурсии снизу вверх.
  2. FSM на узле: Возврат кортежа состояний (take, skip) решает конфликты ограничений между предками и потомками.
  3. Регистровый Zero-Alloc: Множественный возврат в Go транслируется в регистры CPU без выделения памяти в куче.
  4. Mechanical Sympathy: Помните о проблеме Pointer Chasing при обходе указателей и рисках роста стека morestack.

В следующей лекции мы распространим парадигму DP с ациклических деревьев на общие графы, где возникают циклы и требуется топологическая сортировка: 2. DP на графах.