2. Выполните алгоритм Т, используя в качестве аргумента новый ключ; поиск закончится неудачно на шаге ТЗ или Т4. Если последний шаг - ТЗ, просто поместите К в элемент таблицы NODE(P) с номером fc и завершите работу алгоритма. В противном случае поместите в эту позицию адрес нового узла Q <= AVAIL, содержаш;его пустые ссылки, а затем установите Р Q. Теперь присвойте fc и fc соответственно следуюш;ие символы К и X: если к ф fc, сохраните К в позиции fc узла NODE(P), а X - в позиции fc; однако, если к = к, поместите в позицию fc указатель на новый узел Q <= AVAIL и присвойте Р <- Q. Повторяйте этот процесс до тех пор, пока не получится к ф к (считается, что ни один из ключей не служит началом другому).

3. Заменим ключ пустой ссылкой в том узле, в котором он находился. Если теперь данный узел стал "бесполезным" в силу того, что все его элементы, кроме одного, пред-ставляюш;его ключ X, пусты, удалим этот узел и заменим соответствуюш;ий указатель в родительском узле указателем X. Если "бесполезным" становится родительский узел, удалим его описанным способом.

4. Успешный поиск будет проходить так же, как и в случае несжатой таблицы, однако для неудачного поиска в сжатой таблице может потребоваться несколько дополнительных итераций. Например, такой аргумент поиска, как TRASH, заставит программу произвести шесть итераций (что явно больше пяти!); этот случай является наихудшим. Необходимо также проверить невозможность зацикливания на пустых позициях. (Этот замечательный пример упаковки таблицы в 49 элементов предложен Дж. С. Фишберном (J. Scot Fishburn), который также доказал, что 48 позиций для упаковки таблицы недостаточно.)

Более медленный, но более многосторонний путь экономии памяти для луча был предложен Куртом Мали (Kurt Maly), САСМ 19 (1976), 409-415.

В общем, если нужно сжать п разреженных таблиц, содержащих соответственно Xi, ..., Хп ненулевых элементов, метод "первый подходящий", который смещает j-ю таблицу на минимальную величину rj с целью избежания конфликтов с ранее размещенными таблицами даст rj < {xi + - + Xj-i)Xj, поскольку каждый предшествующий ненулевой элемент может блокировать не более Xj смещений. Такая оценка наихудшего случая дает rj < 93 для табл. 1, гарантируя, что любые 12 таблиц длиной 30, содерясащие соответственно 10, 5, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2 ненулевых элементов, могут быть упакованы в 93 -Ь 30 последовательных позиций безотносительно к двоичному предстгшлению ненулевых элементов. Дальнейшее усовершенствование этого метода было проведено в работе R. Е. Tarjan and А. С. Yao, САСМ 22 (1979), 606-611. Динамическая реализация сжатых лучей, предложенная Ф. М. Лиангом (F. М. Liang), использована в таблицах переносов в издательской системе lEX (см. D. Е. Knuth, САСМ 29 (1986), 471-478; Literate Programming (1991), 206-233).

5. В каждом семействе сначала проверяется наиболее вероятный исход; для этого буквы располагаются слева направо в порядке уменьшения вероятности. Оптимальность такого упорядочения может быть доказана аналогично теореме 6.IS. [См. CACiVf 12 (1969), 72-76.]

7. Например, 8, 4, 1, 2, 3, 5, 6, 7, 12, 9, 10, 11, 13, 14, 15. (Независимо от того, какая последовательность используется, ни левое, ни правое поддерево не может содержать больше двух узлов на уровне 4.) Даже полученное нами "наихудшее" дерево принадлежит к числу четырех наилучших возможных деревьев, так что, как видите, деревья цифрового поиска не слишком чувствительны к порядку вставки.

8. Да. В псше KEY теперь содержится только усеченный ключ; левые биты, значения которых определяются позицией узла, удалены. Аналогичная модификация применима и к алгоритму Т.

1 D1. Инициализаиия. (гХ = К) 1 Р f- ROOT. (rll = Р)

С2 D4. Перемещение вправо. Q f-RLINK (Р). С2 Переход к шагу D5 при Q = А. С-1 Р f- Q. С D2. Сравнение. С Выход при К = KEY(P). C-S Смеш;ение К влево на один бит. С - S Переход к шагу D4, если выделенный бит равен 1. С1 РЗ. Перемещение влево. Q4-LLINK(P). Cl Переход к шагу D2 с Р +- Q, если Q А. 5Н Продолжение то же, что и в программе 6.2,2Т, с обменом местами гА и гХ.

Время работы фазы поиска этой программы равно (ЮС - 35 + 4)и, где С - 5 представляет собой число проверок битов. Для случайных данных приближенное среднее время работы таково.

Успешно Неудачно

Программа 6.2.2Т 15 1пЛГ 12.34 15 In Л-2.34

Данная программа 14.4 In Л- 6.17 14.4 In 1,26

(Следовательно, при не очень больших N программа 6.2.2Т работает несколько быстрее.)

