Докажите, что такой процесс при N -> оо должен выполнять в среднем минимум logj,j N шагов (в предположении, что все ключи таблицы, как и аргумент поиска, равновероятны). (Следовательно, выигрыш от использования к процессоров составляет не к раз, как может показаться, а только lg(A; +1) раз; в этом смысле выгоднее выполнять поиск с помощью одного отдельного процессора, не кооперируя их.)

28. [М23] Определим дерево Тью (Thue) Тп при помощи алгебраического выражения с использованием бинарного оператора "*" следующим образом: То{х) = х * х, Ti(x) = х,

Тп+2(х)=Тп+1{х)*Тп{х).

a) Количество листьев дерева Тп равно количеству х в полной записи Тп{х). Выразите его при помощи чисел Фибоначчи.

b) Докажите, что если бинарный оператор "*" удовлетворяет аксиоме

{{х * х) * х) * {{х * х) * х) = X ,

то Тт{Тп{х)) = Тт+п-Лх) ДЛЯ ВСОХ Ш > О И П > 1.

► 29. [22] (Поль Фельдман (Paul Feldman), 1985.) Вместо предположения, что Ki < Кг < •• < Kn, допустим, что Кр < Кр2) < < Кр(), где перестановка р(1)р(2).. .p(N) является инволюцией* и p{j) = j для всех четных значений j. Покажите, что можно найти любой данный ключ К или выяснить, что он отсутствует, проведя максимум 2[lgAJ + 1 сравнений.

30. [27] [Инволюционное кодирование.) Используя идеи предыдущего упражнения, расположите N ключей таким образом, чтобы их относительный порядок неявно кодировал произвольно взятый массив t-битовых чисел хх, Х2, Хт, нг < N/4 4-1 - 2*. Найденный вами способ расположения должен позволять определять первые к бит числа xj при помощи к сравнений для любого j, а также находить произвольный ключ при помощи < 2[lg NJ -Ы сравнений. (Этот результат используется в теоретическом изучении структур данных, асимптотически эффективных во времени и пространстве.)

6.2.2. Поиск по бинарному дереву

В предыдущем разделе мы видели, что неявная структура бинарного дерева облегчает понимание бинарного поиска и поиска Фибоначчи. Рассмотрев соответствующие деревья, мы показали, что для заданного значения Л количество сравнений, необходимое для бинарного поиска, не превышает количества, которое требуется для любого другого метода, основанного на сравнении ключей. Однако методы из предыдущего раздела годятся, в основном, для таблиц фиксированного размера, поскольку последовательное расположение записей делает вставку и удаление записей весьма трудоемкими. Если таблица динамически изменяется, то мы можем потратить на ее постоянное упорядочение куда больше времени, чем сэкономить на бинарном поиске.

Явное использование структуры бинарного дерева позволяет быстро вставлять и удалять записи, а также эффективно выполнять поиск в таблице. В результате мы получаем метод, эффективный как для поиска, так и для сортировки. Цена такой гибкости - два поля ссылок в каждой записи таблицы.

Технологии поиска в растущей таблице часто называют алгоритмами таблиц символов, так как ассемблеры, компиляторы и другие системные программы обычно применяют их для хранения пользовательских символов. Например, ключом записи

* Инволюцией называется такое отображение некоторого множества на себя, квадрат которого является тождественным отображением. - Прим. перев.

(RIEsJ) (GEMINI

(CANCER) [4] LEO (SCORPIO VIRGO

2j 3j 5j Г LIBRA 3 Ш LLI [HJ Lii

Рис. 10. Бинарное дерево поиска.

в компиляторе может быть символьный идентификатор переменной в некоторой программе на языке FORTRAN или С, а остальная часть записи может содержать информацию о типе переменной и ее адресе; другим примером служит ключ, являющийся символом в М1Х-программе, а остаток записи содержит его эквивалент. Программы поиска со вставкой по дереву, которые будут описаны в этом разделе, достаточно эффективны в качестве алгоритмов таблиц символов, в особенности в приложениях, в которых может оказаться желательным вывод списка символов в алфавитном порядке. Другие алгоритмы таблиц символов описываются в разделах 6.3 и 6.4.

На рис. 10 показано бинарное дерево поиска, содержащее названия одиннадцати знаков зодиака*. Если мы приступим к поиску двенадцатого имени, SAGITTARIUS, начиная от корня дерева, то увидим, что оно больше, чем CAPRICORN, и нужно идти вправо; оно бшьше, чем PISCES, а потому мы опять идем вправо. Это имя меньше, чем TAURUS, поэтому теперь мы сворачиваем влево. Так как искомое имя меньше, чем SCORPIO, мы попадаем во внешний узел Поиск оказался неудачным, и

теперь мы можем вставить SAGITTARIUS в то место, где завершился наш поиск, на место внешнего узла [¥]. Таким образом, таблица может расширяться без перемещения существующих записей. Дерево на рис. 10 получено путем последовательной вставки в пустое дерево ключей CAPRICORN, AQUARIUS, PISCES, ARIES, TAURUS, GEMINI, CANCER, LEO, VIRGO, LIBRA, SCORPIO в указанном порядке.

На рис. 10 все ключи левого поддерева меньше (в алфавитном порядке), чем CAPRICORN, а все ключи правого поддерева - больше. То же самое справедливо и для левого и правого поддеревьев любого узла. Отсюда следует, что при обходе дерева в симметричном порядке (см. раздел 2.3.1), поскольку симметричный порядок

* Список знаков зодиака, упорядоченный по месяцам, таков: Козерог (Capricorn), Водолей (Aquarius), Рыбы (Pisces), Овен (Aries), Телец (Taurus), Близнецы (Gemini), Рак (Cancer), Лев (Leo), Дева (Virgo), Весы (Libra), Скорпион (Scorpio), Стрелец (Sagittarius). - Прим. перев.

основан на обходе сначала левого поддерева каждого узла, затем - самого узла, а после - правого поддерева, мы получим список ключей в алфавитном порядке:

AQUARIUS, ARIES, CANCER, CAPRICORN, GEMINI, LEO, VIRGO.

Ниже приводится подробное описание процесса поиска со вставкой.

Алгоритм Т (Поиск по дереву со вставкой (Tree search and insertion)). Дана таблица записей, образующая бинарное дерево. Этот алгоритм (рис. 11) предназначен для поиска данного аргумента К. Если К в таблице отсутствует, новый узел, содержащий К, вставляется в дерево в надлежащее место.

Предполагается, что узлы дерева содержат, по крайней мере, следующие поля:

KEY(P) - ключ, хранящийся в узле NODE(P); LLINK(P) - указатель на левое поддерево узла NODE(P); RLINK(P) - указатель на правое поддерево узла NODB(P).

Пустые поддеревья (внешние узлы на рис. 10) представляются пустыми указателями Л. Переменная ROOT указывает на корень дерева. Для удобства полагаем, что дерево не пусто, т. е. ROOT ф Л, так как при ROOT = Л необходимые операции тривиальны.

Т1. [Инициализация.] Установить Р <- ROOT. (Переменная-указатель Р будет перемещаться вниз по дереву.)

Т2. [Сравнение.] Если К < КЕУ(Р), перейти к шагу ТЗ; если К > КЕУ(Р), перейти к шагу Т4; и если К = КЕУ(Р), поиск успешно завершается.

ТЗ. [Перемещение влево.] Если LLINK(P) ф Л, установить Р ч- LLINK(P) и перейти к шагу Т2; в противном случае перейти к шагу Т5.

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

Т5. [Вставка в дерево.] (Поиск оказался неудачным; теперь мы должны поместить К в дерево.) Установить Q AVAIL (адрес нового узла). Присвоить KEY(Q) <-К, LLINK(Q) 4- RLINK(Q) <- Л. (На практике следует инициализировать и другие поля нового узла.) Если К был меньше, чем KEY(P), следует назначить LLINK(P) 4- Q; в противном случае - назначить RLINK(P) 4- Q. (Теперь мы можем присвоить Р <- Q и считать поиск успешно завершившимся.)

Этот алгоритм сам подсказывает нам свою программную реализацию. Предположим, например, что узлы дерева имеют структуру

за которой, возможно, следует дополнительная информация INFO. Используя, как и в главе 2, список свободной памяти AVAIL, мы можем написать следующую MIX-программу.

Программа Т (Поиск по дереву со вставкой). гА = К, ill = Р, г12 = Q.

01 LLINK EQU 2:3

02 RLINK EQU 4:5