можно было воспользоваться преимуществами многопутевого поиска при произвольных размерах файлов.

Лемма 15.8 Для выполнения поиска или вставки в TST-дереве, содержащем элементы в листьях (т.е., не имеющем ни одной однопутевой ветви в нижней части дерева) и R-путевые ветви в корне, требуется приблизительно InTV - t \nR обращений к байтам для N ключей, которые являются случайными строками байтов. При этом количество требуемых связей равно R (для корневого узла) плюс небольшое постоянное число, кратное N.

Эти грубые оценки непосредственно следуют из леммы 15.6. При оценке затрат времени мы принимаем, что все узлы в пути поиска, за исключением нескольких узлов у верщины, количество которых постоянно, действуют по отнощению к R значениям символов подобно рандомизированным BST-деревьям. Поэтому мы просто умножаем значение времени на 1пЛ. При оценке затрат памяти предполагается, что узлы на нескольких первых уровнях заполнены R значениями символов, а узлы на нижних уровнях содержат только постоянное количество значений символов.

Например, при наличии 1 миллиарда случайных ключей, представляющих собой строки байтов, при R = 256 и при использовании на верхнем уровне таблицы, размер которой равен = 65536, для выполнения типового поиска потребуется около InlO - 2 In 256 - 20.7 - 11.1 = 9.6 сравнений байтов. Использование таблицы в верхней части структуры уменьшает затраты на поиск в два раза. Если ключи являются действительно случайными, этой производительности можно достичь с помощью более непосредственных алгоритмов, в которых используются ведущие байты ключа и таблица существования, как было описано в разделе 14.6. В случае применения TST-деревьев такую же производительность можно получить и тогда, когда ключи имеют менее случайную структуру.

Интересно сравнить TST-деревья без многопутевых ветвей в корне со стандартными BST-деревьями при использовании случайных ключей. В соответствии с леммой 15.8, для выполнения поиска в TST-дереве потребуется около InTV сравнений байтов, в то время как в стандартных BST-деревьях требуется около InTV сравнений ключей. В верхней части BST-дерева сравнения ключей могут быть выполнены путем сравнения всего одного байта, но в нижней части для выполнения сравнения ключа может потребоваться несколько сравнений байтов. Это различие в производительности не является решающим. Причины, по которым при использовании строковых ключей TST-деревья предпочтительнее стандартных BST-деревьев, таковы: они обеспечивают быстрое обнаружение промаха при поиске; они непосредственно приспособлены для многопутевого ветвления в корне; и (что наиболее важно) они хорошо подходят для ключей в виде строк байтов, не являющихся случайными, поэтому длина поиска не превыщает длину ключа в TST-дереве.

Некоторые приложения не могут воспользоваться преимуществом Л-путевого ветвления в корне - например, все ключи в примере с библиотечными кодами из рис. 15.18 начинаются с буквы L или W. Для других приложений может требоваться более высокий коэффициент ветвления в корне - например, как отмечалось, если бы ключи были случайными целыми числами, пришлось бы использовать максимально большую таблицу. Подобные зависимости от приложения можно задействовать при на-

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

Вероятно, наиболее важное свойство trie-деревьев или TST-деревьев с записями в листьях заключается в том, что их характеристики производительности не зависят от длины ключа. Следовательно, их можно использовать для ключей произвольной длины. В разделе 15.5 рассмотрено одно такое особенно эффективное приложение.

Упражнения

> 15.49 Нарисуйте trie-дерево существования, образованное в результате вставки слов now is the time for all good people to come the aid of their party в первоначально пустое trie-дерево. Используйте 27-путевое ветвление.

> 15.50 Нарисуйте TST-дерево существования, образованное в результате вставки слов now is the time for all good people to come the aid of their party в первоначально пустое TST-дерево.

I> 15.51 Нарисуйте 4-путевое trie-дерево, образованное в результате вставки элементов с ключами 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в первоначально пустое trie-дерево, в котором используются 2-разрядные байты.

> 15.52 Нарисуйте TST-дерево, образованное в результате вставки элементов с ключами 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в первоначально пустое TST-дерево, в котором используются 2-разрядные байты.

> 15.53 Нарисуйте TST-дерево, образованное в результате вставки элементов с ключами 01010011 00000111 00100001 01010001 11101100 00100001 10010101 01001010 в первоначально пустое TST-дерево, в котором используются 4-разрядные байты.

