Понятие корневого дерева

В теории графов конечное корневое дерево формально определяется как непустое конечное множество узлов Т, таких что: существует один, специально выделенный узел, называемый корнем, а остальные узлы образуют попарно непересекающиеся подмножества множества узлов Т, каждое из которых является деревом. Это определение позволяет интерпретировать корневое дерево как рекурсивный объект, который содержит сам себя и определяется с помощью себя самого (т. е. дерево определяется в терминах дерева). Определение корневого дерева как определение любого рекурсивного объекта содержит базисную и рекурсивную части. Базисная часть, определяющая корень дерева, является нерекурсивным утверждением. Рекурсивная часть определения записана так, чтобы она редуцировалась (сводилась) к базе цепочкой повторных применений. В данном случае дерево с числом узлов n>1 индуктивно определяется через деревья с числом узлов меньше, чем n, пока не достигнут базисный шаг, где дерево состоит из единственного узла - корня. Рекурсивное определение корневого дерева позволяет более простым способом формализовать его структуру и алгоритмы обработки. Для неформального описания корневых деревьев часто используется генеалогическая терминология, согласно которой каждая ветвь отражает отношение потомок-предок между инцидентными ей узлами. Корень дерева – это узел, который не имеет предка. Узлы дерева, которые не имеют потомков называются листьями. Остальные узлы (не листья и не корень) называются разветвлениями. Следующий рисунок иллюстрирует классическое изображение корневого дерева средствами теории графов, где вершины и ребра графа представляют узлы и ветви дерева.

Рис. 1. Изображение корневого дерева в теории графов

На этом рисунке заглавные буквы латинского алфавита обозначают узлы, а строчные- ветви корневого дерева. Конфигурация ветвей этого корневого дерева такова, что узел А является корнем, узлы В С и D- разветвлениями, а узлы E, F, G, H, и K - листьями.

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

Рис. 2. Альтернативные способы представления корневого дерева

Приведенные альтернативные способы представления корневых деревьев иллюстрируют возможности практического применения иерархических структур.

Например, десятичная система Дьюи применяется в библиографии, а вложенные скобки - для получения полноскобочной записи при грамматическом разборе арифметических выражений.

Важными метрическими характеристиками корневого дерева является степень и уровень узла. Степенью узла корневого дерева считается число поддеревьев, для которых он является корнем. Для рассмотренного примера корневого дерева: корень А имеет степень 3, степени разветвлений B и D - равны 2, а степень разветвления С равна 1. Степени остальных узлов равны 0, потому что они являются листьями, т. е. не имеют поддеревьев. Уровень узла корневого дерева определяется длиной пути, образованного чередующейся последовательностью узлов и ветвей, который соединяет его с корнем. Длина пути измеряется числом узлов в нем. Для рассмотренного примера корень А имеет уровень 1, разветвления B, C и D имеют уровень 2, а листья E, F, G, H и K - уровень 3.

При измерении длины пути числом ветвей в нем, указанные уровни узлов надо уменьшить на 1.

Обобщением понятия корневого дерева является понятие леса. Под лесом понимается упорядоченное множество непересекающихся корневых деревьев. Отражением близости этих понятий является простота преобразований дерева в лес и наоборот, леса в дерево. Исключение корня превращает дерево в лес.

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

Понятие бинарного дерева.

Важной разновидностью корневых деревьев является класс бинарных деревьев, где каждый узел может иметь не более 2-х потомков. В рекурсивном варианте определения бинарное дерево состоит из корня и 2-х бинарных поддеревьев: левого и правого, причем любое из них может быть пустым. Следующий рисунок иллюстрирует изображение бинарного дерева из 8-ми узлов A, B, C, D, E, F, G, H средствами теории графов.

Рис. 3. Изображение бинарного дерева в теории графов.

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

Рис. 4. Отличие корневых и бинарных деревьев

Эти бинарные деревья различны по структуре, потому что корень первого из них имеет только левый потомок, а корень второго - только правый. Однако, как деревья они эквивалентны дереву из 2-х узлов А и В, которое и зображено на том же рисунке справа. В общем случае различие между корневым деревом и бинарным деревом состоит в том, что каждый узел корневого дерева может иметь произвольное число поддеревьев, в то время как любой узел бинарного дерева может иметь только 0, 1 или 2 поддерева и существует различие между левыми и правыми поддеревьями.

Несмотря на эти отличия бинарные деревья могут быть использованы для представления корневых деревьев. Возможность такого представления устанавливает следующее естественное соответствие между корневыми и бинарными деревьями. Левая ветвь каждого узла соединяет его с первым узлом следующего уровня, а правая - с другими узлами следующего уровня (братьями). Следующий рисунок демонстрирует естественное соответствие 3-х уровневого корневого дерева его бинарному представлению.

Рис. 5. Естественное соответствие между корневым и бинарным деревьями.

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