10. Обозначим через ф операцию "исключающее или" над п-битовыми числами, и пусть /(ж) = п - flg(2; + 1)] - число левых ненулевых битов х. Вот одно из решений: (Ь) если поиск с помощью алгоритма Т заканчивается неудачно на шаге ТЗ, то к на единицу меньще количества проверенных битов; в противном случае, если поиск заканчивается на шаге Т4, fc = f(K ф X). (а, с) Выполним обычный поиск, но при этом будем хранить х - минимальное значение АГфКЕУ(Р) по всем KEY(P), сравнивавшимся с К в процессе поиска. Тогда fc = /(ж). (Докажите, что наибольшее число битов, совпадающих с К, имеют ключи, сравниваемые с аргументом. В случае (а) максимум fc достигается либо для наибольшего ключа < К, либо для наименьшего ключа > К.)

11. Нет; удаление узла только с одним пустым поддеревом приведет к потере одного бита в ключах непустого поддерева. Для удаления узла следует заменить его одним из

его терминальных наследников, например, по возможности двигаясь при поиске только вправо.

12. Вставим три случайных числа - а, /?, 7 из диапазона [0,1] - в изначально пустое дерево; затем удалим а с вероятностью р, /3 с вероятностью д, 7 с вероятностью г с помощью предложенного в предыдущем упражнении алгоритма. Дерево

получается с вероятностью \р + + I. * это равно только при р = 0.

13. Добавить к каждому узлу поле KEY и сравнивать К с этим ключом перед проверкой элемента вектора на шаге Т2. Табл. 1 должна быть изменена следующим образом: узлы (1), ..., (12) должны содержать ключи THE, AND, BE, FOR, HIS, IN, OF, TO, WITH, HAVE, HE, THAT соответственно (если они вставляются в порядке уменьшения частрты), и эти ключи должны быть удалены из своих прежних позиций. (Соответствующая программа будет медленнее и сложнее программы Т. Более прямолинейное М-арное обобщение алгоритма D привело бы к созданию дерева с N узлами с одним ключом и М ссылками в каждом узле.)

14. Если j < п, то имеется только одно такое место, а именно - KEY(P). Однако при j > п множество всех появлений находится посредством обхода поддерева узла Р: если имеется г появлений К в TEXT, то поддерево содержит г-1 узел (включая узел Р) и, таким образом, имеет г полей ссылок с TAG = 1. Эти поля ссылок указывают на все узлы, ссылающиеся на позиции в TEXT, которые содержат К (в повторных проверках TEXT нет необходимости).

15. Начните построение дерева с установки KEY(HEAD) равной первой ссылке на TEXT, а также LLINK (HEAD) •«- HEAD, LTAG (HEAD) 1. Дальнейшие ссылки на TEXT могут быть вставлены в дерево с использованием следующего алгоритма.

Установить К равным значению нового ключа, который следует вставить (это первая ссылка на массив TEXT, которую делает алгоритм). Выполните алгоритм Р. Он должен закончиться неудачно, поскольку ни один ключ не может быть префиксом другого ключа. (На шаге Рб осуществляется вторая (и последняя) ссылка на массив TEXT; больше ссылки на TEXT делаться не будут). Предположим теперь, что ключ, найденный на шаге Рб, согласуется с аргументом К по первым I бит, но отличается, начиная с позиции I + 1 {в которой К имеет цифру Ь, а ключ соответственно цифру 1 -6). (Хотя при поиске с помощью алгоритма Р ключ j может стать намного больше, чем I, можно доказать, что описанная здесь процедура найдет наилучшее совпадение с К среди всех имеющихся ключей. Таким образом, во всех ключах текста, которые совпадают с А" по первым / бит, в качестве (Z-l-l)-ro бита содержится 1 - й.) Теперь повторим выполнение алгоритма Р, в котором К заменено его ведущими I бит (т. е. п •<- /). На этот раз поиск будет успешным, поэтому шаг Рб выполняться не будет. Установите R <= AVAIL, KEY(R) положение нового ключа в TEXT. Если LLINK(Q) = Р, установите LLINK(Q) •«- R, < LTAG(Q), LTAG(Q) •«- 0; в противном случае установите RLINK(Q) R, < RTAG(Q), RTAG(Q) 0. Если й = О, установите LTAG(R) 1, LLINK(R) R, RTAG(R) t, RLINK(R) P; иначе установите RTAG(R) 1, RLINK(R) f- R, LTAG(R) i- t, LLINK(R) P. Если t = 1, установите SKIP(R) <-1 + I - j; в противном случае установите SKIP(R) 1 + I - j + SKIP(P) и SKIP(P) j - I - 1.

16. Структура дерева требует, чтобы в каждый узел входила одна идущая снизу пунктирная линия, которая начинается в той части дерева, где соответствующий ключ впервые отличается от всех остальных. Если такой части дерева нет, алгоритмы перестают работать. Мы можем просто убрать ключи, служащие началом других ключей, но тогда алгоритм из упр. 14 не получит достаточного количества данных для поиска всех вхождений аргумента.