Высота дерева графы алгоритм

Деревья поиска

Дерево — одна из наиболее распространенных структур данных в программировании.

Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.

• Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
• Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
• Предки — родители родителей, их родители, и так далее.
• Потомки — дети детей, их дети, и так далее.
• Лист (терминальная вершина) — вершина, не имеющая детей.
• Поддерево — вершина дерева вместе со всеми её потомками.
• Степень вершины — количество её детей.
• Глубина вершины — расстояние от корня до неё.
• Высота дерева — максимальная из глубин всех вершин.

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

Деревья также используются в контексте графов.

Бинарные деревья поиска

Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:

• У каждой вершины не более двух детей.
• Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
• У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
• У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
• Оба поддерева — левое и правое — являются двоичными деревьями поиска.

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

Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.

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

Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.

Источник

Как найти высоту бинарного дерева ( поиска )

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

То есть алгоритм не привязан к значению ключей узлов рассматриваемого двоичного дерева.

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

Рисунок — стандартное анонимное бинарное дерево ( поиска )

А что, собственно, понимают под высотой бинарного дерева?

Высота двоичного дерева — это количество ветвей между его корнем и наиболее глубоко расположенным листовым узлом ( этот лист лежит на самом нижнем уровне ). Связи между узлами дерева называют ветвями ( реже ребрами ).

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

Рисунок — анонимное двоичное дерево с высотой, выраженной через ветви

Следовательно, рассматриваемое анонимное бинарное дерево ( поиска ) имеет высоту, равную $4$:

Рисунок — анонимное бинарное дерево высотой $4$

💡 Но, лично мне, крайне интересно понять, а чему, например, будет равна высота пустого двоичного дерева, или дерева, в котором только одна вершина! Эти моменты крайне важно понимать при анализе алгоритма, так как они являются своего рода пограничными.

Если бинарное поисковое дерево пустое, то есть не содержит ни одного элемента, то принято его высоту считать равной $-1$:

Если бинарное дерево состоит только из одной вершины, то по определению высота такого дерева равна $0$. Некоторые новички в программировании и структурах данных ошибочно считают, что такое дерево имеет высоту, равную $1$. Но это неправильно. Только $0$.

Рисунок — бинарное дерево высоты $0$

Хочу подытожить некоторую информацию относительно высоты бинарного дерева:

#	Количество вершин в двоичном дереве	Как рассчитывается высота дерева
$1$	$0$ ( пустое дерево )	$-1$
$2$	$1$	$0$
$3$	$>1$	по формуле

➡ Очевидно, что моя задача понять, по какой формуле следует рассчитывать высоту заданного двоичного дерева.

Учитывая, что древовидные структуры крайне удобно обрабатывать рекурсивно, то я буду мыслить в сторону рекурсивной обработки.

В результате долгих размышлений и анализа у меня получилась следующая рекурсивная функция ( каскадная рекурсия ):

➡ Подобные реализации я всегда отношу к разряду сложных, так как «за кулисами» работы рекурсии скрыто куча важнейших мелочей. Правильно и быстро программировать такие функции — достаточно сложная задача, требующая высокой квалификации программиста.

А сейчас я распишу логику этого алгоритма в табличной форме, чтобы улучшить читателям понимание принципа работы рекурсивной функции Height().

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

Рисунок — двоичное дерево поиска ( «красный» путь показывает высоту дерева )

Анализирую логику алгоритма вычисления высоты двоичного дерева в табличной форме ( в данном случае эта форма наиболее наглядная и понятная ):

#	Ключ	Формула	Высота
$1$	$100$	max( Height( $50$ ), Height( $150$ ) ) + $1$	$?$
$2$	$50$	max( Height( $25$ ), Height( $75$ ) ) + $1$	$?$
$3$	$150$	max( Height( $125$ ), Height( $200$ ) ) + $1$	$?$
$4$	$25$	лист	$0$
$5$	$75$	max( Height( $63$ ), Height( $87$ ) ) + $1$	$?$
$6$	$125$	лист	$0$
$7$	$200$	max( Height( $190$ ), Height( NULL ) ) + $1$	$?$
$8$	$63$	лист	$0$
$9$	$87$	max( Height( NULL ), Height( $90$ ) ) + $1$	$?$
$10$	$190$	лист	$0$
$11$	$90$	лист	$0$

Сейчас я буду подниматься снизу вверх по этой таблице, подставляя известные значения в формулы. Ответ, который меня интересует, будет получен в самой верхней строке таблицы. Я выделю это значение красным цветом.

