Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 50

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 50)

Добавляется третий параметр Ь; ои указывает, изменилась ли структура поддерева с корнем р, н полностью соответствует параметру Ь в программе поиска в В-дереве. Однако нужно отметить последствия представления «страниц» в виде связанных списков: проход любой страницы происходит с помощью одного или двух обращений к процедуре поиска. Мы должны различать два случая: когда поддерево (обозначенное вертикальной ссылкой) выросло, и когда узел-брат (обозначенный горизонтальной ссылкой) получил другого брата и, следовательно, требуется расщепление. Эта проблема легко решается введением следующих трех значений Ь: 1. Ь = 0; никаких изменений структуры дерева не требуется.

2. Ь = 1: узел р получил брата. 3. Ь = 2: поддерево р увеличилось в высоте. Заметим, что действия, предпринимаемые для переупорядочения узлов, очень напоминают те, которые были разработаны для алгоритма поиска в сбалансированном дереве (4.63). Из (4.87) видно, что все четыре случая можно реализовать простыми поворотами ссылок: однократными поворотами налево или направо н двукратными поворотами налево и направо или направо и налево. В самом деле, процедура (4.87) оказывается несколько проще, чем (4.63).

Ясно, что схема кустарниковых деревьев является альтернативой критерию АВЛ-сбаланснрованности. Поэтому возможно и желательно сравнение их характеристик, Мы отказываемся от анализа точными, математическими методами и обратим основное внимание на некоторые существенные различия. Можно доказать, что АВД-сбалансированные деревья являются подмножеством кустарниковых деревьев. Таким образом, класс последних шире.

Отсюда следует, что их длина пути в среднем больше, чем у АВЛ-деревьев. Отметим, что в этом отношении «наихудший слу- ркееег1ике зеакеЬ(х: !гг!еегк; как р'. кем как Ь: !н!крег); так р1,у2: те!'; Ъеп)п Иу =- пИ йеа Ъеп1п !слова нет в дереве, вставить его) пегз(р); Ь:= 2; п11Ърт а Ъеп1п Ьеу:= х; саиггг:.— — 1; /еЯ:= гп1; паЬ1:=- па1; !Ь:=- !айе; к!г:= 5а!зе епг$ епг) е1ее И х < р!,Усеу 1Ъеп Ъеп1п зеагсйх, р)'.!еХ! !г) ! ИЬФ 01Ъеп И р1,!Ь йеп Ъее)п Р1:=- У ~.!е!11 Ь:= 2; Уг'.Иг;= ка!зе; Иу1!.!Ь йеп Ъей1а гг'.г'-) рг.!с!1 .= р11вгеЫ; р)~лд!г!:= р; р1 1,!Ь:== )а!зе', р:= р1 епг) е1ее Ир1г.г!г йеп Ъеа1п гг'.А) р2:== р1~лкЬк; у11.сЬ;=- !а!зе; уЦ.щЬг:=- р21.!ск); у2~ЛеЯ „= у1; Р!.1еХФ:= Р2"!хги!гг; Р2ггикгеЬз:=.

Р; Р;= Р2 епг! епй ейе Ъеп1п Ь:= Ь вЂ” 1; И Ь Ф О йеп рг.!!г:== !ме епг1 епг) ейе И х > у1,Ьсу йеп Ъерп зеасс!г(х,рг,щЫ,!г); ' И Ь ~ О йеп Ир!,гЬ йеп ЪеФп р1:= у'!хгдЬ1; Ь:= 2; у!,кЬ:= 1а!зе И р1"!.кЬ йеп Ъеп)п 1ЯЯ) рг,г!еЬ1:=- рЦ,!еЯ; р1!,!с~1;= р; у1!г,тЬ:= ~а!зе,' р:=- р1 епг1 е1яе И р1 О!Ь 1Ъеп ЪеЪ1п (ЯЦ у2:= р1 !Ле11; р!'!,!Ь:= Язе; рЦ,!е/У:= р2~.гюзЫ! р21,к!еЬС':= р1; р~.к!аЫ:: р2! !е!11 р21 !ей! 1= р1 р:= р2 епг1 4. Пиалмичеекие иаформаяиоакые структрры ее4 е(ве Ъее(е Ь: Ь вЂ” 1, 11 Ь Ф О (Ъеаар(.гЬ.'= ггис епй еаи( е(ве Ъея(и у(.соил( ( р(.сопи( + 1; Ь:= О едй еЫ (леагсЬ1 (4.87) Ь-в в4 (4) Рис. 4.53. Формирование екустарняковых» деревьев при последователь. костях включений (4.о5), 4.б. Преабразаваная ключа (рассчакавка) 303 чай» вЂ” дерево (4) иа рис.

4.53. С другой стороны, в кустарниковых деревьях перестройка узлов будет происходить реже. Поэтому сбалансированные деревья предпочтительны в тех случаях, когда поиск ключей происходит намного чаще, чем включение (нлн удаление). Если это соотношение умеренное, можно предпочесть схему кустарниковых деревьев. Очень трудно сказать, где проходит граница. Это во многом зависит не только от соотношения между частотой поиска и частотой изменения структуры, но н от особенностей реализации. В частности, записи узлов могут иметь плочено упакованное представление, следовательно, обращение к полям поэребует выборки части слова.

