7Структуры данных типа граф. Представление графов в памяти. Алгоритмы прохождения в «глубину» и в «ширину». Топологическая сортировка. Матрица достижимости.

Граф – двойка G = (X, U), где X – множество элементов (вершин, узлов), а U представляет собой бинарное отношение на множестве X (U X X). Если |X| = n (конечно), то граф является конечным. Элементы U называют либо дугами, либо ребрами.

X1	X2	X = {X1, X2, X3, X4}
X3	X4	X X = {(X1,X1), …,(X4,X4)}

U = {(X1,X2), (X1,X3), (X2,X3), (X2,X4)} U X X = X2

Если (Xi, Xj) – упорядоченная пара, то такой граф называется ориентированным (орграфом), а элементы U называются дугами. Если (Xi, Xj) = (Xj, Xi), то граф –

неориентированный (неорграф), а элементы U называются ребрами.

F: U R – если задана такая функция, то граф является взвешенным, где R – множество вещественных чисел, т.е. отображение дуги на число.

Вообще: U X X.

Компонентами орграфа являются: дуга, путь, контур. Путь – такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом последующей. Контур – конечный путь, у которого начальная вершина совпадает с конечной. Контур единичной длины называют петлей.

Компонентами неорграфа являются, соответственно: ребро, цепь, цикл. Цепь – непрерывная последовательность ребер между парой вершин неориентированного графа. Неориентированный граф называют связным, если любые две его вершины можно соединить цепью. Если же граф – несвязный, то его можно разбить на подграфы. Например:

X2	X3		X6
G:	X4	X5	G = G1 U G2
X1
	G1		G2

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

Представление графа в памяти ЭВМ.

1)Графический способ представления (если граф небольшой).

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

Числовыми характеристиками графа являются: количество узлов, количество дуг, ранг графа. Ранг графа: R(G) = |X| - K, где К – количество компонентов связности графа в случае, если но не связан.

Рассмотрим матрицу смежности. Пусть задан граф G = (X, U), |X| = n. Имеем матрицу А размерности n n, которая называется матрицей смежности, если элементы

			1,(X,X) U
				i j
ее определяются следующим образом:	a				.
	ij
			0,(X,X) U
				i j

Рассмотрим применение матричной алгебры для определения характеристик графа. Выражение a i k a k j означает, что между узлами i и j есть две дуги, проходящие через узел k, если значение выражения равно True.

n	a
Выражение a		означает, что всегда имеется путь между этими узлами
k 1 ik	k j

длиною 2 (два), если выражение истинно.

А А = А(2) – логические операции заменяются арифметическими. Тогда каждый элемент a i j будет давать информацию о том, есть ли путь из i в j (i, j = 1, 2,…,n).

Выражение А(n) = А(n – 1) А означает, есть ли путь длиной n между различными

узлами i. По диагонали будет характеристика, есть ли циклы (контура) в матрице. n

Р = А V А(2) V …V А(n) = А(k ) - матрица связности. Определяется, существует ли k 1

какой-либо путь между узлами i и j. Алгоритм вычисления данного выражения:

1.Р = А;

2.повторить 3, 4 (k=1, 2,…, n);

3.повторить 4 для i=1, 2, …,n;

4. повторить Рi j = Рi j V (Рi k Рk j), j=1, 2,…, n.

В связной памяти наиболее часто представление графа осуществляется с помощью структур смежности. Для каждой вершины множества X задается множество М(X i) соответственно вех его последователей (если это орграф) или соседей (для неорграфа). Таким образом, структура смежности графа G будет представлять собой список таких множеств: < М(X 1), М(X 2),…, М(X n)> для всех его вершин.

Рассмотрим пример (узлы обозначаем в виде цифр: 1, 2,…, n):

2	3	5	Для неорграфа:

G:		1: 2, 3;	2: 1, 3;	3: 1, 2;	4: 5;	5: 4.
	1	4
		Для орграфа: 1: 2;		2: 3; 3: 1;	4: 5;	5: - .

