Лес_деревья_бинарные_деревья

3.4. Соответствие между упорядоченным лесом и бинарным деревом

существует однозначное соответствие между бинарным деревом и упорядоченным лесом.

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

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

• разорвем все связи между узлами, оставив для каждого из них только крайнюю левую связь — от узла к его левому сыну, если он есть;
• проведем правую связь от каждого узла к его правому брату, если он есть.

Таким образом, каждый узел имеет теперь не более двух связей — правую и левую, причем любая из них может отсутствовать.. Такое представление леса называется «левый сын»-«правый брат» [3] и ему соответствует бинарное дерево, изображенное на рис.3.9, б.

а)упорядоченный лес из двух деревьев б)соответствующее бинарное дерево

в) привычное изображение бинарного дерева

Рис.3.9. Соответствие между упорядоченным лесом и бинарным деревом.

Немного развернув рисунок, получим привычное изображение бинарного дерева (рис.3.9,в)

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

Поскольку алгоритмы и прямого, и обратного перехода включают действия, которые можно выполнить только единственным образом, можно говорить об однозначном соответствии между упорядоченным лесом и эквивалентным ему бинарным деревом. Такое соответствие иначе называется естественным или каноническим [8,10].

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

Если представить упорядоченный лес как линейный список упорядоченных деревьев (т. е. S-выражение особого вида), то напрашивается прямая аналогия с рекурсивным представлением иерархических списков в виде пары «голова-хвост». Для упорядоченного леса «голова» — первое его дерево, а «хвост»— оставшиеся деревья. В свою очередь, первое дерево (голову списка) также можно представить в виде пары «голова»-«хвост», если «головой» считать корень, а «хвостом» — лес его поддеревьев. Таким образом, любой непустой упорядоченный лес можно представить в виде трех частей:

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

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

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

Реализация иерархических списков была рассмотрена ранее (см. разд. 3.1) как введение в функциональное программирование.

При использовании императивных языков (таких как С++ или Pascal) чаще применяется реализация бинарных деревьев. Отметим, что многие задачи (сортировка, поиск, сжатие данных и т. п.) сами по себе предполагают использование бинарных деревьев в качестве структур данных. Учитывая еще и возможность их использования для реализации упорядоченных деревьев, следует признать, что бинарные деревья являются основной формой представления иерархических структур. Проанализируем различные формы реализации и приведем примеры.

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

Источник

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

Деревом называют конечный связный граф с выделенной вершиной (корнем), не имеющий циклов (рис. 2.14).

Для каждой пары вершин дерева — узлов — существует единственный маршрут, поэтому вершины удобно классифицировать по степени удаленности от корневой вершины. Расстояние до корневой вершины V ₀ называется ярусом s вершины, s= d (V ₀ V).

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

Рис. 2.14. Иллюстрация графа-дерева

В одном из них остается корневая вершина, и этот граф G ₁тоже будет являться деревом. В другом графе выделим вершину, инцидентную удаленному мосту. Тогда второй подграф также будет являться деревом. Если в исходном графе вершина F принадлежала s -му ярусу, а дерево «обрубили» по ребру, соединявшему вершины t -го и (t — 1)-го ярусов, причем s ³ t, то тогда

В_частности, если s = t и FÎ , то вершина F будет корневой для и s’ (F)= s — t =0. Если s < t, то вершина заведомо принадлежит подграфу G ₁.

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

Теорема 2.7. Граф G(V, X) ( ï V ï = п > 1 > является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

граф G(V, X) связен и не содержит циклов’,

граф G(V, X) не содержит циклов и имеет п- 1 ребро;

граф G(V, X) связен и имеет п- 1 ребро;

граф G(V, X) не содержит циклов, но добавление ребра между несмежными вершинами приводит к появлению одного и только одного элементарного цикла;

граф G(V, X) связный, но утрачивает это свойство после удаления любого ребра;

в графе G(V, X) всякая пара вершин соединена цепью, и только одной..

Итак, дерево с п вершинами имеет п — 1 ребро, поэтому оно будет минимальным связным графом. Висячие вершины, за исключением корневой, называются листьями. На рис. 2.14 листьями являются, например, вершины V ₄, V ₁₃ и V ₂₀. При п = 2 дерево состоит из корня и листа и имеет вид отрезка.

Пусть G ₁, G ₂. -, G _k — непересекающиеся деревья, т.е. » i, j Î (1. k), G _i Ç G _j=Æ. Тогда упорядоченное объединение деревьев G = , представляет собой несвязный граф, называемый лесом. Компонентами связности леса являются деревья. Остовом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом (говорят: «покрывающим его деревом»).

Кодеревом Т’ остова T графа G называется дополнение T до G, т. е. такой его подграф, который содержит все его вершины и только те ребра, которые не входят в Т. Тогда G= Т ÈТ’ = Т Å Т’. Иначе говоря, кодеревом остова Т(V, Х ₁ ) графа G(V, Х) будет остов Т’ (V, Х\Х ₁ ). Очевидна двойственность: (Т’)’= Т.

Дерево может быть представлено расслоенным на ярусы (уровни), при этом ветвям, попавшим в один ярус, соответствует одинаковая длина пути исходного графа. Число путей в каждом дереве соответствует числу висячих вершин (листьев). Например, в графе на рис. 2.14 двадцать листьев и двадцать путей от V ₀.

При описании деревьев принято использовать термины: отец, сын, предок, потомок.

Каждая вершина дерева называется узлом, причем каждый узел является корнем дерева, имеющего п поддеревьев (п е [0, п)). Тогда узел без поддеревьев называется листом и является висячей вершиной. Узел k -го яруса называется отцом узла (k+ 1)-го яруса, если они смежны. Узел (k+ 1)-го яруса называется сыном узла k-го яруса. Два узла, имеющие одного отца, называются братьями (рис. 2.15). Упорядоченным деревом называется дерево, в котором поддеревья каждого узла образуют упорядоченное подмножество. Для упорядоченных деревьев принята терминология: старший и младший сын для обозначения соответственно первого и последнего сыновей некоторого узла.

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

Бинарное дерево уровня п называется полным, если каждый его узел уровня п является листом, а каждый узел уровня меньше, чем п, имеет непустое левое и правое поддеревья. Примером полного бинарного дерева служит таблица розыгрыша соревнования по олимпийской системе («плей-офф»). На рис. 2.17 приведена таблица розыгрыша Кубка мира по футболу 2002 г., начиная со стадии четвертьфиналов (указан корень V₀ — Бразилия).

Бинарные деревья применяются в информатике для поиска одного из двух возможных вариантов ответа. Например, при поиске данных, когда необходимо сравнить каждый элемент списка с образцом, и если значения совпадают, то процесс поиска завершен, а если не совпадают, то поиск данных продолжается. Впервые понятие двоичного дерева ввел в III в. римский философ Порфирий.

Рис. 2.17. Бинарное дерево для представления розыгрыша Кубка мира по футболу 2002 г.

Цикломатическое число графа. Пусть задан неориентированный граф G. Цикломатическим числом графа называется число v(G) = т(G) + с(G) — п(G), где т(G) — число его ребер; с(G) — число связных компонент графа; п(G) — число вершин. Цикломатическое число дерева равно нулю. Цикломатическое число леса равно сумме цикломатических чисел составных связных компонент — деревьев и, следовательно, тоже равно нулю. Для остальных графов цикломатические числа — положительные.

Например, для полного графа К₅ (имеющего пять вершин и С₅ 2 = 10 ребер) Цикломатическое число равно у=10+1-5=6.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник