Теория экономических информационных систем - Мишенин А. И

ными латинскими буквами). Деревья обычно формируются двунаправленными, адрес связи от записи уровня i+1 к записи i-ro уровня называется обратным.

При размещении дерева в памяти ЭВМ каждая запись мо­ жет занимать произвольное место.

Назовем звеном связи набор адресов связи, принадлежа­ щих одной записи. Если порядок дерева равен р, то звено связи состоит из р+1 адресов (один адрес обратный, опреде­ ляющий связь с записью непосредственно более высокого уровня). Корень дерева адресуется из специального указате­ ля дерева. Незанятые адреса связи содержат признак конца списка. В качестве примера размещения дерева в памяти ЭВМ на рис. 3.6,6 показан один из возможных вариантов представления дерева с рис. 3.6,а, обратные адреса связи не показаны.

Рассмотрим деревья порядка 2 (бинарные). Они интерес­ ны тем, что составляющие их записи могут быть упорядоче­ ны. Для этого один из атрибутов записи должен быть объяв­ лен ключевым.

Чтобы определить понятие упорядоченности бинарных деревьев, требуется ввести ряд новых понятий. В качестве при­ мера рассмотрим бинарное дерево на рис. 3.7 (внутри показа­ ны значения ключевого атрибута). Запись А - корень дерева. Записи, у которых заполнены два адреса связи, называются полными, записи с одним заполненным адресом - неполными, записи с двумя незаполненными адресами - концевыми. На рис. 3.7 записи А, В, Е, F - полные, С - неполная, D, H, I, J, К - концевые. Адреса связи делятся на левые и правые. Так, адрес от Е к Н - левый, от Е к I - правый. Каждая запись имеет левую и правую ветви. Правую (левую) ветвь записи образует подде­ рево, адресованное из этой записи через правый (левый) адрес связи. У записи С правая ветвь состоит из записей F, I, К, ле­ вая ветвь пустая.

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

Рис. 3.7. Пример бинарного дерева

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

Упорядоченное бинарное дерево формируется из неупоря­ доченного массива записей по специальному алгоритму. Этот алгоритм создает дерево из первой записи массива, затем - дерево из первых двух записей, из первых трех записей и так далее до исчерпания всех записей массива.

Алгоритм построения упорядоченного бинарного дерева

1. Первая запись массива с ключом р(1) становится корнем дерева.

2. Значение ключа второй записи р(2) сравнивается с р(1), находящимся в корне дерева. Если р(2)<р(1), то вторая запись помещается на левой от корня ветви, в противном случае - на правой ветви. Сейчас получено упорядоченное дерево из пер­ вых двух записей, далее на каждом шаге создается упорядо­ ченное дерево из первых i записей.

3. Выбор места i-й записи массива производится следую­ щим образом. Ключ p(i) сравнивается с корневым значением, и выполняется переход по левому адресу (если p(l)>p(i)), а при p(l)<=p(i) - по правому адресу. Ключ достигнутой записи так­ же сравнивается с p(i), и снова организуется переход по лево­ му или правому адресу и т. д. Когда будет достигнут незапол­ ненный адрес связи, то он должен адресовать запись с ключом p(i). Указанные действия повторяются до исчерпания всех за­ писей исходного массива.

Например, упорядоченное дерево на рис. 3.7 получается из массива записей с ключевыми атрибутами 23, 10, 18, 27, 15,32, 8,30,32,21.

В процессе поиска данных по совпадению в упорядочен­ ном бинарном дереве просматривается некоторый путь по де­ реву, начинающийся всегда в его корне. Искомое значение ключа q сравнивается со значением корня р(1). Если p(l)>q, просмотр дерева продолжается по левой ветви корня, если p(l)<=q - по правой. Для произвольной записи дерева с клю­ чом p(i) результаты сравнения означают:

• p(i)=q - запись, удовлетворяющая условию поиска, най­ дена, и поиск продолжается по правой ветви p(i);

• p(i)>q - производится переход к записи, расположенной на левой ветви p(i);

• p(i)<q - производится переход к записи, расположенной на правой ветви p(i).

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

Для определения среднего числа сравнений при поиске за­ писи в упорядоченном бинарном дереве рассмотрим ситуацию, когда требуемая запись не найдена, что равноценно вставке записи с искомым значением в дерево. Ненайденный ключ может с одинаковой вероятностью попасть в один из М+1 интервалов, образованных ключами, находящимися в дереве. Неудачный поиск закончится всегда на нулевом адресе связи.

Если обозначить через Е(М) сумму длин всех ветвей дерева с учетом выхода на нулевые адреса связи, то среднее число срав­ нений при поиске в упорядоченном бинарном дереве С'(М) составит

Дерево с М-1 вершиной отличается от дерева с М верши­ нами, полученного из него, отсутствием одной концевой за­ писи или (применительно к величине Е) двумя нулевыми ад­ ресами связи. Поэтому Е (М) - Е (М -1) =2. Вычислим разность

dL = С'(М) - С'(М-1)= ——- - — = 2/(М+1). М+1

Математическое ожидание средней длины пути при поис­ ке С'(М) равно сумме математических ожиданий dL от 1 до М. Приближенно заменяя суммирование интегрированием, получаем:

При замене натурального логарифма на двоичный (1п2 = 0,7) получаем оценку числа сравнений при поиске в упо­ рядоченном бинарном дереве:

С = 1,4 log М или С - log M.

При формировании упорядоченного бинарного дерева в среднем производится

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

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

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

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

Способ нахождения соседней справа записи очень простой. Если исключаемая запись имеет ключ q, то от нее происходит переход по правой ветви дерева и нроизводится поиск от дос­ тигнутой записи значения q. Запись, на которой остановится поиск, будет соседней. Она пересылается на место исключае­ мой записи, а сама соседняя запись исключается. Это уже про­ стая задача, так как соседняя запись не может быть полной.

При поиске соседней слева записи надо выполнить переход по левой ветви от данной записи (с ключом q), а дальнейшие действия такие же, как и для поиска соседней справа записи.

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

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

буквами, а списки заключаются в круглые скобки. Список, включенный в другой список, называется подсписком. Пере­ числение всех списков из записей al, a2. aN, образующих множество L0, сводится к следующему.

Обозначим через Li' множество всех кортежей с элемента­ ми из Li. Введем последовательность множеств:

L1=L0'+L0 (+ здесь означает знак объединения множеств) L2=L1'+L1

Все списки содержатся в множестве L=L0+Ll+. Li+.

Пусть L0= . Тогда LI =

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

Все линейные списки содержатся в множестве L0'. Записи, входящие в список, могут занимать произволь­

ные участки в памяти ЭВМ. Адреса связи, принадлежащие каждой записи, образуют звено связи. В звене связи однонап­ равленного списка два адреса: первый указывает на следую­ щий элемент списка, второй - на подсписок или запись. В звене связи двунаправленного списка четыре адреса связи: два из них обеспечивают прямое и обратное направление в списке, третий и четвертый адресуют начало н конец под­ списка. Однонаправленный список ((a,b),b,((c),c)) показан на рис. 3.8.

Дерево тоже имеет формулу, так как существует эквива­ лентный ему список,

Рис. 3.8. Представление списка ((a, b), b, ((с,) с)) в памяти ЭВМ

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

В табл. 3.1 собраны все оценки методов организации дан­ ных, что позволяет сделать ряд выводов.

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