Главная Промышленная автоматика.

листинге 5.7. Написание процедур MAKENULL, DELETE и PRINT для данной реализации нагруженных деревьев оставляем в качестве упражнений для читателей.

Листинг 5.7. Процедура INSERT

procedure INSERT ( X: wordtype; var words: TRIE ) ; var

i ! integer; { считает позиции в слове х } С: TRIE; { используется для указания на узлы дерева, соответствующие гфефиксу слова х }

begin

i:= 1; t:= words;

while x[i] <> $ do begin

if VALUEOFltT, x[i]) = nil then

{ если текущий узел не имеет сьиа для

символа х[1], то он создается } GETNEW{tT, x[i]); t:= VALUEOF{tT, x[i] ) ;

{ продвижение к сыну узла t для символа x[i] } i:= i + 1 { перемещение далее по слову х }

end;

{ в слове X достигнут первый символ $ } ASSIGN ( tT, $ , t)

{ делает петлю на $ для создания листа } end; { INSERT }

Представление узлов нагруженного деревапосредствомсписков

Множество слов, которые имеют р различных префиксов и для хранения требуют 27р байт, можно представить посредством реализации узлов нагруженного дерева с помощью массивов фиксированной длины. Величина 27р байт может значительно превыщать общую длину слов в множестве. Существует другая реализация нагруженных деревьев, которая экономит используемый объем памяти. Напомним, что мы рассматриваем каждый узел нагруженного дерева как отображение (см. раздел 2.6). В принципе, можно применить любую реализацию отображений, но мы хотим найти наиболее подходящую, область определения которых сравнительно мала. При таком условии наилучщим выбором будет реализация отображения посредством связанных списков. Здесь представлением отображения, т.е. узла нагруженного дерева, будет связанный список символов, для которых соответствующие значения не являются указателями nil. Такое представление можно сделать с помощью следующего объявления:

type

celltype = record domain: chars;

value: Tcelltype;

{ указатель на первую ячейку списка узла сьиа } next: Tcelltype

{ указатель на следующую ячейку списка }

end;

Мы оставляем в качестве упражнений написание для данной реализации процедур ASSIGN, VALUEOF, MAKENULL и GETNBW. После создания этих процедур процедура INSERT из листинга 5.7 должна стать работоспособной программой.



Эффективность структуры данных нагруженныхдеревьев

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

Сами слова хранятся в большом символьном массиве, где начало и конец каждого слова помечается специальным маркером, таким как $. Например, слова THE, THEN и THIN будут храниться как

ТПЕ$ТПЕК$ТПШ$ . . .

Указателями для этих слов будут курсоры, указывающие на позиции 1, 5 и 10 массива. Подсчитаем пространство, занимаемое сегментами хеш-таблицы и массивом символов.

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

2. I + п байт для символьного массива, хранящего п слов общей длиной / и п разделителей слов.

Таким образом, общее занимаемое пространство составляет 9га -i- I плюс пространство, используемое для заголовков сегментов.

Для сравнения: нагруженное дерево с узлами, представленными связанными списками, требует р + п ячеек - по одной ячейке на каждый префикс и по одной ячейке на каждое окончание слова. Каждая ячейка содержит символ и два указателя, т.е. всего 9 байт. Поэтому общее занимаемое пространство составляет 9р + 9га байт. Если I и пространство заголовков сегментов больше 9р, то нагруженное дерево занимает меньше пространства, чем хеш-таблица. По в реальных приложениях, таких как словари, отношение робычно меньше 3, поэтому в этих приложениях хеш-таблицы более экономичны.

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

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



5.4. Реализация множеств посредством сбалансированныхдеревьев

в разделах 5.1 и 5.2 мы рассмотрели способы представления множеств посредством деревьев двоичного поиска и узнали, что операторы, подобные INSERT, выполняются за время, пропорциональное средней длине пути в этом дереве. Затем мы показали, что средняя глубина узлов составляет O(logra) для "случайного" дерева из п узлов. Однако некоторые последовательности операций вставки и удаления узлов дерева могут привести к деревьям двоичного поиска, чья средняя глубина будет пропорциональна п. Это наводит на мысль попытаться после каждой вставки или удаления реорганизовать дерево так, чтобы оно всегда бьшо полно, тогда время выполнения оператора INSERT и других подобных операторов всегда будет иметь порядок O(logra).

На рис. 5.5,а показано дерево из шести узлов, а на рис. 5.5,6 - то же дерево (уже полное) после вставки седьмого узла с элементом 1. Но обратите внимание, что каждый узел на рис. 5.5,6 имеет другого родителя, отличного от родителя, изображенного на рис. 5.5,а. Отсюда следует, что надо сделать л шагов при вставке элемента 1, чтобы сохранить дерево по возмокности сбалансированным. Это значительно хуже, чем в случае простой вставки в полное дерево двоичного поиска при реализации словарей, очередей с приоритетами и других АТД, где оператор INSERT (и другие ему подобные) требует времени порядка 0(log7i).





2 4 6 1 3 5 7

Рис. 5.5. Полные деревья

Сушествуют другие подходы к реализации словарей и очередей с приоритетами, где даже в самом худшем случае время выполнения операторов имеет порядок O(logn). Мы подробно рассмотрим одну из таких реализаций, которая называется 2-3 дерево и имеет следуюшие свойства.

1. Каждый внутренний узел имеет или два, или три сына.

2. Все пути от корня до любого листа имеют одинаковую длину.

Будем считать, что пустое дерево и дерево с одним узлом таюке являются 2-3 деревьями.

Рассмотрим представления множеств, элементы которых упорядочены посредством некоторого отношения линейного порядка, обозначаемого символом "<". Элементы множества располагаются в листьях дерева, при этом, если элемент а располагается левее элемента Ъ, справедливо отношение а < Ь. Предполагаем, что упорядочивание элементов по используемому отношению линейного порядка основьтается только на значениях одного поля (среди других полей записи, содержашей информацию об элементе), которое формирует тип элементов. Это поле назовем ключом. Например, если элементы множества - работники некоторого предприятия, то ключевым полем может быть поле, содержашее табельный номер или номер карточки социального страхования,

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 [48] 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0037