1. Деревья и обходы

До сих пор мы рассматривали линейные структуры данных: 1. Массивы и динамические массивы и 3. Связные списки. В них каждый элемент имеет строго максимум одного предшественника и одного непосредственного последователя. Такая геометрия идеальна для хранения плоских списков и очередей, но окружающий физический мир и большинство архитектурных задач иерархичны по своей природе.

Файловые системы операционных систем, DOM-дерево в браузерах, таблицы маршрутизации URL в современных веб-фреймворках (например, Radix tree в echo или gin), индексы высоконагруженных СУБД — всё это опирается на фундаментальную нелинейную структуру данных: Дерево (Tree).

Анатомия и терминология

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

• Корень (Root): Самый верхний узел иерархии, не имеющий родительского узла.
• Узел (Node): Базовая элементарная единица дерева, содержащая полезную нагрузку (значение) и ссылки на дочерние узлы.
• Ребро (Edge): Направленная связь между родительским и дочерним узлами.
• Родитель / Ребенок (Parent / Child): Отношение субординации. Узел, из которого исходит ребро — родитель; узел, в который ребро входит — ребенок.
• Лист (Leaf): Терминальный узел дерева, не имеющий ни одного потомка.
• Высота (Height) дерева: Максимальное число ребер на пути от корня до самого удаленного листа.
• Глубина (Depth) узла: Длина пути (количество ребер) от корня до данного конкретного узла.

flowchart TD
    Root["Корень (Root)<br/>Глубина: 0"] -->|"Ребро"| L1["Узел (Child)<br/>Глубина: 1"]
    Root -->|"Ребро"| R1["Узел (Child)<br/>Глубина: 1"]

    L1 --> LL1["Лист (Leaf)<br/>Глубина: 2"]
    L1 --> LR1["Лист (Leaf)<br/>Глубина: 2"]
    R1 --> RL1["Лист (Leaf)<br/>Глубина: 2"]

    classDef rootNode fill:#1e293b,stroke:#38bdf8,stroke-width:2px,color:#f8fafc;
    classDef innerNode fill:#1e3a8a,stroke:#60a5fa,stroke-width:1.5px,color:#f8fafc;
    classDef leafNode fill:#14532d,stroke:#10b981,stroke-width:1.5px,color:#f8fafc;

    class Root rootNode;
    class L1,R1 innerNode;
    class LL1,LR1,RL1 leafNode;
  

Mechanical Sympathy: Деревья и аппаратное железо

С точки зрения архитектуры современного процессора, наивное дерево на указателях — это наихудший сценарий для подсистемы памяти.

В непрерывных массивах мы наслаждались идеальной пространственной локальностью (Spatial Locality) и предсказуемой работой аппаратного Prefetcher-а, который автоматически подтягивал данные в L1-кэш целыми линиями по 64 байта. В классическом же дереве каждый узел создается независимой аллокацией в куче (Heap). В результате узлы оказываются хаотично разбросаны по виртуальному адресному пространству.

Каждый шаг спуска по дереву от родителя к ребенку (node.Left или node.Right) превращается в Pointer Chasing (погоню за указателями). Процессор не в состоянии предугадать адрес следующего узла и вынужден простаивать сотни тактов, ожидая доставку данных из медленной RAM через контроллер шины памяти.

Представление дерева в Go

В языке Go деревья конструируются через структуры с рекурсивными типизированными указателями. В алгоритмической практике чаще всего используется Бинарное дерево (у каждого узла не более двух потомков — Left и Right):

package main

// Node представляет узел бинарного дерева с generic-типом T
type Node[T any] struct {
    Value T
    Left  *Node[T]
    Right *Node[T]
}

Алгоритмы обхода (Traversals)

Поскольку дерево представляет собой ветвящуюся структуру, мы не можем просто пройти по нему элементарным циклом for i := 0; i < len; i++. Нам требуются специализированные дисциплины навигации. Они подразделяются на два фундаментальных класса: Поиск в глубину (DFS) и Поиск в ширину (BFS).

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

Алгоритм DFS стремится спуститься от корня как можно глубже вдоль ветви, пока не упрется в лист, и лишь затем откатывается назад для исследования соседних поддеревьев. В основе DFS фундаментально лежит дисциплина Стек (LIFO) — либо явная структура данных, либо стек вызовов функций (Call Stack).

Существует три канонических порядка обхода бинарного дерева:

A. Прямой обход (Pre-order: Root -> Left -> Right)

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

B. Симметричный обход (In-order: Left -> Root -> Right)

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

C. Обратный обход (Post-order: Left -> Right -> Root)

Сначала полностью обрабатываются все дочерние узлы (слева и справа), а родительский узел обрабатывается в самую последнюю очередь.
Практическое применение: Освобождение памяти / удаление дерева (в языках без автоматического GC требуется освободить всех потомков до уничтожения родителя), вычисление размера каталога на диске (необходимо сложить размеры всех вложенных папок, прежде чем вычислить размер родительской директории).

flowchart TD
    subgraph Tree["Порядок обхода DFS"]
        N1["1. Node (A)"]
        N2["2. Left (B)"]
        N3["3. Right (C)"]
        N1 --> N2
        N1 --> N3
    end

    classDef tNode fill:#1e293b,stroke:#38bdf8,stroke-width:1.5px,color:#f8fafc;
    class N1,N2,N3 tNode;
  

