Поиск в таком бинарном дереве в большей или меньшей степени сводится к поиску путем сравнений, но ветвление осуществляется по признаку "равно-не равно" а не "меньше-больше". Элементарная теория из раздела 6.2.1 гласит, что необходимо выполнить в среднем хотя бы IgiV сравнений для того, чтобы различить N ключей. Среднее количество сравнений, сделанных при поиске в дереве, которое подобно изображенному на рис. 31, должно быть не меньше количества сравнений, выполняемых при бинарном поиске с использованием описанных в разделе 6.2 технологий.

С другой стороны, луч из табл. 1 способен выполнять ]1/-путевое ветвление за один раз; мы увидим, что среднее время поиска для больших N включает всего около log N = IgN/lgM итераций при случайных входных данных. Мы также увидим, что "чистая" схема луча (подобная алгоритму Т) требует, в целом, примерно N/lnM узлов для различения N случайных ключей; следовательно, общее количество необходимой памяти пропорционально MN/ In М.

Из этих рассуждений становится ясно, что идея луча хороша только для нескольких первых уровней дерева. Повысить производительность можно за счет комбинирования двух стратегий: луча для нескольких первых символов и переключения на другую стратегию - для оставшихся. Например, Э. Г. Сассенгат (мл.) (Е. Н. Sussenguth, Jr.) [САСМ 6 (1963), 272-279] предложил использовать посимвольную схему до достижения части дерева, в которой возможны, скажем, не более шести ключей, а затем проходить последовательно по этому списку. Далее мы увидим, что такая смешанная стратегия позволяет уменьшить количество yзJЮв луча примерно в шесть раз без существенного изменения времени работы.

Т. Н. Турба (Т. N. Turba) [САСМ 25 (1982), 522-526] указал, что иногда при поиске с ключами переменной длины удобно иметь по одному поисковому дереву или лучу для каждой длины ключа.

Бинарный цифровой поиск. Допустим, что iW = 2, и аргумент поиска сканируется по одному биту. Для этого случая разработаны два специальных интересных метода.

Первый метод, именуемый цифровым поиском по дереву {digital tree search), разработан Э. Г. Коффманом (Е. G. Coffman) и Дж. Ивом (J. Eve) [САСМ 13 (1970), 427-432, 436]. Его суть заключается в хранении полных ключей в узлах так же, как в алгоритмах поиска по дереву из раздела 6.2.2, но с использованием битов аргумента вместо результатов сравнения для выбора левой или правой ветви. На рис. 32 изображено бинарное дерево, построенное по этому методу путем вставки 31 наиболее употребительного английского слова в порядке уменьшения частот появления слов. Чтобы получить данные для иллюстрации метода, слова были

представлены в кодах символов MIX и конвертированы в двоичные числа с пятью битами на байт. Так, слово WHICH представляется битовой последовательностью 11010 01000 010010001101000.

Для поиска слова WHICH на рис. 32 сравним его со словом THE в корне дерева. Так как они не совпадают и первый бит слова WHICH равен 1, мы двигаемся вправо и сравниваем его со словом OF. Слова опять не совпадают, и следующий бит слова WHICH равен 1, поэтому мы снова перемещаемся вправо и сравниваем наше слово WHICH со словом WITH, и т. д. Алфавитный порядок ключей в цифровом поиске по дереву больше не соответствует симметричному порядку узлов.

Интересно обратить внимание на разницу между деревьями, представленными на рис. 32 и 12 (из раздела 6.2.2), так как последнее дерево было построено тем же способом, но с использованием сравнения ключей вместо битов. Если принять во внимание данные частоты появления слов, цифровой поиск по дереву на рис. 32 потребует в среднем 3.42 сравнений при успешном завершении поиска. Это несколько лучше, чем в случае дерева, показанного на рис. 12, для которого требуется 4.04 сравнения (хотя, конечно же, время самого сравнения различно для этих двух ситуаций).

ЧОбГ "139

Рис. 32. Дерево цифрового поиска для 31 наиболее употребительного английского слова, вставленного в порядке уменьшения частот.