Структуру смежности можно реализовать массивом из n линейно связанных списков:

1

2

3

4

5

2 3 1 5

Представление графа может оказать влияние на эффективность алгоритма. Часто запись алгоритмов на графах задается в терминах вершин и дуг, независимо от представления графа. Например, алгоритм определения количества последователей вершин: C (X) Xi, S – количество дуг.

S = 0;

x X выполнить: начало

С(x)=0;

t M(x) выполнить: C(x) = C(x) + 1; S = S + C(x);

конец;

Алгоритмы прохождения графа.

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

Имеем граф G = (X, U), X = {x1, x2,…, xn}. Каждое прохождение можно рассматривать как определенную последовательность. Максимальное число прохождений (перестановок) – n!.

Алгоритм прохождения графа в глубину:

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

9

4 6 3

8

7

5

10

5

4

			Определим списки смежности для каждой вершины графа G:
1:	2,		3, 5	2: 1,		3,		4	3: 1, 2,		4,			5		4: 2, 3		5: 1,3
t: 1, 2, 3, 4, 5

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

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

	P
G	G	и | x i | = n i , то количество прохождений такого несвязного графа:
	i
	i 1
n 1	n 2	… n р ( i = 1, 2,…, p).

Пусть граф G = (X, U) задан структурой смежности < М(x 1), М(x 2),…, М(x n)>. Определим Num(x) как массив для регистрации посещений вершин (Num(x)=1, если вершина не посещалась; Num(x)=0, если вершина посещалась). Тогда алгоритм

прохождения графа в глубину будет выглядеть так:
x	X выполнить Num(x)=1;
x X выполнить: если Num(x)=1, то D(x);
Процедура D(x);
начало
	R(V);
	Num(V)=0;
	t M(V) выполнить: если Num(t)=1, то D(t);
конец;
Алгоритм прохождения графа в ширину:
Определим списки смежности для каждой вершины графа G:
1: 2, 3, 5	2: 1,	3,	4	3: 1, 2, 4, 5	4: 2, 3	5: 1,3
t: 1, 2, 3, 4, 5 (для выбранной вершины переписываем весь список смежности).
Выберем начальную вершину x н. Первые элементы искомой перестановки t
являются элементами смежного списка вершины						x н, т.е. M(x н).	Обозначим список
смежности следующим образом: M(x н) = {(w1, xн),						(w2, xн),…,(wk,	xн)}. Следующими

элементами перестановки будут те элементы их M(w1), которые отсутствуют в формируемой перестановке t. Затем, берем все элементы из M(w2), и т.д. обход

прекращается, когда все вершины, достижимые из x н, будут содержаться в t (wi	X,
i=1, 2,…, k).
Топологическая сортировка.

Топологическая сортировка (ТС) вершин орграфа G заключается в присвоении его вершинам чисел 1, 2,…, | x |, причем должно выполняться следующее условие для орграфов: если имеется дуга (xi, xj), то j > i (i j).

Рассмотрим случай для ацикличного графа:

4 3 2 4

							Поиск ведем на множестве узлов
							графа:
	5			3
1		2	1		6	1	2			3	4					5	6
	Топологически			Топологически
	неотсортированный			отсортированный
	граф			граф

Топологическая сортировка может быть использована:

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

2.При организации программных систем. Здесь рассматривается совокупность

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

Рассмотрим алгоритм топологической сортировки. Идея его заключается в том, что осуществляется поиск такой вершины, из которой не выходит ни одна дуга. Такой вершине присваивается | x |. Затем эту вершину выбрасывают вместе с дугами и опять осуществляют поиск на | x | - 1, …

Введем массив LABEL размерностью | x |. Он будет обладать следующими свойствами: если вершина не выброшена, то значение LABEL(x)=0; если есть дуга (xi, xj),

то LABEL(x j) > LABEL(x i).

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

x X выполнить: (Num(x)=1; LABEL(x)=0;) C = | x | + 1;

x X выполнить: если Num(x)=1, то DM(x);

