Новиков Ф.А. Дискретная математика для программистов (860615), страница 57
Текст из файла (страница 57)
— Е+ (v, А[г\) { добавляем ребро (г>, А[г\) }В : = В - v { удаляем вершину v из списка неиспользованных }end forПример Для дерева, представленного на рис. 9.10, код Прюфера 7,9,1,7,2,2,7,1,2,5,12. На этом рисунке числа в вершинах — это их номера, а числа на рёбрахуказывают порядок, в котором будут выбираться висячие вершины и удалятьсярёбра при построении кода Прюфера.К О Д Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево, построенноеалгоритмом 9.2 по коду А, который построен алгоритмом 9.1 по дереву Т, то Т"изоморфно Т, X" ~ Т.
Для этого установим отображение / : 1 ..р —>• 1 ..р междуномерами вершин в деревьях Т и X" по порядку выбора вершин в алгоритмах:если вершина v выбрана па г-м шаге алгоритма 9.1, то вершина f(v) выбрана наг-м шаге алгоритма 9.2. Заметим, что Dom / = 1 ..р, поскольку висячие вершиныесть в любом дереве и удаление висячей вершины оставляет дерево деревом. Далее, I m / = 1 ..р, поскольку па г-м шаге алгоритма 9.2 использовано г — 1 числоиз р чисел и остаётся р — г + 1 чисел, а в хвосте кода Прюфера занято не болеер — г чисел. Более того, Vv ( f ( v ) = v). Действительно, номера вершин, которыеявляются висячими в исходном дереве, не появляются в коде Прюфера (кроме,может быть, одной висячей вершины с наибольшим номером), а номера вершин,ОБОСНОВАНИЕ9.3. Представление деревьев в программах305которые пе являются висячими, обязательно появляются.
Поскольку при выборе первой вершины v в алгоритме 9.1 все вершины с меньшими номерами пеявляются висячими, их номера будет присутствовать в коде и, значит, не могут быть использованы па первом шаге алгоритма 9.2. Таким образом, па первомшаге алгоритм 9.2 выберет ту же вершину v. Но после удаления вершины v павтором шаге снова имеется дерево, к которому применимы те же рассуждения.Итак, / — тождественное и, значит, взаимно-однозначное отображение. Заметимтеперь, что для определения г-го элемента кода па г-м шаге алгоритма 9.1 используется, а затем удаляется ребро (и, Л [г]) и в точности то же ребро добавляется вдерево Т' на г-м шаге алгоритма 9.2. Следовательно, / — взаимно-однозначноеотображение, сохраняющее смежность и Т ~ Т'.•ЗАМЕЧАНИЕКод Прюфера — наиболее экономное по памяти представление дерева.
Его можно немногоулучшить, если заметить, что существует всего одно дерево с двумя вершинами — К2,а потому информацию о «последнем ребре» можно не хранить, она восстанавливаетсяоднозначно.9.3.2. Представление упорядоченных ориентированныхдеревьевВ упорядоченных ордеревьях выделен корень и поддеревья упорядочены. Использование этой информации позволяет построить ещё более компактное представление по сравнению с кодом Прюфера для свободных деревьев. Пусть упорядоченное ордерево задано списками смежности (см. 7.4.4), причём узлы перенумерованы в соответствии с порядком прямого обхода, определённым в доказательстве теоремы 9.2.3. Тогда следующий алгоритм построит представлениеупорядоченного ордерева с р узлами в виде битовой шкалы (кода) из 2q = 2р - 2разрядов.Алгоритм 9.3 Построение кода упорядоченного ордереваВход: Нетривиальное упорядоченное ордерево Т, заданное списками смежностиГ : array [l..p] ofгде N = record v : l..p;n : ]N end record, причём узлыперенумерованы в прямом порядке.Выход: Массив С : array [1..2g] of 0..1, являющийся кодом ордерева Т.i : = 0 { количество заполненных разрядов кода }TraverseTYee(l) { корневой узел имеет номер 1 }Основная работа выполняется рекурсивной процедурой TraverseTree, для которой переменная г и массивы Г и С глобальны.306Глава8.СвязностьВход: Число n : 1 ..р — номер текущего узла.Выход: Заполнение двух разрядов кода С.i: = г + 1; С[г]: = 1 { отмечаем вход в узел }d\ = Г[п] { указатель на первый элемент списка сыновей }while d Ф nil doTraverseTree(d.v) { построение кода поддерева очередного сына }d: = d.n { выбор следующего сына }end whilei: = i + 1; C[i]: = 0 { отмечаем выход из узла }ЗАМЕЧАНИЕАлгоритм 9.3 в сущности строит протокол выполнения алгоритма обхода в глубину упорядоченного ордерева.
Запись 1 отмечает вход в узел по единственной входящей дуге,запись 0 отмечает возврат из узла по этой же дуге.По построенному коду нетрудно восстановить исходное представление упорядоченного ордерева с помощью алгоритма 9.4, в котором используются вспомогательный стек S для хранения номеров узлов и две процедуры:• NewNode(u : l..p,n : IN) : }N — функция, создающая новый элемент спискасмежности с полями v и п и возвращающая указатель на него;• Append(L, е : |iV) — процедура, присоединяющая элемент, указатель на который задан параметром е, к списку, указатель на первый элемент которогозадан параметром L.Алгоритм 9.4 Восстановление упорядоченного ордерева по кодуВход: Массив С : array [1..2g] of 0..1 — код упорядоченного ордерева Т.Выход: Массив Г : array [l..p] of | N , где N = record V: l..p; П:end record — списки смежности упорядоченного ордерева Т.р: = 1 { счётчик узлов }Г[1]: = nil { корень }п : = 1 { текущий узел }for i from 1 to 2q doif C[i) = 1 thenp: = p + 1 { номер нового узла }Г[р]: = nil { новый узел пока листовой }d: = NewNode(p, nil) { дуга от текущего узла к новому узлу }Append (Г [n],d) { добавить узел в список смежности }п —* S { положить номер текущего узла на стек }п: = р { перейти в новый узел }elseп <— S { снять со стека и перейти в новый узел }end ifend for3079.3.
Представление деревьев в программахОБОСНОВАНИЕМассив С является представлением упорядоченного ордерева Т,то есть если к Т применить алгоритм 9.3, а затем к результату применить алгоритм 9.4, то получится то же самое упорядоченное ордерево Т. Действительно,алгоритм 9.4 интерпретирует протокол работы алгоритма 9.3. Каждый раз, ког-д а а л г о р и т м 9 . 3 в х о д и т п о д у г е в н е к о т о р ы й у з е л первый раз, он записывает впротокол 1, и в точности в том же порядке алгоритм 9.4 создаёт узлы. Каждыйраз, когда алгоритм 9.3 возвращается на предыдущий уровень и записывает впротокол 0, алгоритм 9.4 возвращается к родительскому узлу, снимая его номерсо стека.•Пример Применение алгоритма 9.3 к упорядоченному ордереву па рис. 9.11,слева, даст код 1101001101011000.ЗАМЕЧАНИЕНаложенное здесь требование прямого порядка нумерации узлов не является ограничением и используется только для упрощения изложения.
Можно показать, что при любойнумерации узлов ордерева алгоритм 9.3 построит код, а алгоритм 9.4 восстановит по этомукоду изоморфное ордерево, отличающееся разве что нумерацией узлов.9.3.3. Число упорядоченных ориентированных деревьевПредставление упорядоченных ордеревьев, построенное в предыдущем подразделе, обладает замечательным характеристическим свойством, позволяющим получить явную формулу для числа упорядоченных ордеревьев. Введём обозначения.Пусть Ь : array [l..nj of 0..1 — любая битовая шкала. Обозначим через No(b,k) —количество нулей в отрезке шкалы b[l..k],k ^ п, и через N\(b,k) — количествоединиц в отрезке шкалы Ь[1../г], к < п. Пусть теперь С : array [1..2q] of 0..1 — битовая шкала, построенная по упорядоченному ордереву Т алгоритмом 9.3.
Тогдапо построению алгоритма имеем:No(C,2q) = N\{C,2q) к,Ук <2q [N0(C, к) < N\(C, к)).(*)Из алгоритма 9.4 следует, что данное свойство является характеристическим,то есть любая шкала, обладающая свойством (*), является кодом некоторогодерева, причём по теореме 9.2.3 соответствие между деревьями и кодами взаимнооднозначно. Пусть Sn — множество битовых шкал длины 2п:5 n = f {с = ( а ь . .
. , а 2 п ) | V i б 1..2п (сц G { 0 , 1 } ) } .Обозначим число тех битовых шкал с е Sn, которые обладают свойством (*),через С(п):С(п)|{се Sn | N0{c,2n) = Ni(с,2п)По определению С(0) = f 1.к Vк < 2п (NQ(c,k) ^Nx(c,k))}\.308Глава8.СвязностьПримеррис. 9.6.ЛЕММАЯсно, что С(1) = |{(1,0)}| = 1, С(2) = 2 - см. рис. 9.5, С(3) = 4 - см.Для числа С(п) выполняется следующее равенство:TL— 1С(п) =Y^C(k)C(n-k-l).к—ОРассмотрим подмножество кодов с е Sn, удовлетворяющих более сильному условиюДОКАЗАТЕЛЬСТВОN0(C,2q) = Ni(C,2q)kVk<2q(N0(C,k)< N^C.k)),(*')и обозначим число таких кодов через С'{п).
Ясно, что в любом коде, удовлетворяющем условию (*'), первый бит равен 1, а последний — 0. Если их отбросить,то оставшаяся часть кода будет удовлетворять условию (*), и поэтому С'(п) == С(п - 1), причём по определению С'( 1) = С(0) = 1. Пусть теперь s — наименьшее число, такое, что код с[1..п] удовлетворяет условию (*'). Сгруппируемвсе коды, удовлетворяющие условию (*), по значениям числа s. В группе, в которой s = п, имеется С'(п) кодов, а в группах, в которых 1 ^ s ^ п — 1, имеетсяC"(s)C(n - s) кодов. ИмеемTI— 171—1С(п) = С'(п) + J2 C'(s)C(n - s) = С{п - 1) • 1 + Y^ C(s - 1 )С{п - s) =3=1S=1n—2n—1= C{n - 1)C(0) + Y C(k)C{n - к - 1) =C{k)C(n - к - 1),fc=0 fc=0где к: = s — 1.•Таким образом, для числа С(п) битовых шкал, удовлетворяющих условию (*),выполняется характеристическое рекуррентное соотношение чисел Каталана(см.
5.7.4), откуда немедленно следует теорема.ТЕОРЕМАЧисло ориентированных упорядоченных деревьев с q дугами равноC(2q,q)q+ 19.3.4. Проверка правильности скобочной структурыИз характеристического свойства (*) рассматриваемого представления упорядоченных ордеревьев в качестве побочного, но полезного наблюдения можноизвлечь эффективный алгоритм проверки правильности скобочной структуры(см. пример 5 в первой группе примеров подраздела 9.2.3).9.3. Представление деревьев в программах309Алгоритм 9.5 Проверка правильности скобочной структурыВход: Строка s : array [l..n] of char, возможно, содержащая скобки «(» и «)».Выход: Число 0, если скобочная структура правильна, или число в диапазоне 1..(п + 1), указывающее на позицию в строке, где скобочная структуранарушена.р: = 0 { число прочитанных открывающих минус число закрывающих скобок }for г from 1 to п doif s[i] = "(" thenp: = p + 1 { прочли открывающую скобку }end ifif s[i] = ")" thenp: = p — 1 { прочли закрывающую скобку }end ifif p < 0 thenreturn i { лишняя закрывающая скобка }end ifend forif p = 0 thenreturn 0 { скобочная структура правильна }elsereturn n + 1 { пе хватает закрывающих скобок }end ifВсякая правильная скобочная структура взаимно-однозначно соответствует упорядоченному ордереву.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
