Структуры данных и алгоритмы (1021739), страница 38
Текст из файла (страница 38)
Усредняя эти выражения по всем i от 0 до п - 1, получим рекуррентноеуравнениеР(п) = 1 +n4-£ (iPO) + (n-i- l)P(n - i - 1)).(5.1)1=0Вторая часть этой суммы ^Г"=о (n — i- l)P(n - i - 1) , если подставить i вместо(п - i - 1), преобразуется в первую часть (5.1) 2^"=0 iP(i) • В последней сумме слагаемое при i = 0 равно нулю, поэтому суммирование можно начинать с i = 1. Таким образом, формулу (5.1) можно переписать в следующем виде:Р(п) = 1 + 4-S^W, п > 2.П(5.2)i,iТеперь индукцией по п покажем, что Р(п) < 1 + 41ogra. Очевидно, что это утверждение справедливо для п = 1, поскольку Р(1) = 1, и для п = 2, так какР(2) = 2 < 1 + 41og2 = 5. Предположим, что оно выполняется для всех i < п.
Тогда на основании (5.2) имеем<2 + ^^ilogi.га j-i(5.3)Здесь использовано неравенство ^ " = i i < n 2 / 2 , поэтому — ^£"=1 i ^ l . Разделимпоследнюю сумму в (5.3) на две суммы: по i < [га/2], в этом случае слагаемые не будут превышать ilog(ra/2), и по i > [га/2], где слагаемые не превышают ilog(ra). Тогданеравенство (5.3) можно переписать так:Q-^Yilog(ra/2)+2л-Уilogra .(5.4)Независимо от того, четное или нечетное га, нетрудно показать, что первая суммав (5.4) не превышает величины (ra2/8)log(ra/2), которая равна (ra2/8)logra - (п2/8), авторая не превышает (3n2/8)logn. С учетом этих оценок из (5.4) получаемР(га)<2 + 4-( — logra-— | < l + 41ogn.га I 281\/Этот шаг завершает индукцию и доказывает утверждение. Итак, доказано, что в дереве двоичного поиска, которое получено путем случайной вставки га элементов, средняя5.2.
АНАЛИЗ ВРЕМЕНИ ВЫПОЛНЕНИЯ ОПЕРАТОРОВ151длина пути от корня до произвольного узла имеет порядок O(logn), т.е. точно такой жепорядок (с точностью до константы пропорциональности), как и для полного двоичногодерева. Более точный анализ показывает, что константу 4 в вышеприведенной оценкеможно заменить на 1.4.Из доказанного утверждения следует, что время выполнения проверки на принадлежность произвольного элемента к множеству имеет порядок O(logn).
Подобныйанализ показывает, что если мы включим в путь только те узлы, которые имеютобоих сыновей, или только узлы, имеющие лишь левого сына, то все равно для средней длины пути получим уравнение, подобное (5.1), и поэтому будет оценка порядкаO(logn). Отсюда следует вывод, что для выполнения операций проверки на принадлежность к множеству элемента, которого заведомо нет в множестве, вставки произвольного нового элемента или удаления элемента также требуется в среднем временипорядка O(logn).Эффективность деревьев двоичного поискаПри реализации словарей посредством хеш-таблиц время выполнения основныхоператоров в среднем постоянно, т.е. практически не зависит от размера множеств.Поэтому такая реализация более эффективна, чем реализация деревьев двоичногопоиска, за исключением того случая, когда необходимо часто применять операторMIN, который требует времени порядка О(п) для хеш-таблиц.Сравним деревья двоичного поиска с частично упорядоченными деревьями, которые применяются для реализации очередей с приоритетами (см.
главу 4). Частичноупорядоченные деревья из п элементов требуют только O(logn) шагов для выполнения операторов INSERT и DELETEMIN, но не в среднем, а в самом худшем случае.Более того, константа пропорциональности перед logn для частично упорядоченныхдеревьев меньше, чем для деревьев двоичного поиска. Но на дереве двоичного поискамогут выполняться как операторы DELETE и MIN, так и их комбинацияDELETEMIN, тогда как на частично упорядоченном дереве выполняется только последний из этих операторов. Кроме того, оператор MEMBER требует О(п) шагов начастично упорядоченном дереве, но только O(logTi) шагов на дереве двоичного поиска.
Таким образом, частично упорядоченные деревья хорошо подходят для реализации очередей с приоритетами, но не эффективны при выполнении других операторовмножеств, которые могут выполняться на деревьях двоичного поиска.5.3. Нагруженные деревьяВ этом разделе мы рассмотрим специальную структуру для представления множеств, состоящих из символьных строк. Некоторые из описанных здесь методов могут работать и со строками объектов другого типа, например со строками целых чисел. Эта структура называется нагруженными деревьями1 (tries). Рассмотрим ихприменение к символьным строкам.1В оригинале структура называется trie, это слово получено из букв, стоящих в середине слова "retrieval" (поиск, выборка, возврат).
Устоявшегося термина для этой структуры в русской литературе пока нет. (О расхождении терминологии можно судить по переводу известной книги D£.Knuth. The art of computer programming, Vol. Ill: Sorting and Searching: в первом русском переводе (Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. — М., "Мир",1978 г.) вместо trie используется термин бор (от слова выборка), в последнем переводе переработанного издания этой книги (Кнут Д.
Искусство программирования. Т. 3: Сортировка и поиск. —М., Издательский дом "Вильяме", 2000 г.) — термин луч (от слова получение).) Чтобы не заниматься "терминотворчеством", мы применили известный термин нагруженные деревья, которыйсоответствует смыслу этой структуры. В данном случае можно было бы применить и термин синтаксические деревья, но, хотя этот термин по своему значению и "пересекается" с термином нагруженные деревья, он имеет другую направленность.
— Прим. ред.152ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВПример 5.2. Как описывалось в главе 1, возможная реализация проверки орфографии состоит из следующей последовательности действий: сначала читается словоиз текстового файла с остановкой после каждого слова (слова отделяются друг отдруга пробелом или символом новой строки), далее проверяется, есть ли это слово встандартном словаре наиболее употребительных слов.
Слова, отсутствующие в словаре, распечатываются как возможные ошибки. В листинге 5.5 приведен эскиз возможной программы spell (правописание). Здесь использована процедура getword(x, f),которая читает следующее слово в текстовом файле / и присваивает его переменнойх, имеющей тип wordtype (мы определим его позже). Еще одна используемая переменная А имеет знакомый нам тип SET. Реализация этого АТД использует операторыINSERT, DELETE, MAKENULL и PRINT. Последний оператор распечатывает элементы множества. ПЛистинг 5.5. Программа проверки орфографииprogram spell ( input, output, dictionary );typewordtype = { надо определить }SET = { надо определить, используя структурунагруженного дерева }varA: SET; { хранит считанное слово, пока ононе найдено в словаре }nextword: wordtype;dictionary: file of char;procedure getword ( var x: wordtype; f: file of char );{ читает следующее слово в файле f иприсваивает его переменной х }procedure INSERT ( х: wordtype; var S: SET ) ;{ надо определить }procedure DELETE ( x: wordtype; var S: SET );{ надо определить }" .
' -• <, • • ;procedure MAKENULL ( var S: SET ) ;{ надо определить }procedure PRINT ( var S: SET );{ надо определить }beginMAKENULL(A);while not eof(input) do begingetword(nextword, input);INSERT(nextword, A)end;while not eof(dictionary) do begingetword (nextword,- dictionary) -,DELETE(nextword, A)end;PRINT(A)end; { spell }Структура нагруженных деревьев поддерживает операторы множеств, у которых элементы являются словами, т.е. символьными строками. Удобно, когда5.3. НАГРУЖЕННЫЕ ДЕРЕВЬЯ153большинство слов начинается с одной и той же последовательности букв или, другими словами, когда количество различных префиксов значительно меньше общейдлины всех слов множества.В нагруженном дереве каждый путь от корня к листу соответствует одному словуиз множества.
При таком подходе узлы дерева соответствуют префиксам слов множества. Чтобы избежать коллизий слов, подобных THE и THEN, введем специальный символ $, маркер конца, указывающий окончание любого слова. Тогда толькослова будут словами, но не префиксы.Пример 5.3. На рис. 5.4 показано нагруженное дерево слов {THE, THEN, THIN,THIS, TIN, SIN, SING}. Здесь корень соответствует пустой строке, а два его сына —префиксам Т и S. Самый левый лист представляет слово THE, следующий лист —слово THEN и т.д. ОРис. 5.4.
Нагруженное деревоНа основании рис. 5.4 можно сделать следующие выводы.1.2.3.Каждый узел может иметь до 27 сыновей1, которые могут быть буквами илисимволом $.Большинство узлов имеет значительно меньше 27 сыновей.Листом может быть только окончание ребра, помеченного символом $.Узлы нагруженного дерева как АТДМы можем рассматривать узел нагруженного дерева как отображение, где областью определения будет множество {А, В, .... Z, $} (или другой выбранный алфавит),а множеством значений — множество элементов типа "указатель на узел нагруженного дерева".
Более того, так как дерево можно идентифицировать посредством егокорня, то АТД TRIE (Нагруженное дерево) и TRIENODE (Узел нагруженного дерева)имеют один и тот же тип данных, хотя операторы, используемые в рамках этихАТД, имеют существенные различия. Для реализации АТД TRIENODE необходимыследующие операторы.1.2.Процедура ASSIGN(raode, с, р), которая задает значение р (указатель на узел)символу с в узле node,2Функция VALUEOF(noefe, с) — возвращает значение (указатель на узел), ассоциированное с символом с в узле node.1Здесь предполагается, что алгоритм работает только с английским алфавитом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