Процедура DM(v); начало

Num(V)=0;

t M(V) выполнить: если Num(t)=1, то DM(t);

конец; C = C – 1;

LABEL(V) = C;

8 Внешняя сортировка и ее особенности. Алгоритм прямого слияния. Анализ и его

усовершенствования. Многофазная сортировка.

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

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

Кнаиболее известным алгоритмам внешних сортировок относятся:

●сортировки слиянием (простое слияние и естественное слияние);

●улучшенные сортировки (многофазная сортировка и каскадная сортировка).

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

Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.

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

В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.

Фаза – это действия по однократной обработке всей последовательности элементов. Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.

Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.

Общий алгоритм сортировки слиянием

Сначала серии распределяются на два или более вспомогательных файлов. Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл, вторая – во второй и так далее до последнего вспомогательного файла. Затем опять запись серии начинается в первый вспомогательный файл. После распределения всех серий, они объединяются в более длинные упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются. Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется. В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл, либо в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. И так до тех пор, пока все данные не будут отсортированы.

Выделим основные характеристики сортировки слиянием:

●количество фаз в реализации сортировки;

●количество вспомогательных файлов, на которые распределяются серии. Рассмотрим основные и наиболее важные алгоритмы внешних сортировок более подробно.

Сортировка простым слиянием

Одна из сортировок на основе слияния называется простым слиянием.

Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки, основанный на процедуре слияния серией.

В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2k.

Алгоритм сортировки простым слиянием

Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.

Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл (рис. 43.1).

После выполнения i проходов получаем два файла, состоящих из серий длины 2i. Окончание процесса происходит при выполнении условия 2i>=n. Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.

Признаками конца сортировки простым слиянием являются следующие условия:

●длина серии не меньше количества элементов в файле (определяется после фазы слияния);

●количество серий равно 1 (определяется на фазе слияния).

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

Поскольку на каждом проходе размерность серии удваивается, то сортировка заканчивается, когда p ³ n, где р – размер серии, а n – размер исходного файла.

Количество проходов: k = [log 2 n]. По определению при каждом проходе все множество из n элементов копируется ровно 1 раз, следовательно общее число пересылок М = n[log 2 n]. Число сравнений С еще меньше, чем М, т.к. при копировании остатка последовательности сравнения не производятся. Поскольку сортировка слиянием использует ВЗУ, то временные затраты на операцию пересылки на несколько порядков превышают временные затраты на операции сравнения.

Улучшение характеристик сортировки можно обеспечить увеличением файлов на фазе разделения и фазе слияния. Обозначим количество файлов – N. Тогда слияние r серий при 1 проходе дает r/N – количество серий, а на k-том проходе r/Nk. Тогда количество проходов будет k = [log N n], а количество пересылок М = n[log N n].

Многофазная сортировка.

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

Рассмотрим пример использования трех файлов fl, f2 и f3. Пусть вначале файл fl содержит 13 серий, файл f2 — 8 серий, а f3 — выходной файл. Рассмотрим сам процесс coртировки.

Сначала 8 серий из файлов f 1 и f2 сливаются и посылаются в f3. Файл f2 оказывается свободным, при очередном проходе туда посылаются 5 серий, полученных от слияния записей из f1 и f3, и т.д. до тех пор, пока все серии не сольются в одну в файле f1.

Сортировка завершена, отсортированные записи в файле f1.

Число проходов при многофазной сортировке будет зависеть от начального распределения серий по входным файлам. Доказано на практике, что для хорошей работы многофазной сортировки с тремя файлами необходимо, чтобы числа начальных серий в двух выходных файлах были двумя соседними числами Фибоначчи.

9 Б-деревья. Определение Алгоритмы поиска, включения и исключения.

Необходимость их применения.

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

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

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

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

Пример. Пусть дерево организовано таким образом, что каждая страница содержит 100 элементов, а вершина, в которой хранится эта страница, имеет 101-го потомка. Тогда поиск в дереве с миллионом элементов будет в среднем требовать log100(106)=3 обращения к страницам, тогда как для двоичного и не разбитого на страницы дерева это число составляет в среднем log2(106)=20 обращений.

