tree

Дерево

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

← Граф | Бинарное дерево →

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

Дерево как ограниченный граф

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

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

Дерево само по себе не указывает, откуда смотреть на иерархию. Можно выделить одну вершину как точку отсчёта — корень (root). До этого все вершины равноправны (такое дерево называют свободным, free tree); после выделения корня появляется направление сверху вниз, от корня к самым нижним вершинам. В файловой системе корень — самый верхний каталог, каждая папка и файл — вершина дерева (вершину дерева чаще называют узлом). Направление задаёт роли: вершина ближе к корню — родитель, вершина под ней — её ребёнок.

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

Несколько ролей вершин, которые понадобятся дальше. Родитель (parent) — вершина, стоящая прямо над данной по пути к корню; ребёнок (child) — вершина прямо под ней. Лист (leaf) — узел без детей (в файловой системе — файл или пустая папка). Внутренняя вершина — узел с детьми (папка с содержимым).

Две меры расстояния по дереву считают рёбрами на пути. Глубина узла — сколько рёбер на пути от корня до этого узла. Для каталога /home/alice/code корень / находится на глубине 0, home — 1, alice — 2, code — 3: три ребра вниз от корня. Высота дерева — глубина самого нижнего листа, то есть длина самого длинного пути от корня вниз.

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

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

Когда дерево обходят сверху вниз, от корня к нижним узлам, в каждом узле нужны ссылки на его детей. Так работает файловый менеджер, рисующий дерево папок: он начинает с корня и спускается. Тогда узел хранит своё значение и список ссылок на детей:

class TreeNode
  attr_accessor :value, :children
 
  def initialize(value)
    @value = value
    @children = []   # ссылки на дочерние узлы
  end
end

Когда же нужно подниматься от узла вверх, к корню, в каждом узле достаточно одной ссылки — на родителя. Так строят «хлебные крошки» (breadcrumbs — навигационную цепочку вида home > alice > code) от текущей папки до корня; так же git log --graph идёт от коммита к его родителю-предку. Здесь дерево удобно задать отображением «узел → его родитель», где у корня родителя нет (nil):

parent = {
  home:  nil,    # корень
  alice: :home,
  bob:   :home,
  code:  :alice
}

Ни один из вариантов не «правильнее» другого: список детей дёшев для спуска и бесполезен для подъёма, ссылка на родителя — наоборот. Выбор фиксирует, какие обходы будут быстрыми.

Операции

Добавление ребёнка — O(1): достаточно дописать новую ссылку в список детей узла. Удаление целого поддерева (узла со всеми его потомками) тоже O(1), если ссылка на этот узел уже есть: разрываешь единственное ребро от родителя — и весь кусок ниже сразу отрезан от дерева, ведь добраться до потомков можно было только через этого родителя. Реальная цена возникает, когда память отрезанных узлов нужно вернуть: тогда их приходится обойти, и удаление становится O(k) по числу узлов в поддереве k.

Обход всех узлов — O(n) по числу узлов 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).

---

← Граф | Бинарное дерево →