Реализация DFS на Go (Рекурсивно)

Рекурсивный подход — наиболее лаконичный и естественный способ навигации по дереву:

// PreOrder выполняет прямой обход дерева: Корень -> Лево -> Право
func PreOrder[T any](node *Node[T], action func(T)) {
    if node == nil {
        return
    }
    action(node.Value)          // 1. Обработка текущего узла
    PreOrder(node.Left, action)  // 2. Спуск в левое поддерево
    PreOrder(node.Right, action) // 3. Спуск в правое поддерево
}

// InOrder выполняет симметричный обход: Лево -> Корень -> Право
func InOrder[T any](node *Node[T], action func(T)) {
    if node == nil {
        return
    }
    InOrder(node.Left, action)
    action(node.Value)
    InOrder(node.Right, action)
}

// PostOrder выполняет обратный обход: Лево -> Право -> Корень
func PostOrder[T any](node *Node[T], action func(T)) {
    if node == nil {
        return
    }
    PostOrder(node.Left, action)
    PostOrder(node.Right, action)
    action(node.Value)
}

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

В отличие от DFS, алгоритм BFS исследует пространство дерева строго горизонтальными слоями — по уровням (Level-order): сначала исследуется корень, затем все непосредственные потомки (уровень 1), затем все внуки (уровень 2) и так далее.

Рекурсия для BFS неприменима, поскольку стек вызовов естественным образом углубляет поиск. Архитектурным сердцем BFS всегда является структура данных Очередь (Queue) с дисциплиной FIFO («первым пришел — первым ушел»). См. подробности в 5. Очередь.

Механика работы BFS:

1. Помещаем корневой узел в очередь.
2. Пока очередь содержит элементы:
   • Извлекаем узел из головы очереди (Dequeue).
   • Обрабатываем его полезную нагрузку.
   • Если у узла есть левый потомок — добавляем его в хвост очереди (Enqueue).
   • Если у узла есть правый потомок — добавляем его в хвост очереди (Enqueue).

flowchart TD
    N1["Уровень 0: Корень [1]"] --> N2["Уровень 1: Слева [2]"]
    N1 --> N3["Уровень 1: Справа [3]"]

    N2 --> N4["Уровень 2: [4]"]
    N2 --> N5["Уровень 2: [5]"]
    N3 --> N6["Уровень 2: [6]"]

    classDef lvl0 fill:#1e293b,stroke:#38bdf8,stroke-width:2px,color:#f8fafc;
    classDef lvl1 fill:#1e3a8a,stroke:#60a5fa,stroke-width:1.5px,color:#f8fafc;
    classDef lvl2 fill:#14532d,stroke:#10b981,stroke-width:1.5px,color:#f8fafc;

    class N1 lvl0;
    class N2,N3 lvl1;
    class N4,N5,N6 lvl2;
  

Реализация BFS на Go

Для небольших деревьев в демонстрационных целях допустимо использовать встроенный слайс Go в роли очереди:

func BFS[T any](root *Node[T], action func(T)) {
    if root == nil {
        return
    }

    // Инициализируем очередь корневым элементом
    queue := []*Node[T]{root}

    for len(queue) > 0 {
        // Извлекаем элемент из начала очереди (Dequeue)
        current := queue[0]
        queue = queue[1:] // Внимание: в highload-коде используйте кольцевой буфер во избежание утечек!

        // Выполняем пользовательскую обработку
        action(current.Value)

        // Добавляем дочерние узлы в конец очереди (Enqueue)
        if current.Left != nil {
            queue = append(queue, current.Left)
        }
        if current.Right != nil {
            queue = append(queue, current.Right)
        }
    }
}

Сферы применения BFS: Нахождение кратчайшего пути в невзвешенных графах, поуровневая визуализация и форматирование деревьев, сериализация иерархических структур с контролем ширины связей.

Итог

1. Деревья решают фундаментальную задачу представления иерархических отношений. Базовый строительный блок — узел (Node), удерживающий ссылки на своих потомков.
2. С позиций Mechanical Sympathy, классические деревья на независимых узлах кучи создают заметную нагрузку на сборщик мусора (GC Pressure) и порождают множественные промахи кэша (Cache Misses) из-за погони за указателями (Pointer Chasing).
3. DFS (Поиск в глубину) реализуется через рекурсию либо явный Стек. Классифицируется на прямой (Pre-order), симметричный (In-order) и обратный (Post-order) обходы.
4. BFS (Поиск в ширину) методично обходит узлы по слоям (уровням) и строго требует применения структуры Очередь (FIFO).
5. Рантайм Go нивелирует риск классического переполнения стека благодаря динамическим масштабируемым стекам (runtime.morestack), однако цена постоянного копирования памяти ощутима в CPU-профилях.

Освоив анатомию деревьев и алгоритмы навигации по ним, мы переходим к исследованию самой знаменитой и востребованной их разновидности в компьютерных науках — структуре, лежащей в основе эффективного поиска и сортировки. В следующей статье: 2. Бинарное дерево.