➡ Напомню, что высота несуществующего двоичного дерева составляет $-1$, то есть Height( NULL ) = $-1$.

#	Ключ	Формула	Высота
$1$	$100$	max( Height( $50$ ), Height( $150$ ) ) + $1$	$4$
$2$	$50$	max( Height( $25$ ), Height( $75$ ) ) + $1$	$3$
$3$	$150$	max( Height( $125$ ), Height( $200$ ) ) + $1$	$2$
$4$	$25$	лист	$0$
$5$	$75$	max( Height( $63$ ), Height( $87$ ) ) + $1$	$2$
$6$	$125$	лист	$0$
$7$	$200$	max( Height( $190$ ), Height( NULL ) ) + $1$	$1$
$8$	$63$	лист	$0$
$9$	$87$	max( Height( NULL ), Height( $90$ ) ) + $1$	$1$
$10$	$190$	лист	$0$
$11$	$90$	лист	$0$

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

Рисунок — бинарное дерево с простановкой высот для каждой вершины

Еще хотелось бы пояснить за вычислительную сложность рассмотренного алгоритма. Очевидно, что в процессе вычисления высоты дерева приходится обойти каждый его узел, следовательно, вычислительная сложность составляет $O( n )$, где $n$ — количество вершин дерева.

Существуют ли более эффективные алгоритмы, чем $O( n )$? Возможно, но я таких не знаю 😎

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

ВНИМАНИЕ

Для заказа программы на двоичное дерево ( поиска ) пишите на мой электронный адрес proglabs@mail.ru

Источник

Алгоритм Прима:

Всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остовное дерево.

Используя алгоритм Прима, сначала выбираем вершину v₀ графа G, а затем выбираем ребро с наименьшим весом e₁ = 0 ,v₁>, инцидентное к вершине v₀ и формируем дерево Т₁.

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

Сформировав дерево Т_k формируем дерево Т_k+1, выбирая ребро с минимальным весом e_k+1 такое, что одна его вершина принадлежит дереву Т_k, а другая — нет, и добавляем это ребро в дерево.

Продолжаем процесс до тех пор, пока дерево не будет содержать все вершины графа G.

1) Выбрать вершину v₀ графа G и ребро с наименьшим весом e₁, для которого v₀ – одна из вершин, и сформировать дерево T₁.

2) Для заданного дерева T_k с ребрами e₁, e₂, e₃, …, e_k, если имеется вершина, не принадлежащая T_k, выбрать ребро с наименьшим весом, смежное с ребром дерева T_k и имеющее вершину вне дерева T_k. Добавить в дерево T_k, формируя дерево T_k+1.

3) Продолжить, пока имеются вершины графа G, не принадлежащие дереву.

Построение минимального остовного дерева можно проводить двумя способами:

1) остов графа строится непосредственно на самом графе, выделяя ребра утолщенной линией, которые входят в остовное дерево;

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

Начав с вершины а, первым выбираем ребро , поскольку оно имеет минимальный вес.

Т. о. дерево T1 состоит из ребра .

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

Далее выбираем ребро , поскольку это ребро с минимальным весом из тех, что имеют только одну вершину в Т2. Получаем Т3.

Теперь, так как имеется два ребра с одинаковым весом и одной вершиной в Т3, имеем выбор.

Предположим, выбрано ребро , поэтому дерево Т4 имеет следующий вид.

Следующим выбираем ребро . Это ребро имеет минимальный вес из тех, что имеют только одну вершину в дереве Т4; отсюда Т5

Наконец, выбираем ребро . Поскольку это ребро минимального веса из тех, что имеют одну вершину в Т4, а вершина g — последняя из оставшихся вершин, имеем дерево Т6, которое является искомым остовным деревом.

Пример. Для данного взвешенного графа найти минимальное корневое остовное дерево, используя алгоритм Прима. Определить высоту построенного дерева.

Выбираем вершину , которая будет корнем дерева. Из трех ребер, инцидентных вершине , выбираем те, что имеют наименьший вес.

Два ребра (до вершин и ) с весом, равным 7, инцидентны вершине . Присоединяем их.

К вершине присоединяем ребро с весом 5 до вершины . К вершине присоединяем ребро с весом 4 до вершины . К вершине присоединяем ребро с весом 6 до вершины .

Получаем следующее минимальное корневое дерево с весом, равным _min(T)=7+7+6+5+4=29. Высота дерева = 3.

Источник