Конечно, если дерево растет случайным образом, то в худшем случае может потребоваться и 106/100=104 обращений. Поэтому для сильно ветвящихся деревьев также необходима некоторая схема управления их ростом.

Идеальная сбалансированность требует слишком больших затрат на балансировку. Разумный критерий был сформулирован в 1970 году Р. Бэйером и Е. Маккресттом:

каждая страница (кроме, быть может, корневой) должна содержать при заданном фиксированном n от n до 2n вершин.

Соблюдение этого критерия позволяет осуществить поиск элемента по ключу в дереве с N элементами максимум за lognN обращений к вершинам этого дерева. Кроме того, каждая страница заполнена не менее чем на половину, а значит, коэффициент использования памяти составляет не менее 50%.

Б-деревом называется сильно ветвящееся дерево, обладающее следующими свойствами:

1. При заданном натуральном n каждая страница, кроме корневой, содержит не менее n и не более 2n элементов. Корневая страница может содержать от 1 до 2n элементов.

2. Каждая страница, содержащая m элементов, либо является концевой, либо имеет ровно m+1 потомка.

3. Все концевые вершины находятся на одном уровне.

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

На рис. 1 показан пример Б-дерева при n=2.

Каждая страница Б-дерева организована в виде массива с размерностью [1..2n], причем элементы массива располагаются на странице в порядке неубывания их ключей (рис. 2).

Подобная организация Б-деревьев представляет собой естественное развитие принципа двоичных деревьев и определяет метод поиска элемента с заданным ключом.

Поиск элемента в Б-дереве

Считываем страницу в оперативную память и пользуемся обычным методом поиска среди ключей k1, k2, ... km. Если число m достаточно большое, то можно воспользоваться дихотомическим поиском, в противном случае можно использовать последовательный поиск. Какой вид поиска выбрать - здесь неважно, так как время,

затрачиваемое на поиск в оперативной памяти, как правило, пренебрежимо мало по сравнению с временем пересылки страницы из внешней памяти в оперативную. При поиске элемента с заданным ключом x возможны следующие ситуации:

1.x=ki при некотором i (1<=i<=m): искомый элемент найден;

2.ki<x<ki+1 при некотором i (1<=i<m): поиск продолжается на странице с

адресом pi;

3. x<k1: поиск продолжается на странице с адресом p0;

2. km<x: поиск продолжается на странице с адресом pm.

Если на некотором шаге окажется, что pi=nil, то это означает, что в Б-дереве нет элемента с данным ключом х. В этом случае в ходе поиска несуществующего элемента в оперативную память будет перегружено максимум k= lognN страниц; поэтому значение n необходимо выбрать таким образом, чтобы эти k страниц поместились в оперативную память.

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

Включение элемента в Б-дерево

Включение нового элемента осуществляется только на концевые страницы, т.е. страницы нижнего уровня.

I случай. Новый элемент е нужно поместить на страницу с m<2n элементами. В этом случае процесс включения затрагивает только эту страницу. Алгоритм включения:

1.Установить, что элемент е отсутствует в дереве.

2.Определить страницу и позицию r на странице, в которую следует

поместить элемент е.

3.Сдвинуть на одну позицию вправо элементы этой страницы с r-го по m-й.

4.Вставить новый элемент е в позицию r.

5.Увеличить размер страницы на единицу.

II случай. Новый элемент е нужно поместить на страницу с m=2n элементами. Алгоритм включения:

1.Установить, что элемент е отсутствует в дереве.

2.Определить страницу А в которую следует поместить элемент и

убедиться, что эта страница уже полна.

3.Создать чистую страницу В.

4.Элементы со страницы А вместе с новым элементом е (всего их 2n+1)

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

5. Размеры страниц А и В положить равными n, увеличить на единицу размер родительской страницы.