Алгоритм D {Цифровой поиск со вставкой по дереву). Дана таблица записей, представляющих бинарное дерево, которое описано выше. Алгоритм предназначен для поиска некоторого аргумента К. Если К отсутствует в таблице, новый узел, содержащий К, вставляется в дерево в соответствующем месте.

Алгоритм предполагает, что дерево не пусто и что его узлы имеют поля KEY, LLINK и RLINK, такие же, как в алгоритме 6.2.2Т. В действительности, как вы можете убедиться сами, алгоритмы практически идентичны. D1. [Инициализация.] Установить Р ROOT и К -(г- К.

D2. [Сравнение.] Если К = KEY(P), поиск успешно завершается. В противном случае установить b равным лидирующему биту К и сдвинуть К влево на

один бит (тем самым удалив этот бит и вставив О справа). Если 6 = 0, перейти к шагу D3; в противном случае перейти к шагу D4.

D3. [Перемещение влево.] Если LLINK (Р) Ф Л, установить Р LLINK (Р) и перейти к шагу D2. В противном случае перейти к шагу D5.

D4. [Перемещение вправо.] Если RLINK (Р) ф Л, установить Р <- RLINK(Р) и перейти к шагу D2.

D5. [Вставка в дерево.] Установить Q AVAIL, KEY(Q) -s- К, LLINK(Q) -s- RLINK (Q) •f- Л. Если 6 = 0, присвоить LLINK(P) •(- Q; в противном случае присвоить RLINK (Р) !-Q. I

Хотя алгоритм поиска по дереву 6.2.2Т по сути своей бинарный, не сложно увидеть, что он может быть распространен на М-арный цифровой поиск для любого М > 2 (см. упр. 13).

Дональд Р. Моррисон (Donald R. Morrison) [ЗАСМ 15 (1968), 514-534] открыл весьма привлекательный способ построения Л-узловых деревьев поиска, основанных на бинарном представлении ключей без необходимости их хранения в узлах. Этот метод, названный "Патриция" (Patricia - Practical Algorithm То Retrieve Information Coded In Alphanumeric), очень хорошо подходит для работы с большими ключами переменной длины, например с заголовками или фразами, хранящимися в файле большого объема. Похожий алгоритм был одновременно опубликован в Германии (G. Gwehenberger, Elektronische Rechenanlagen 10 (1968), 223-226).

Основная суть метода "Патриция" состоит в построении бинарного дерева без однопутевых ветвей посредством включения в каждый узел количества битов, которые можно пропустить, прежде чем приступить к следующему тесту. Существует несколько способов реализации этой идеи; возможно, простейший из них представлен на рис. 33. Имеется массив битов TEXT (обычно довольно длинный), который может храниться во внешнем файле с произвольным доступом, поскольку при каждом поиске обращение к TEXT осуществляется только один раз. Каждый ключ, который должен храниться в нашей таблице, определяется местом его начала в тексте; можно считать, что он идет от места своего начала и до конца текста. (Метод "Патриция" не ищет точного соответствия между ключом и аргументом; вместо этого определяется, существует ли ключ, начинающийся с аргумента).

В ситуации, показанной на рис. 33, представлено семь ключей, которые начинаются с каждого входящего в текст слова, а именно - с "THIS IS THE HOUSE THAT JACK BUILT?", "IS THE HOUSE THAT JACK BUILT?; ..., "BUILT?! Имеется одно важное ограничение: ни один ключ не может быть началом другого. Оно выполняется, если текст завершается специальным символом конца текста (в нашем случае это "?"), который не встречается нигде в тексте. То же ограничение неявно применяется и в схеме луча алгоритма Т, в которой признаком конца слова служит "и! Дерево, используемое методом "Патриция" для поиска, должно целиком размещаться в оперативной памяти с произвольным доступом (или должно быть организовано по страничной схеме, описанной в разделе 6.2.4). Оно состоит из заголовка и iV - 1 узла; узлы имеют несколько полей.

KEY, указатель на текст. Это поле должно иметь длину как минимум Ig С бит, если текст содержит С символов. На рис. 33 слова, показанные внутри