Деревья
Формально дерево (tree) определяется как конечное множество \(T\) одного или более узлов со следующими свойствами:
a) существует один выделенный узел, а именно — корень (root) данного дерева \(T\);
b) остальные узлы (за исключением корня) распределены среди \(m \geq 0\) непересекающихся множеств \(T_{1},... , T_{m}\), и каждое из этих множеств, в свою очередь, является деревом; деревья \(T_{1},... , T_{m}\) называются поддеревьями (subtrees) данного корня.
Из этого определения следует, что каждый узел дерева является корнем некоторого поддерева данного дерева. Количество поддеревьев узла называется степенью (degree) этого узла. Узел со степенью нуль называется концевым узлом (terminal node) или листом (leaf). Неконцевой узел называется узлом ветвления (branch node). Уровень (level) узла по отношению к дереву T определяется рекурсивно следующим образом. Уровень корня дерева T равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T, содержащего данный узел.
Если в п. (b) данного выше определения имеет значение относительный порядок поддеревьев \(T_{1},... , T_{m}\), то дерево является упорядоченным (ordered tree). Если в упорядоченном дереве \(m \geq 2\), то имеет смысл назвать поддерево \(T_{2}\) вторым поддеревом данного корня и т.д. Упорядоченные деревья иногда также называются плоскими деревьями (plane trees), поскольку при их упорядочении имеет значение способ размещения дерева на плоскости. Если не считать различными два дерева, которые отличаются только относительным порядком поддеревьев узлов, то дерево называется ориентированным (oriented), поскольку при этом имеет значение только относительная ориентация узлов, а не их порядок.
Лес (forest) — это множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев. Тогда еще одна формулировка п. (b) в данном выше определении дерева могла бы выглядеть так: узлы дерева при условии исключения корня образуют лес.
Стандартная терминология древовидных структур происходит от генеалогических деревьев типа "родовой схемы" (наследники человека). Каждый узел называется родителем (parent) корней его поддеревьев, а сами корни называются братьями-сестрами (siblings), а также детьми (children) своего родителя. Корень всего дерева не имеет родителя.
Для обозначения родства, которое может простираться на несколько уровней дерева, будут использоваться термины "предок" (ancestor) и "потомок" (descendant).
Одним из преимуществ древовидного представления информации является удобство анализа. Когда мы помещаем информацию в древовидную структуру, определенные отношения можно увидеть гораздо быстрее, чем в любом текстовом представлении. Кроме того, деревья обладают определенными свойствами, которые позволяют осуществлять эффективный синтез информации.
Ссылки: