Способы представления деревьев в ЭВМ. Упорядоченные и бинарные деревья, их свойства.

Назовем упорядоченным ориентированным деревом T (V, E) множество узлов, такое, что

1) существует узел r Î V, который называется корнем дерева;

2) остальные узлы содержатся в k попарно непересекающихся множествах T ₁,…, T _k, T _iÇ T _j=Æ, i,j=1,…, k, i¹j.

Ориентированное дерево можно записать так: T ={{ r }, T ₁,…, T _k }Чаще всего в упорядоченных деревьях стрелки не рисуют. Достаточно того, что мы представляем его именно в виде дерева, обычно перевернутого. Для корневых деревьев часто используется «ботаническая» и «генеалогическая» терминология. Так концевые (висячие) вершины называют листьями. По генеалогической терминологии если вершина v₁ достижима из вершины v₂, то вершину v₂ называют предком вершины v₁, а вершину v₁ – потомком вершины v₂. То есть непосредственной достижимости соответствует понятие прямого потомка. Глубиной корневого дерева называется максимальная длина пути из корня в лист. k-м уровнем или слоем корневого дерева будем называть все вершины, достижимые из корня за k шагов, то есть путь до которых состоит из k дуг.

Бинарные деревья.

Бинарным наз.ориентированное дерево, состоящее из корня и двух непересекающихся поддеревьев – левого и правого, каждое из которых тоже является бинарным деревом. Для любого узла бинарного дерева полустепень захода равна 1, а полустепень исхода равна 2.

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

Представление упорядоченных деревьев в ЭВМ.

Представление упорядоченных деревьев в ЭВМ осуществляется через соответствующие им бинарные деревья. Это так называемое линейное кодирование бинарных деревьев. То есть вместо матрицы мы получаем цепочку.

Кодирование списком. Одна ячейка списка – 3 значения: 1)указатель на сам узел, 2) указатель на левый узел, 3) указатель на правый узел. Таким образом, объем памяти n=3p. Очень удобно восстанавливать исходное упорядоченное дерево.

Польская запись. Первый элемент – указатель на узел, второй – условный код: 0 – нет потомков, 1 – есть левый потомок, 2- есть правый потомок, 3 – есть оба потомка. Наиболее компактная запись, так как тройка в двоичном коде – это 11. Поэтому общий объем памяти n£2p. Но ходить по такому дереву сложнее, чем при кодировании списком. Это удобная запись именно для бинарных деревьев.

Бинарное дерево называется выровненным, если все концевые вершины располагаются на двух последних уровнях. Выровненное дерево имеет при заданном числе узлов p наименьшую глубину. Бинарное дерево называется полным, если все его концевые вершины располагаются на одном уровне.

Количество концевых вершин в полном бинарном дереве глубины h. При h =2 - четыре вершины (2²).При h =3 - восемь вершин(2³).и так далее.

Докажем по индукции, что для дерева глубины h будет 2 ^h вершин.

Пусть утверждение справедливо для h = k. Покажем, что оно справедливо для h=k+ 1. Из каждой висячей вершины бинарного дерева можно выпустить максимум 2 дуги. Т.е. на уровне k+ 1 будет 2×2 ^k =2 ^{k+ 1} дуг. Итак, в бинарном дереве глубины h может быть не более 2 ^h листьев (концевых вершин). Тогда высота дерева с числом листьев n будет не меньше чем h ³log₂ n.

Это оценка снизу. Но при определении максимального количества операций для древовидного процесса решений нужна оценка сверху. Для оценки сверху нужно учесть количество всех возможных перестановок концевых вершин. При больших значениях n по формуле Стирлинга получается следующая оценка: h £ n log₂ n.

 

18. Задача о минимальном соединении. Алгоритм Краскала и алгоритм Прима.

Первым взялся за рассмотрение этой задачи английский математик Кэли. Он показал, что число различных деревьев, которые можно построить на n вершинах t_n = n^{n- 2}. Этот результат получил название теоремы Кэли. Кэли предполагал, что вершины занумерованы определенным образом, то есть не учитывал изоморфизм,т.к.под вершинами у него подразумевались конкретные города. Решение же этой задачи с учетом изоморфизма оказалось гораздо сложнее. Перейдем к другой практической постановке задачи - о поиске соединения минимального веса. Как и в задаче поиска кратчайших путей, мы здесь имеем матрицу весов, которая задает стоимость всех возможных соединений. Требуется найти соединение минимальной суммарной стомости, то есть минимального веса. Задача в такой постановке называется задачей Штейнера.

Такое соединение представляет собой свободное дерево. С другой стороны, это дерево является подграфом некоторого взвешенного графа G на том же количестве вершин, который описывает все возможные соединения и их стоимости. Подграф графа G, включающий все его вершины, называется остовным подграфом. То есть в математической постановке мы имеем задачу о построении остовного дерева минимального веса. Мы рассмотрим два алгоритма построения такого дерева.

Алгоритм Краскала.

Возьмем неориентированный взвешенный граф со следующей матрицей весов. Диаграмма графа показана на рис.3.18.

 

		¥	¥		¥	¥
					¥	¥	¥
¥				¥
¥					¥
		¥				¥	¥
¥	¥		¥				¥
¥	¥			¥
	¥			¥	¥

Шаг 1. Упорядочим все ребра по возрастанию весов. Имеем следующую последовательность: (1,2), (3,6), (4,5), (4,8), (1,8), (2,3), (2,4), (4,7), (7,8), (1,5), (3,4), (3,7), (5,6), (2,5), (3,8), (6,7).

Рис.3.18

Шаг 2. Берем первое слева (самое дешевое) ребро в списке и образуем первую компоненту связности: G ₁={ V ₁={1,2}, E ₁={(1,2)}}

Шаг 3 (общий). Предположим, что на текущем шаге алгоритма у нас есть уже какое-то количество компонент связности G ₁,…, G_k. Берем очередное ребро в списке и поступаем с ним следующим образом.

1. Если обе концевые вершины ребра принадлежат какой-то из компонент G _i, то пропускаем его и переходим к следующему.

2. Если одна концевая вершина ребра (u,v), например, u принадлежит G _i, то включаем в эту компоненту ребро и новую вершину v – вторую концевую точку ребра.

3. Если обе концевые вершины не принадлежат ни одной из существующих k связных компонент, образуем компоненту G _k+1 из этого ребра и его концевых вершин.

4. Если концевые вершины ребра принадлежат разным компонентам связности, например, G _s и G _t, то объединяем эти компоненты в одну и добавляем ребро, их соединяющее. Теперь имеем k=k- 1 компоненту связности.

Если k =1 и все вершины графа в нее включены, то процесс завершен.

Продолжим теперь процесс построения для нашего графа.

В соответствии с условием 3 общего шага выбираем ребра (3,6), (4,5) и образуем две новые компоненты связности: G ₂={ V ₂={3,6}, E ₂={(3,6)}}, G ₃={ V ₃={4,5}, E ₃={(4,5)}}. (рис.3.19 а).

Следующее ребро (4,8) удовлетворяет условию 2, поэтому присоединяем его к третьей компоненте: G ₃={ V ₃={4,5,8}, E ₁={(4,5),(4,8)}} (рис. 3.19 б).

Ребро (1,8) удовлетворяет условию 4, то есть объединяет две компоненты связности: G ₁= G ₁È G ₃È(1,8)={ V ₁={1,2,4,5,8}, E ₁={(1,2),(4,5),(4,8),(1,8)}} (рис.3.19 в).

Ребро (2,3) также удовлетворяет условию 4, в результате чего объединяются все уже построенные компоненты связности: G ₁= G ₁È G ₂È(2,3)={ V ₁={1,2,3,4,5,6,8}, E ₁={(1,2),(4,5),(4,8),(1,8),(3,6),(2,3)}} (рис.3.19 г).

