Деревья

Настало время познакомиться с самыми часто встречающимися нелинейными структурами данных — деревьями.

Деревья

Дерево — конечное множество узлов $T$ , в котором есть один выделенный узел $\code{root}$ — корень, а остальные узлы разделены на $m \ge 0$ непересекающихся множеств $T_1, T_2, \dotsc, T_m$ , которые тоже являются деревьями.

T \without \{\code{root}\} = \bigdjunion_{i=1}^m T_i

Эти деревья $T_1, T_2, \dotsc, T_m$ называются поддеревьями корня $\code{root}$ , а их количество $m$ — степенью корня. Обозначается степень корня $\deg \code{root} \defeq m$ .

Несмотря на однонаправленность определения, все у нас хорошо. Степень существует для любых узлов, и определяется как количество поддеревьев этого узла.

Здесь много несостыковок со школьным определением дерева «дерево — связный граф без циклов». В школьном определении нет выделенного корня, да и степень вершины на $1$ больше... Пугаться не стоит, просто это другие деревья. Школьные деревья в нашем мире тоже есть, просто называются свободными деревьями.

Из нашего определения выстраивается чёткая иерархия деревьев, их поддеревьев, поддеревьев их поддеревьев и т. д. Неимоверно большой соблазн взять и нарисовать линии, соединяющие корень с поддеревьями (или с корнями поддеревьев, что одно и то же). Тем самым иерархия показана еще и графически.

Теперь мы явно задали наше дерево $T$ как граф, врешины которого — все узлы $T$ , а ребро между двумя узлами рисуется, если один из этих узлов является корнем поддерева второго узла.

Типы узлов деревьев

Если степень узла равна $0$ , то этот узел называется листом (leaf) или терминальным узлом (terminal node).

Если степень узла больше $0$ , то этот узел называется внутренним узлом или узлом ветвления (branch node).

\deg v = 0 \defequiv \text{узел}~ v ~\text{лист} \qquad \deg v > 0 \defequiv \text{узел}~ v ~\text{внутренний}

Величины

Пусть $v$ — узел дерева $T$ .

Глубиной вершины $v$ называется количество рёбер на пути от корня дерева $T$ до вершины $v$ .

\depth v \defeq \text{длина пути от}~ \root T ~\text{до}~ v

Глубина корня всегда $0$ , то есть $\depth (\root T) = 0$ .

В некоторой литературе часто упоминается понятие уровень вершины — величина, на $1$ большая глубины вершины. Мы такое понятие использовать не будем.

Деревья в памяти компьютера

Есть два принципиально разных способа хранения деревьев в компьютере: безперспективный и малоперспективный.

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

Можно пройтись по нашей выстроенной иерархии снизу вверх, храня связь между ребёнком и родителем. Тогда в каждом узле просто появится указатель на родителя. Если указатель у какой-то вершины на родителя пустой, значит родителя нет и эта вершина — глобальный корень.

Теперь мы можем подниматься вверх по иерархии, просто проходя по ссылке на родителя. Осталось научится спускаться вниз. Для этого нам нужно хранить список из детей. Я пока не накладываю никаких ограничений на этот список: это может быть динамический массив с доступом на время $O(1)$ , это может быть двусвязный циклический список, обеспечивающий быстрое добавление и удаление детей, или какая-то из комбинация типа блочного списка.

struct node:
    node parent
    list[node] children
    some additional data

У нас в любом случае будет оверхед на этот самый список.