CS Notes

tree

3 min read

Дерево

Предпосылки: оценка сложности в O(…), граф (вершины, рёбра, путь, цикл, связность).

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

Определение

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

Ключевое свойство: количество рёбер = количество вершин − 1 (E = V − 1). Добавишь ещё одно ребро — появится цикл. Уберёшь одно — граф распадётся. На практике это даёт быструю проверку: если в связном графе E = V − 1, это дерево; если E ≥ V — есть циклы.

«Просто дерево» (свободное дерево, free tree) — граф без выделенной вершины. Корневое дерево — с выделенным корнем (root). Корень задаёт направление: от корня к листьям. В файловой системе корень — /, каждая папка — узел, файлы — листья. После выделения корня у каждого узла появляются роли «родитель» и «ребёнок».

Терминология корневого дерева

Родитель (parent) — вершина на уровень выше. Ребёнок (child) — вершина на уровень ниже. Лист (leaf) — вершина без детей (в файловой системе — файл или пустая папка). Внутренняя вершина — вершина с детьми (папка с содержимым). Глубина узла — длина пути от корня до узла: /home/alice/code имеет глубину 3. Высота дерева — длина пути от корня до самого глубокого листа.

Хранение корневого дерева

Для работы с деревом нужно представить связи «родитель — ребёнок» в памяти. Выбор зависит от того, какие операции важнее.

Список детей — каждый узел хранит ссылки на своих детей:

class TreeNode
  attr_accessor :value, :children
 
  def initialize(value)
    @value = value
    @children = []
  end
end

Указатель на родителя — каждый узел хранит ссылку на родителя:

parent = {
  А: nil,   # корень
  Б: :А,
  В: :А,
  Г: :В
}

Какой вариант нужен — зависит от задачи. Рендеринг дерева папок в файловом менеджере — обход сверху вниз, от корня к листьям: нужен список детей. Построение «хлебных крошек» (breadcrumbs) от текущего файла до корня — подъём вверх: нужен указатель на родителя. git log --graph строит путь от коммита к его предкам — тоже указатель на родителя.

Операции

Добавление ребёнка — O(1) (дописать в список children). Удаление поддерева — O(1) если есть указатель на узел (отцепить от родителя), но O(k) если нужно освободить память k удалённых узлов. Обход всех узлов — O(n). Поиск по значению — O(n): без дополнительных ограничений на структуру нет способа сузить область поиска. В файловой системе с 100 000 файлов поиск файла по имени без индекса означает обход всех 100 000 узлов.

Если ограничить число детей до двух, у каждого узла появляются фиксированные роли: левый и правый ребёнок. Это бинарное дерево: Бинарное дерево.

Sources

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (trees as connected acyclic graphs, свойства E = V − 1).

Sources

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (trees as connected acyclic graphs, свойства E = V − 1).

Graph View

Backlinks