о 15.54 Нарисуйте TST-дерево, образованное в результате вставки элементов с ключами библиотечных кодов из рис. 15.18 в первоначально пустое TST-дерево.

о 15.55 Измените приведенную реализацию поиска и вставки в многопутевом trie-дереве (программа 15.7), чтобы она работала при условии, что все ключи (фиксированной длины) являются и-байтовыми словами (т.е. не требуется указание конца ключа).

о 15.56 Измените приведенную реализацию поиска и вставки в TST-дереве (профамма 15.8), чтобы она работала при условии, что все ключи (фиксированной длины) являются И-байтовыми словами (т.е. не требуется указание конца ключа).

15.57 Экспериментально сравните время и объем памяти, требуемые для 8-путе-вого trie-дерева, построенного из случайных целых чисел с использованием 3-разрядных байтов, для 4-позиционого trie-дерева, построенного из случайных целых чисел с использованием 2-разрядных байтов, и для бинарного trie-дерева, построенного из тех же ключей, при N= 10, 10\ 10 и 10 (см. упражнение 15.14).

15.58 Измените программу 15.9, чтобы подобно операции sort она обеспечивала посещение всех узлов, которые соответствуют искомому ключу.

о 15.59 Создайте функцию, которая выводит все ключи в TST-дереве, отличающиеся от искомого не более чем в к позициях для заданного целочисленного значения к.

15.60 Приведите полную характеристику худщего случая длины внутреннего пути /?-путевого trie-дерева с различными н-разрядными ключами.

15.61 Разработайте реализацию таблицы символов с использованием многопутевых trie-деревьев, которая включает в себя деструктор, конструктор копирования и перефуженную операцию присваивания, а также поддерживает операции construct, count, insert, remove и join для АТД первого класса таблицы символов с поддержкой дескрипторов клиента (см. упражнения 12.6 и 12.7).

15.62 Разработайте реализацию таблицы символов с использованием многопутевых TST-деревьев, которая включает в себя десфуктор, конструктор копирования и перефуженную операцию присваивания, а также поддерживает операции construct, count, insert, remove и join для АТД первого класса таблицы символов с поддержкой дескрипторов клиента (см. упражнения 12.6 и 12.7).

t> 15.63 Создайте программу, которая выводит все ключи в /?-путевом trie-дереве, имеющие те же начальные t байтов, что и заданный искомый ключ.

15.64 Измените приведенную реализацию поиска и вставки в многопутевом trie-дереве (программа 15.7), чтобы исключить однопутевое ветвление, как это было сделано для patricia-деревьев.

15.65 Измените приведенную реализацию поиска и вставки в TST-дерево (программа 15.8), чтобы исключить однопутевое ветвление, как это было сделано для patricia-деревьев.

15.66 Создайте программу, которая выполняет балансировку BST-деревьев, представляющих внутренние узлы TST-дерева (реорганизует их так, чтобы все их внещние узлы располагались на одном из двух уровней).

15.67 Создайте версию операции insert для TST-деревьев, которая поддерживает представление всех внутренних узлов в виде сбалансированного дерева (см. упражнение 15.66).

15.68 Приведите полную характеристику худщего случая длины внутреннего пути TST-дерева, содержащего N различных н-разрядных ключей.

15.69 Создайте программу, генерирующую случайные 80-байтовые строковые ключи (см. упражнение 10.19). Воспользуйтесь этим генератором ключей для построения 256-путевого tne-дерева, содержащего УУ случайных ключей при = 10

10 и 10, с применением операции search, а затем - операции insert в случае промаха при поиске. Программа должна выводить общее количество узлов в каждом trie-дереве и общее время, затраченное на построение каждого /пе-дерева.

15.70 Выполните упражнение 15.69 для TST-деревьев. Сравните полученные характеристики производительности с характеристиками trie-деревьев.

15.71 Создайте генератор, который генерирует ключи, перемещивая случайную 80-байтовую последовательность (см. упражнение 10.21). Воспользуйтесь полученным генератором ключей для построения 256-путевого trie-дерева, содержащего 7V случайных ключей при N = 10, 10**, 10 и 10**, с применением операции search, а затем - операции insert в случае промаха при поиске. Сравните полученные ха-