Структуры данных и алгоритмы (1021739), страница 39
Текст из файла (страница 39)
—Прим. ред.2Эта функция является версией функции COMPUTER из раздела 2.5.154ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ3.Процедура GETNEW(node, с) делает значение узла node с символом с указателемна новый узел.Нам также будет необходима процедура MAKENULL(node), делающая узел nodeпустым отображением.Самой простой реализацией узлов нагруженного дерева будет массив node указателей на узлы с индексным множеством {А, В, ..., Z, $}. Таким образом, АТДTRIENODE можно определить следующим образом:typechars = { ' А 1 , ' В 1 , ..., ' Z 1 , ' $ ' } ;TRIENODE = array[chars] of T TRIENODE;Если node — массив узлов, то node[c] совпадает с VALUEOF(node, с) для любогосимвола с.
Чтобы избежать создания многочисленных листьев, являющихся потомками '$', примем соглашение, что node['$'] имеет значение nil или указателя на самого себя. (При формировании дерева node не может иметь сына, соответствующего'$', но после возможных преобразований может появиться такой сын, которого мыникогда не создавали.) Теперь можно написать процедуры, выполняемые над узламинагруженного дерева. Их код приведен в следующем листинге.Листинг 5.6.
Операторы узлов нагруженного дереваprocedure MAKENULL ( var node: TRIENODE );{ делает node листом, т.е. пустым отображением }varс: chars;beginfor c:= 'A' to '$' donode[с]:= nilend; { MAKENULL }procedure ASSIGN { var node: TRIENODE; c: chars; p: tTRIENODE );beginnode[c]:= pend; { ASSIGN }function VALUEOF ( var node: TRIENODE; c: chars ): tTRIENODE;beginreturn(node[c])end; { VALUEOF }procedure GETNEW ( var node: TRIENODE; c: chars );beginnew(node[c]);MAKENULL(node[c])end; { GETNEW }Теперь определим АТД TRIE:typeTRIE = tTRIENODE;Мы можем определить тип wordtype как массив символов фиксированной длины.Предполагается, что среди значений такого массива обязательно есть по крайней мере один символ '$'. Считаем, что концу слова соответствует первый символ '$', независимо от того, что за ним следует.
При выполнении этих предположений написанапроцедура INSERT(*, words), которая вставляет слово х в множество words (слова),представленное посредством нагруженного дерева. Код этой процедуры показан в5.3. НАГРУЖЕННЫЕ ДЕРЕВЬЯ155листинге 5.7. Написание процедур MAKENULL, DELETE и PRINT для данной реализации нагруженных деревьев оставляем в качестве упражнений для читателей.Листинг 5.7. Процедура INSERTprocedure INSERT ( х: wordtype; var words: TRIE );varinteger; { считает позиции в слове х }'TRIE; { используется для указания на узлы дерева,соответствующие префиксу слова х }begini:= 1;t:= words;while x[i] <> '$' do beginif VALUEOFftt, x[i]) = nil then{ если текущий узел не имеет сына длясимвола x[i], то он создается }GETNEW(tt, x[i]);t:= VALUEOFttT, x[i]);{ продвижение к сыну узла t для символа х[1] }i:= i + 1 { перемещение далее по слову х }end;{ в слове х достигнут первый символ '$' }ASSIGN(tt, '$', t){ делает петлю на '$' для создания листа }end; { INSERT }Представление узлов нагруженного дерева посредством списковМножество слов, которые имеют р различных префиксов и для хранения требуют 27р байт, можно представить посредством реализации узлов нагруженногодерева с помощью массивов фиксированной длины.
Величина 27р байт может значительно превышать общую длину слов в множестве. Существует другая реализация нагруженных деревьев, которая экономит используемый объем памяти. Напомним, что мы рассматриваем каждый узел нагруженного дерева как отображение (см. раздел 2.6). В принципе, можно применить любую реализациюотображений, но мы хотим найти наиболее подходящую, область определения которых сравнительно мала. При таком условии наилучшим выбором будет реализация отображения посредством связанных списков. Здесь представлением отображения, т.е.
узла нагруженного дерева, будет связанный список символов, для которых соответствующие значения не являются указателями nil. Такое представление можно сделать с помощью следующего объявления:typecelltype = recorddomain: chars;value: Tcelltype;{ указатель на первую ячейку списка узла сына }next: Tcelltype{ указатель на следующую ячейку списка }end;Мы оставляем в качестве упражнений написание для данной реализации процедур ASSIGN, VALUEOF, MAKENULL и GETNEW. После создания этих процедурпроцедура INSERT из листинга 5.7 должна стать работоспособной программой.156ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВЭффективность структуры данных нагруженных деревьевДля хеш-таблиц и нагруженных деревьев сравним необходимое время выполнения операторов и занимаемый объем памяти для представления п слов с р различными префиксами и общей диной слов I.
Будем предполагать, что указатели требуютдля своего хранения по 4 байт на указатель. По всей видимости, наиболее эффективными по критерию требуемой памяти и поддержке операторов INSERT и DELETEбудут хеш-таблицы. Если слова имеют разную длину, то ячейки сегментов хештаблицы не будут непосредственно содержать слова, а только два указателя. Одинтребуется для связи ячеек сегмента, а другой будет указывать на начало слова, соответствующего сегменту.Сами слова хранятся в большом символьном массиве, где начало и конец каждогослова помечается специальным маркером, таким как '$'. Например, слова THE,THEN и THIN будут храниться какTHE$THEN$THIN$ .
. .Указателями для этих слов будут курсоры, указывающие на позиции 1, 5 и 10 массива. Подсчитаем пространство, занимаемое сегментами хеш-таблицы и массивомсимволов.1.8га байт для ячеек сегментов — по одной ячейке на слово. Ячейка содержит двауказателя, т.е. занимает 8 байт, которые умножаются на п (количество слов).2. I + п байт для символьного массива, хранящего п слов общей длиной I и п разделителей слов.Таким образом, общее занимаемое пространство составляет 9га + I плюс пространство,используемое для заголовков сегментов.Для сравнения: нагруженное дерево с узлами, представленными связанными списками, требует р + п ячеек — по одной ячейке на каждый префикс и по одной ячейке на каждое окончание слова. Каждая ячейка содержит символ и два указателя, т.е.всего 9 байт.
Поэтому общее занимаемое пространство составляет 9р + 9п байт. ЕслиI и пространство заголовков сегментов больше 9р, то нагруженное дерево занимаетменьше пространства, чем хеш-таблица. Но в реальных приложениях, таких каксловари, отношение l/р обычно меньше 3, поэтому в этих приложениях хеш-таблицыболее экономичны.С другой стороны, к достоинствам нагруженных деревьев можно отнести возможность перемещения по дереву и выполнения таких операторов, как INSERT,DELETE и MEMBER, за время, пропорциональное длине "обслуживаемого" слова.Хеш-функция, чтобы быть действительно "случайной", хеширует каждый символслова.
Поэтому ясно, что вычисления хеш-функции требуют примерно такого жевремени, как и выполнение, например, оператора MEMBER для нагруженногодерева. И, конечно, время вычисления хеш-функции не включает время, необходимое для разрешения коллизий или выполнения операций вставки, удаленияили поиска. Поэтому мы вправе ожидать, что нагруженные деревья будут работать значительно быстрее со словарями, состоящими из символьных строк, чемхеш-таблицы.Другим достоинством нагруженных деревьев является то, что, в отличие от хештаблиц, они поддерживают эффективное выполнение оператора MIN.
Кроме того, если хеш-таблица построена так, как описано выше, то после удаления слова из словаря здесь нельзя сравнительно просто организовать повторное использование освободившегося пространства в массиве символов.5.3. НАГРУЖЕННЫЕ ДЕРЕВЬЯ1575.4. Реализация множеств посредствомсбалансированных деревьевВ разделах 5.1 и 5.2 мы рассмотрели способы представления множеств посредствомдеревьев двоичного поиска и узнали, что операторы, подобные INSERT, выполняютсяза время, пропорциональное средней длине пути в этом дереве.
Затем мы показали, чтосредняя глубина узлов составляет O(logra) для "случайного" дерева из п узлов. Однаконекоторые последовательности операций вставки и удаления узлов дерева могут привести к деревьям двоичного поиска, чья средняя глубина будет пропорциональна п. Этонаводит на мысль попытаться после каждой вставки или удаления реорганизовать дерево так, чтобы оно всегда было полно, тогда время выполнения оператора INSERT идругих подобных операторов всегда будет иметь порядок O(logn).На рис. 5.5,а показано дерево из шести узлов, а на рис. 5.5,6 — то же дерево (ужеполное) после вставки седьмого узла с элементом 1. Но обратите внимание, что каждый узел на рис.
5.5,6 имеет другого родителя, отличного от родителя, изображенного на рис. 5.5,а. Отсюда следует, что надо сделать л шагов при вставке элемента 1,чтобы сохранить дерево по возможности сбалансированным. Это значительно хуже,чем в случае простой вставки в полное дерево двоичного поиска при реализации словарей, очередей с приоритетами и других АТД, где оператор INSERT (и другие емуподобные) требует времени порядка O(logn).72461а357бРис. 5.5. Полные деревьяСуществуют другие подходы к реализации словарей и очередей с приоритетами,где даже в самом худшем случае время выполнения операторов имеет порядокO(logrc).
Мы подробно рассмотрим одну из таких реализаций, которая называется 2-3дерево и имеет следующие свойства.1. Каждый внутренний узел имеет или два, или три сына.2. Все пути от корня до любого листа имеют одинаковую длину.Будем считать, что пустое дерево и дерево с одним узлом также являются 2-3 деревьями.Рассмотрим представления множеств, элементы которых упорядочены посредством некоторого отношения линейного порядка, обозначаемого символом "<". Элементы множества располагаются в листьях дерева, при этом, если элемент а располагается левее элемента Ъ, справедливо отношение а < Ь. Предполагаем, что упорядочивание элементов по используемому отношению линейного порядка основываетсятолько на значениях одного поля (среди других полей записи, содержащей информацию об элементе), которое формирует тип элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