Во многих реализациях работа с булевскими полями ()й, гй в случае кустарниковых деревьев) может быть более эффективной, чем с полями из трех значений (Ьа( в случае сбалансированных деревьев). алх ПРЕОБРАЗОВАНИЯ КЛЮЧА (РАССТАНОВКА) Сформулируем основную задачу, к которой мы обращаемся в последнем разделе, в дополнение к задачам, демонстрирующим методы динамического размещения данных; Задано множество 5 элементов, характеризующихся значениями ключей, на которых задано отношение порядка. Как организовать 5, чтобы поиск элемента с заданным кл1очом й требовал как можно меншпе затрат? Очевидно, что в памяти ЭВМ к каждому элементу в конце концов обращаются с помощью его адреса и в памяти.

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

Поэтому Н вЂ” это отображение, которое преобразует ключи в индексы массива, что дало термин преобразование ключей, обычно применяемый для обозначения этого приема. Следует заметить, что нам не придется использовать какие- либо процедуры динамического размещения, поскольку массив — одна из базовых, статических структур. Таким образом, этот раздел несколько чужероден в главе о динамических 4. Динимичесние информационные структуры информационных структурах, ио поскольку преобразование ключей часто используется в той же области, где наряду с нпм в качестве конкурентов используются древовидные структуры, то, по-вндимому, его обсуждение здесь уместно.

Основная трудность преобразования ключей заключается в том, что множество возможных значений ключей намного обширнее, чем множество имеющихся адресов памяти (индексов массива). Типичный пример — использование слов длиной, скажем, до 10 букв алфавита в качестве ключей для ндентп. фикации индивидуумов в множестве, например, до тысячи человек. Следовательно, имеются 2бш возможных ключей, которые нужно отобразить в 10» возможных индексов, Поэтому очевидно, что Н вЂ” это функция, отображающая «много в один». Если дан некоторый ключ й, то первый этап в операции поиска — это вычисление соответствующего индекса й = Н (й), а второй — очевидно, необходимый этап — проверка, действительно ли элемент с ключом й находится в массиве (таблице) Т по адресу й, т.

е. проверка Т(Н(к)1 айву = й, Сразу возникают два вопроса; 1. Какую функцию Н следует использовать? 2, Как поступать в ситуации, когда Н не дает местонахождения нужного элемента? Ответ на второй вопрос заключается в том, что нужно использовать какой-то метод для получения нового адреса, скажем, с индексом К а если там вновь нет нужного элемента, то с третьим индексом й" и т. д. Случай, когда на указанном месте находится другой ключ, а не искомый, называется конфликтом, задача получения альтернативных индексов называется разрешением конфликтов, Далее мы обсудим выбор функции преобразования н методы разрешения конфликтов.

4.6.1. Выбор функции преобразояаимя Основное требование к хорошей функции преобразования состоит в том, чтобы она распределяла ключи как можно более равномерно по шкале значений индексов. Кроме выполнения этого требования, распределение не связано никакой схемой, н даже желательно, чтобы оио производило впечатление совершеяно случайного. Такая особенность дала этому методу несколько ненаучное название «расстановкн» (хеширования), а Н называется функцией расстановки "), Разумеется, она должна эффективно вычисляться, т. е. состоять ") Следует отметить, что и советской литературе ипериые »тот метод был описап А.

П. Ершовым н наяиаи им «функциями расстановки». гуром, ред. 306 4,б. Преобразования камча (расстановка) из очень небольшого числа основных арифметических действий. Предположим, что имеется функция огЫ(м), которая определяет порядковый номер ключа й во множестве всех возможных значений ключей. Предположим далее, что индексы массива занимают интервал целых чисел 0...

Ф вЂ” 1, где М— размер массива. Тогда очевидным решением является (4.88) Н (Ф) = огд(й) шед М Эта функция обладает тем свойством, что значения ключей равномерно распределя|отея на всем интервале индексов, поэтому она служит основой большинства преобразований ключей. Кроме того, она очень эффективно вычисляется при М, равном степени двойки. Но как раз этого случая следует избегать, если ключи являются последовательностями букв. Предположение, что все ключи равновероятны, в этом случае совершенно ошибочно. В результате слова, различающиеся лишь несколькими символами, будут с большой вероятностью отображаться в одинаковые индексы, что приведет к чрезвычайно неравномерному распределению. Поэтому рекомендуется, чтобы )тт в (4.88) было простым тислолт (4.71.

Отсюда следует, что придется выполнять операцию целого деления, которую нельзя заменить простым маскированием двоичных разрядов. Но это не является препятствием для большинства современных вычислительных машин, которые имеют встроенную команду деления. Часто употребляется свертка, состоящая из выполнения логических операций, таких, как «исключающее или» на некоторых частях ключа, представленного последовательностью двоичных цифр. Эти операции на некоторых машинах могут выполняться быстрее, чем деление, но не всегда можно быть уверенным, что они равномерно распределяют ключи на интервале индексов, Поэтому мы не будем подробно обсуждать такие методы, 4.6.2.

Разрешение конфпнктев Если строка в таблице, соответствующая заданному ключу, ие содержит нужный элемент, то имеет место конфликт, т, е. два элемента имеют ключи,отображающиеся в один и тот же индекс. Нужна вторая проба с использованием другого индекса, который однозначно получается на основе данного ключа. Существует несколько методов получения таких вторичных индсксов. Очевидный и эффективный метод») — свя- *) Это, конечно, метод разрешения конфликтов, а не метод получения вторичных индексов. — Прим.

Характеристики

Список файлов учебной работы