Длина внутреннего пути дерева

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

имеется одна специально выделенная вершина, называемая корнем дерева ;
остальные вершины (исключая корень) содержатся в m попарно непересекающихся множествах T1,T2. Tm , каждое из которых, в свою очередь, является деревом.

Деревья T1,T2. Tm называются поддеревьями данного дерева .

Упорядоченным деревом мы будем называть такое дерево, в котором важен порядок следования поддеревьев T1,T2. Tm .

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

Ребро — это неориентированная связь между двумя вершинами дерева. Ясно, что ребро можно превратить в дугу, если задать на нем ориентацию (направление), а любое дерево можно превратить в ориентированное дерево, если задать ориентацию ребер.

Количество поддеревьев некоторой вершины называется степенью этой вершины. Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями .

Вершина с нулевой степенью называется листом , иначе — она называется внутренней вершиной (внутренним узлом) .

Число листьев дерева называется весом дерева.

Символы A,B,C. , которые служат для обозначения вершин, называются метками вершин .

Приведенное неформальное определение является рекурсивным (мы определили дерево в терминах деревьев). Ниже мы дадим формальное нерекурсивное определение дерева, но рекурсивное определение кажется более подходящим, так как рекурсивность является естественной характеристикой структур типа дерево.

Для удобства дальнейших рассмотрений договоримся о графическом способе изображения деревьев. Корень будем располагать выше поддеревьев (ясно, что корень при изображении будет располагаться выше всех остальных вершин дерева). Вершины дерева будем изображать точками на плоскости, а корень дерева связывать дугами (ребрами) с корнями деревьев T1,T2. Tm . Взгляните на рисунок и на комментарии, приведенные ниже его:

Рис.1. Иллюстрация основных понятий

Символы A, B, C, D, K, L, M, N, R — метки вершин , вершина А — корень , вершины C, L, R, M, N, K — листья , вес дерева равен 6 (количество листьев — 6), вершина В имеет степень 2, вершина D имеет степень 4.

Определение 2 (неформальное) Вершина Y , которая находится непосредственно под узлом X , называется (непосредственным) потомком (сыном) X , вершина X в данном случае называется (непосредственным) предком (отцом) Y .

В этом случае, если вершина X находится на уровне i , то говорят, что вершина Y находится на уровне i+1 . Мы будем считать, что корень дерева расположен на уровне 0. Максимальный уровень какой-либо вершины дерева называется его глубиной или высотой .

Максимальная степень всех вершин дерева называется степенью дерева .

если вершина не имеет потомков, то она является листом ;
степень внутренней вершины можно определить как число ее (непосредственных) потомков.

Максимальное число вершин в дереве заданной высоты h достигается в случае, когда все вершины имеют по d поддеревьев, кроме вершин уровня h , не имеющих ни одного. Тогда в дереве степени d нулевой уровень содержит одну вершину (корень), первый уровень содержит d ее потомков, второй уровень содержит d 2 потомков d узлов уровня 2 и т.д.

Таким образом получаем, что максимальное число вершин для дерева с высотой h и степенью d можно найти по формуле:

Определение 3 (неформальное) Количество дуг, которые нужно пройти, чтобы продвинуться от корня к вершине X , называется длиной пути к вершине X . Очевидно, что вершина, расположенная на уровне i , имеет длину пути i .

Ветвью будем называть путь от корня дерева к любому ее листу .

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

Длина внутреннего пути = Длина внутреннего пути в левом поддереве + Длина внутреннего пути в правом поддереве + Количество узлов в дереве - 1.

Для иллюстрации определений приведем рисунок двух деревьев, которые будем предполагать упорядоченными:

Рис.2. Упорядоченные деревья

длина пути к вершине L равна 3,
длина пути к вершине К равна 1,
длина внутреннего пути равна 18,
одно из ветвей дерева — AKDL .

Дерево II отличается от дерева I , так как в нем изменен порядок следования поддеревьев с корнями K и B . Определение 4 [1] (неформальное) Лес — это множество деревьев (обычно упорядоченное), состоящее из некоторого (быть может, равного нулю) числа непересекающихся деревьев. Часто для леса, состоящего из n деревьев пользуются термином «дерево с n-кратным корнем» .

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

либо пусто,
либо состоит из корня (некоторая выделенная нами вершина), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревом корня .

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

Каждая вершина бинарного дерева, отличная от корня, может рассматриваться как корень бинарного поддерева с вершинами, достижимыми из нее.

Изобразим несколько бинарных деревьев:

Рис.4. Примеры бинарных деревьев

Определение 6 (неформальное) Говорят, что два бинарных дерева T и T’ подобны , если они имеют одинаковую структуру ; это означает, что подобные деревья либо оба пусты, либо оба непусты и их левые и правые поддеревья соответственно подобны.

Попросту говоря, подобие означает, что графические изображения деревьев T и T’ имеют одинаковую «конфигурацию».

Говорят, что бинарные деревья T и T’ эквивалентны , если они подобны и если, кроме того, соответствующие вершины содержат одинаковую информацию.

либо оба пусты,
либо же оба непусты, Info (Корень(T))=Info (Корень(T’)) и их левые и правые поддеревья соответственно эквивалентны.

В качестве иллюстрации приведенных определений рассмотрим четыре бинарных дерева:

Первые два из них не подобны; второе, третье и четвертое деревья подобны, причем второе и четвертое эквивалентны. (1) Кнут Д. Искусство программирования для ЭВМ. Т.1: Основные алгоритмы. — M.: Мир, 1976. — 736 с.

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

Источник