Если включение в родительскую страницу вновь приводит к переполнению страницу, то разделение надо повторить уже на уровне родительской страницы. В крайнем случае разделение придется проводить на всех уровнях, включая корневой. Фактически только тогда может появиться новая корневая страница, и, следовательно, увеличиться высота Б-дерева. Так что Б-деревья растут несколько странно: от листьев к корню.

Исключение элемента из Б-дерева

I случай. Исключаемый элемент е находится на концевой странице Р. Пусть удаляемый элемент занимает позицию r. Алгоритм исключения:

1.Удалить со страницы Р элемент е.

2.Сдвинуть на одну позицию влево элементы этой страницы с r+1-го по m-й.

3.Уменьшить размер страницы Р на единицу.

II случай. Исключаемый элемент е с ключом ki находится не на концевой странице. В этом случае его следует заменить одним из двух лексикографически смежных

элементов. Поиск смежного элемента похож на поиск при исключении из двоичного дерева: сначала спускаемся вниз влево на дочернюю страницу в направлении ссылки pi-1, а затем продолжаем спускаться вниз вдоль самых правых ссылок до листовой страницы Р. Алгоритм исключения:

1.В качестве смежного элемента взять самый правый элемент со страницы Р.

2.Заменить исключаемый элемент на смежный.

3.Уменьшить размер страницы Р на единицу.

В обоих случаях может оказаться, что размер страницы Р сократился до n-1, т.е. на странице Р осталось недопустимо мало элементов. В этом случае надо попытаться позаимствовать недостающий элемент на соседней с Р странице Q. Если размер страницы Q больше n, то это можно сделать. Более того, уж если приходится вызывать дополнительную страницу в оперативную память, то лучше взять не один, а несколько элементов, распределив элементы страниц Р и Q поровну на обе страницы. Этот процесс, называемый балансировкой страниц, затрагивает также и родительский элемент страниц Р и Q: возможно, что он спустится на одну из этих страниц, а на его место поднимется элемент снизу.

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

10 Оптимальные деревья поиска. Эффективность их применения. Алгоритм построения

оптимального дерева поиска.

Во всех наших рассуждениях по поводу организации деревьев поиска до сих пор исходили из предположения, что частота обращения ко всем вершинам одинакова, т. е. все ключи с одинаковой вероятностью рассматриваются как аргументы поиска. Если нет других, то такое предположение является разумным. Но встречаются ситуации, когда есть информация о вероятности обращения к отдельным ключам. Обычно для таких ситуаций характерно постоянство множества ключей, т. е. в дерево не включаются новые ключи и не исключаются старые. Структура дерева остаѐтся неизменной Типичный пример – сканер транслятора, определяющий не относится ли каждое слово исходного текста программы к классу ключевых для данного языка программирования.

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

Пусть	p	k	- вероятность обращения к k – й вершине дерева ,	pk	1
				k	. Надо так

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

пути каждой вершины некоторый вес, который равен вероятности p k .

Условимся, что корень находится на уровне 1. Тогда средняя длина (среднее значение) пути всего дерева представляет собой сумму всех путей от корня к каждой вершине, умноженной на вероятность обращения к этой вершине.

n

S h p

k k

k 1

где h k – уровень вершины k.
Цель – минимизировать среднее значение l ср.
Пример.
Задано множество ключей {k i} {1 , 2 , 3}, n = 3,	p1		1	,	p2		2	,	p3		4
			7				7				7

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

( 2 n)!		4n
(n +1)(n! )2		3

π n 2

Приблизительное равенство верно при n 10.

		4		2		1 11			4		1		2 12
	a)	1	2		3			d)	1	2		3
		7		7		7 7			7		7		7 7
		1		2		4 17			1		4		2 15
	b)	1	2		3			e)	1	2		3
		7		7		7 7			7		7		7 7

21 4 12

c)1 2 2

77 7 7

При данном распределении вероятностей лучшим является вырожденный вариант ( вариант

а ).

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

k j и k j + 1

Обнаружение, что данное слово не является зарезервированным, можно считать обращением к некоторой специальной вершине.

