Структуры данных и алгоритмы (1021739), страница 45
Текст из файла (страница 45)
Для нахождения длины НОП послевыполнения этого алгоритма надо выполнить FIND(n).Листинг 5.15. Программа нахождения НОП(1)(2)(3)(4)(5)(6)(7)procedure НОП;beginинициализация So= (0, 1, . . . , п) и Sj(= 0 для k от 1 до п;for j:= I to n do { вычисление всех S* для позиции j }for наибольшее число г е PLACES (bj) do begink:= FIND(r) ;if k:= FIND(r-l) then beginSPLIT (Sk, Sk, S'k, r);MERGE (S1*, Sm, S*+i)endendend; { НОП }Анализ времени выполнения алгоритма нахождения НОПКак упоминалось ранее, описываемый алгоритм целесообразно применять тогда,когда между элементами рассматриваемых последовательностей не очень много совпадений.
Число совпадений можно подсчитать по формуле р = ^™J PLACES(by) |, где|PLACES(&;)| обозначает число элементов в множестве PLACES(fy). Другими словами,р — это сумма по всем bj количества позиций в первой последовательности, совпадающих с bj. Напомним, что при сравнении файлов мы ожидали, что р имеет такойпорядок, как длины сравниваемых последовательностей (файлов) т и п .Оказывается, что 2-3 деревья — подходящая структура для множеств St.
Мы можем инициализировать эти множества (строка (1) в листинге 5.15) за О(п) шагов.Для реализации функции FIND необходим массив, осуществляющий отображение измножества позиций в множество листьев дерева, а также указатели на родителей узлов в 2-3 дереве. Имя множества, т.е. h для множества Sk, можно хранить в корнедерева. В этом случае оператор FIND можно выполнить за время O(logn), следуя зауказателями от листа дерева к его корню.
Поэтому все выполнения строк (4) и (5) влистинге 5.15 в совокупности требуют времени порядка О(р logn).Выполняемый в строке (5) оператор MERGE обладает тем свойством, что каждыйэлемент в множестве S\ меньше, чем любой элемент в множестве SA+1, и мы можем5.6. АТД С ОПЕРАТОРАМИ MERGE И SPLIT177воспользоваться этим, применяя 2-3 деревьев для реализации данного оператора1.Вначале оператор MERGE помещает 2-3 дерево множества S't слева от дерева множества S/,+1. Если оба дерева имеют одинаковую высоту, то создается новый корень,сыновьями которого являются корни этих MERGE деревьев. Если дерево множества;S't короче дерева множества S*+1, то корень дерева множества S'k становится самымлевым сыном самого левого узла на соответствующем уровне дерева множества St+iЕсли после этого узел будет иметь четырех сыновей, то дерево модифицируется точнотак же, как и при выполнении процедуры INSERT из листинга 5.11.
Пример подобного объединения деревьев показан на рис. 5.15. Аналогично, если дерево множестваSt+1 короче дерева множества S'k, то корень дерева множества Sk+i становится самымправым сыном самого правого узла на соответствующем уровне дерева множества S'/,.А"6 7S'*8910 11 12 13 14S/r+1а. До реструктуризации6789 10 11 12 13 14Sk+1б. После реструктуризацииРис. 5.15. Пример выполнения оператора MERGEОператор SPLIT, разбивающий множество по элементу г, осуществляет проход подереву от листа, содержащего г, к корню дерева, дублируя по пути все внутренниеузлы, расположенные на пути, и отдавая эти копии узлов двум результирующим деревьям.
Узлы, не имеющие сыновей, исключаются из дерева, а узлы, имеющие поодному сыну, удаляются, вставляя своего сына на соответствующий уровень дерева.Пример 5.9. Предположим, необходимо разбить дерево, изображенное нарис. 5.15,6, по узлу 9. Два дерева с дубликатами узлов, расположенных на пути отлиста 9 к корню, показаны на рис. 5.16,а.
На дереве слева родитель листа 8 имееттолько одного сына, поэтому лист 8 становится сыном родителя узлов 6 и 7. Этот родитель теперь имеет трех сыновей, поэтому все в порядке. Если бы он имел четырехсыновей, то потребовалось бы создать новый узел и вставить его в дерево. Теперь надо удалить узлы без сыновей (старый родитель листа 8) и цепочку из узлов с однимсыном, ведущую к корню дерева. После этих удалений родитель листьев 6, 7 и 8становится корнем дерева, как показано на рис. 5.16,6. Аналогично, на правом дереве рис.
5.16,а лист 9 становится левым братом листьев 10 и 11, лишние узлы удаляются, в результате получаем дерево, показанное на рис. 5.16,6. ПЕсли операция разбиения деревьев и последующая их реорганизация происходяттак-, как описано выше, то можно показать, что в большинстве случаев для выполнения оператора SPLIT потребуется не более O(logn) шагов. Таким образом, общее время выполнения строк (6) и (7) в листинге 5.15 требует О(р logn) шагов. Еще необходимо учесть время, затрачиваемое перед выполнением процедуры НОП на вычисление и сортировку множеств PLACES(a) для всех элементов а. Как уже упоминалось,если элементы а — "большие" объекты (например, текстовые строки), то это времяможет быть больше времени, необходимого на реализацию любой части описываемо; * Строго говоря, мы должны дать другое название этому оператору, поскольку в данномслучае он не объединяет непересекающиеся множества, а работает с деревьями, т.е.
не соответствует названию MERGE.ШГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВго алгоритма. Как будет показано в главе 8, если манипулирование и сравнение элементов можно "уложить" в единичные "шаги", то на сортировку первой последовательности а]а2...а„ потребуется порядка О(п logn) таких шагов, после чего PLACES(a)может быть считан из списка за время О(п). В итоге получаем, что длину НОП можно подсчитать за время порядка О(тах(п, р) logn), которое (поскольку обычно р > п)можно принять как О(р logn).6 7 89 10 11 12 13 14а.
Разделенные деревьяА6 7 89 10 11 12 13 14б. Результат реструктуризацииРис. 5.16. Пример выполнения оператораSPLITУпражнения5.1.5.2.5.3.*5.4.5.5.*5.6.Нарисуйте все возможные деревья двоичного поиска для четырех элементов 1, 2, 3 и 4.Вставьте целые числа 7, 2, 9, 0, 5, 6, 8, 1 в пустое дерево двоичного поиска,повторив действия процедуры INSERT из листинга 5.2.Покажите результат удаления числа 7, а затем числа 2 из дерева, полученногов упражнении 5.2.Если для удаления двух элементов из дерева двоичного поиска используетсяпроцедура из листинга 5.4, то зависит ли вид конечного дерева от порядка, вкотором удаляются элементы?Вы хотите, используя нагруженное дерево, отследить все 5-символьные последовательности, имеющиеся в данной строке. Покажите нагруженное дерево,полученное для 14 последовательностей длины 5, извлеченных из строкиABCDABACDEBACADEBA.Для выполнения примера 5.5 надо в каждом листе, который представляет, например, строку abc.de, хранить указатель на внутренний узел, представляющий (в данном случае) суффикс bcde.
В этом случае, если, например, следую-УПРАЖНЕНИЯ1795.7.5.8.5.9.15.10.5.11.5.12.5.13.5.14.*5.15.*5.16.5.17.180щий символ /, мы не сможем вставить всю последовательность bcdef, начинаяпроцесс от корня. Также отметим, что имея последовательность abcde, можносоздать узлы для последовательностей bcde, cde, de и е, которые в итоге будутнам необходимы.
Измените структуру данных нагруженного дерева для поддержки таких указателей и модифицируйте алгоритм вставки в нагруженноедерево с учетом особенностей этой структуры данных.Нарисуйте 2-3 дерево, которое получится в результате вставки в пустое'множество (представленное как 2-3 дерево) элементов 5, 2, 7, 0, 3, 4, 6, 1, 8, 9.Покажите результат удаления элемента 3 из 2-3 дерева, полученного в упражнении 5.7.Покажите последовательные значения всех множеств S^, которые получаютсяв процессе выполнения алгоритма нахождения НОП из листинга 5.15 присравнении последовательностей abacabada и bdbacbad.Предположим, что мы используем 2-3 дерево для реализации операторовMERGE и SPLIT из раздела 5.6:а) покажите результат разбиения дерева из упражнения 5.7 по элементу 6;б) выполните слияние дерева из упражнения 5.7 с деревом, состоящим из листьев элементов 10 и 11.Некоторые структуры, описанные в этой главе, легко модифицировать дляреализации АТД MAPPING (Отображение). Напишите процедуры MAKENULL,ASSIGN и COMPUTE для их выполнения над АТД MAPPING при использовании следующих структур данных:а) деревья двоичного поиска.
В области определения отображения упорядочьте элементы посредством отношения порядка "<";б) 2-3 деревья. Во внутренних узлах поместите только поле ключей элементовобласти определения.Покажите, что в любом поддереве дерева двоичного поиска минимальный элемент находится в узле без левого сына.Используйте пример 5.12 для создания нерекурсивной версии процедурыDELETEMIN.Напишите процедуры ASSIGN, VALUEOF, MAKENULL и GETNEW для узловнагруженного дерева, представленных в виде списков.Сравните время выполнения операторов и используемое пространство нагруженного дерева (реализуемого как список ячеек), открытой хеш-таблицы и дерева двоичного поиска, если элементы исходного множества являются строками, состоящими не более чем из 10 символов.Если элементы множества упорядочены посредством отношения "<", тогда вовнутренних узлах 2-3 дерева можно хранить один или два элемента (не обязательно ключи), и в этом случае не обязательно, чтобы элементы хранилисьв листьях дерева.
Напишите процедуры INSERT и DELETE для 2-3 дереваэтого типа.Другая модификация ,2-3 деревьев предполагает хранение во внутренних узлах дерева только ключей ki и k2, но не обязательно именно минимальныхключей второго и третьего поддеревьев. Требуется только, чтобы все ключи kтретьего поддерева удовлетворяли неравенству k ^ k2, все ключи k второгоподдерева — неравенствам ki < k < h^, а для всех ключей k первого поддерева выполнялось k < ftj.а) как в рамках этих соглашений упростить реализацию оператора DELETE?б) какие из операторов словарей и отображений при использовании таких 2-3деревьев будут выполняться более эффективно, а какие менее?ГЛАВА 5.
СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ*5.18. Еще одной структурой данных, которая поддерживает словари с операторомMIN, являются АВЛ-деревья (названные так в честь авторов Г.М. АдельсонаВельского и Е.М. Ландиса), или деревья, сбалансированные по высоте. Эти деревья являются деревьями двоичного поиска, у которых для каждого узла высоты его правого и левого поддеревьев отличаются не более чем на единицу.Напишите процедуры реализации операторов INSERT и DELETE при использовании АВЛ-деревьев.5.19. Напишите на языке Pascal программу для процедуры insert], из листинга 5.12.*5.20. Конечный автомат состоит из множества состояний, которые мы будем обозначать целыми числами от 1 до п, таблицы переходноетояние, вход], котораядля каждого состояния и для каждого символа вход определяет следующее состояние. Предположим, что входом всегда является или 0 или 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