Ребро (2,4) пропускаем согласно условию 1 общего шага. Следующее ребро (4,7) позволяет включить в остовное дерево последнюю вершину.

G ₁= G ₁È(4,7)={ V ₁={1,2,3,4,5,6,7,8}, E ₁={(1,2),(4,5),(4,8),(1,8),(3,6),(2,3),(4,7)}} (рис.3.19 д). Процесс построения завершен. Вес полученного дерева P =1+1+1+2+1+2+2=10.

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

Компонента связности G здесь одна, но придется постоянно хранить список «запасных» ребер. Сама работа алгоритма напоминает «поиск в ширину».

Шаг 1. Берем первую вершину v ₀ и все смежные с ней, то есть рассматриваем все инцидентные вершине v ₀ ребра. Выбираем ребро минимального веса (v ₀, v) включаем его в G и переходим в вершину v. Остальные ребра вносим в рабочий список E ₀. Можно сразу упорядочивать ребра в E ₀ по возрастанию весов.

Шаг 2(общий).

2.1. Добавляем в список E ₀ все ребра, инцидентные последней включенной в G вершине v.

2.2. Из полученного списка выбираем ребро минимального веса, содержащее хотя бы одну еще не включенную в G вершину u. Добавляем его в G вместе с вершиной u и переходим в эту вершину, то есть к шагу 2.1.

2.3. Если все вершины включены, то процесс завершен.

Давайте выполним такое построение для нашего графа с рис.3.18.

1. На первом шаге компонента связности та же: G ={ V ={1,2}, E ={(1,2)}}. Создаем рабочий список из оставшихся ребер, инцидентных вершине 1: E ₀={(1,8),(1,5)}. Будем упорядочивать ребра в рабочем списке по возрастанию весов слева направо.

2. Последней включенной вершиной является вершина 2. Добавляем инцидентные ей ребра в рабочий список, упорядочивая список по возрастания весов: E ₀={(1,8),(2,3),(1,5),(2,5)}. Теперь из этого списка выбираем ребро минимального веса, содержащее еще не включенную вершину 8: G ={ V ={1,2,8}, E ={(1,2),(1,8)}}.

3. Исключаем ребро (1,8) из списка, а в список добавляем ребра, инцидентные вершине 8: E ₀={(4,8),(2,3),(7,8),(1,5),(2,5),(3,8)}. Из него выбираем очередное ребро, содержащее не включенную вершину 4: G ={ V ={1,2,4,8}, E ={(1,2),(1,8),(4,8)}}.

Продолжаем процесс по той же схеме.

4. E ₀={(4,5),(2,3),(7,8),(4,7),(1,5),(2,5),(3,8)}; G ={V={1,2,4,5,8}, E ={(1,2),(1,8), (4,8), (4,5)}}.

5. E ₀={(2,3),(7,8),(4,7),(1,5),(5,6),(2,5),(3,8)}; G ={ V ={1,2,3,4,5,8}, E ={(1,2), (1,8),(4,8), (4,5),(2,3)}}.

6. E ₀={(3,6),(7,8),(4,7),(1,5),(3,4),(5,6),(2,5),(3,8)}; G ={ V ={1,2,3,4,5,6,8}, E ={(1,2), (1,8), (4,8), (4,5),(2,3),(3,6)}}.

7. E ₀={(7,8),(4,7),(1,5),(3,4),(5,6),(2,5),(3,8),(6,7)}; G ={ V ={1,2,3,4,5,6,7,8}, E ={(1,2), (1,8), (4,8), (4,5),(2,3),(3,6),(7,8)}}.

Вес полученного дерева P =1+2+1+1+2+1+2=10, как и в предыдущем построении, хотя порядок включения ребер другой. И последнее ребро было выбрано другое, но аналогичного веса. Полученные остовные деревья равносильны. В целом алгоритм Прима, хотя и кажется многим более понятным, в вычислительном плане менее эффективен, поскольку нам приходится просматривать список ребер по нескольку раз.