Если известна вероятность g j того, что аргумент поиска х находится между двумя ключами , эта информация существенно трансформирует структуру дерева оптимального поиска.

Обобщим задачу: учтѐм неудачный поиск. Средняя длина пути в этом случае

- средняя длина пути

( * )

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

hi – уровень внутренних вершин, который начинается с 1.

h	- уровень внешних вершин, который начинается с 0.
j

Эту среднюю длину пути Р называют ценой дерева поиска, т. к. она представляет некоторую меру поиска ожидаемых затрат. Дерево поиска, имеющее минимальную для всех деревьев, заданных множеством ключей {k i} и вероятностями pi и g j, где будет находиться специальная вершина, называется оптимальным деревом.

Вместо вероятностей pi и g j мы будем использовать счѐтчики частоты обращений. Введѐм переменные ai – число поисков с аргументом x = k i;

b j - число поисков с аргументом х , лежащим между ключами k j и k j + 1. b 0 – число поисков с аргументом x < k 1

b n – число поисков с x > k n

n	n
P ah bh		взвешенная длина пути дерева.
i i	j j
i1	j 0

Учитывая, что число возможных конфигураций из n вершин растѐт экспоненциально, задача построения оптимального дерева методом перебора является безнадѐжной. Воспользуемся принципом: любое поддерево оптимального дерева оптимально. Этот принцип подсказывает вычислительную процедуру, с помощью которой находится всѐ большие и большие оптимальные поддеревья, таким образом дерево растѐт от листьев к корню.

В основе этого алгоритма лежит следующее уравнение

					n	m
P = P L + W + P R				,	W a b
					i	j
					i 1	j 0
W – общее количество поисков, вес дерева
P L – взвешенная длина пути левого поддерева
P R – взвешенная длина пути правого поддерева.
Пример.
Р = 8*1 + 5*2 + 3* 3 = 5*1 + 3*2 + 8 + 5 + 3							P = P L + W
					P L	W
Пусть теперь T i j				- оптимальное поддерево , состоящее из вершин
k i + 1 , k i + 2 , … , k j					и частот	a i + 1 , a i + 2	, … , a j ;
b i , b i + 1 , … , b j
T o n		- всѐ дерево
W o n		- вес всего дерева
P o n		- взвешенный путь всего дерева
W i j		- общее число поисков для этого поддерева
P i j		- взвешенный путь для поддерева ( i j )
PWmin[P P]
ij			ij i kj	ik1 kj
0	i < j		n
При начальных условиях Wii = bi						i n
T i i	имеет только специальные вершины.
P i i = 0, 0			i n
W i j = W i j – 1 + a j + b j
O( n 3		) -	сложность вычисления P i j .

Алгоритм Гильберта – Мура.

Введѐм следующие определения:

Дано множество ключей; массив a [i], массив b[ j]. Определить W[ i , j ] , P[ i , j ].

r [ i , j ] – массив для записи значений k (индекс ключа) для поддерева T[ i , j ].
В r o n будет записан ключ корня всего дерева.
Шаг 1	. Начальная установка:
Для i	= 0 , … , n установить P [ i , i ] := 0 ; W [ i , i ] := b [ i ] ;

W [ i , j ] := W [ i , j -1 ] + a [ j ] + b [ j ] при						j = i + 1 , i + 2 , … , n .
Для					– 1 , j ] и r [ j –
Этим определяются все деревья, состоящие из одного узла.
Шаг 2	. Цикл по h . Выполнить шаг 3 для h = 2 , 3 , … , n и закончить алгоритм.
Шаг 3	. Цикл по j . К этому моменту найдены оптимальные деревья с менее, чем h узлами.
Этот шаг определяет все оптимальные деревья с n узлами.
Выполнить шаг 4		при	j = h , h + 1 , … , W.
Шаг 4	. Находятся матрицы			P i j и	r i j .
Установить i = j – h		и	вычислить
		[	]	[	]	[	]	[ ]