Значения приблизительно IgV членов этой суммы, для которых 2 значительно меньше N, очень близки к 1; значения всех членов, для которых 2 значительно больше N, близки к 0; и значения нескольких членов, для которых 2~ N, лежат в интервале между О и 1. Таким образом, значение суммы приближенно равно IgA. Для более точного определения этого значения требуется выполнение очень сложных математических вычислений (см. раздел ссылок). В приведенном анализе предполагается, что значение w достаточно велико, чтобы во время поиска никогда не возникала ситуация недостаточного количества разрядов; тем не менее, учет действительного значения w лишь уменьшит получаемое значение затрат.

В худшем случае можно было бы получить два ключа, имеющие огромное количество одинаковых разрядов, но вероятность подобного события ничтожно мала. Вероятность того, что утверждение леммы 15.3 для худшего случая не соблюдается, экспоненциально стремится к нулю (см. упражнение 15.29).

Еще один подход к анализу trie-деревьев заключается в обобщении подхода, который использовался при анализе BST-деревьев (см. лемму 12.6). Вероятность того, что к ключей начинаются с О разряда, ?i N - к ключей начинаются с 1 разряда, равна

Следовательно, длина внешнего пути описывается рекуррентным соотношением

1 >

C=N +

v /

Это рекуррентное соотношение аналогично рекуррентному соотношению быстрой сортировки, которое было решено в разделе 7.2, но решить его значительно труднее. Как ни удивительно, но точным решением является выражение для средних затрат на поиск, полученное на основании леммы 15.3, умноженное на N (см. упражнение 15.26). Исследование самого рекуррентного соотношения позволяет понять, почему trie-деревья лучше сбалансированы, чем BST-деревья: вероятность того, что разделение произойдет вблизи середины дерева, гораздо выше, чем в любом другом месте. Поэтому рекуррентное соотношение больше напоминает соотношение сортировки слиянием (приблизительное решение которого равно NlgN), нежели рекуррентное соотношение быстрой сортировки (приблизительное решение которого равно 2 Л IgAO-

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

®

РИСУНОК 15.8 ХУДШИЙ СЛУЧАЙ БИНАРНОГО TRIE-ДЕРЕВА

На этих рисунках показан результат вставки ключей N=01000 и 1=01001 в первоначально пустое бинарное trie-дерево. Как и в DST-depeee (см. рис. 15.4), длина пути ограничивается длиной двоичного представления ключей; однако, как видно из этого примера, пути могут иметь эту длину даже при наличии в trie-дереве всего двух ключей.

ства ключей в дереве (см. рис. 15.8). Количество внутренних узлов может несколько превышать количество ключей.

Лемма 15.4 Тпе-дерево, построенное из N случайных w-разрядных ключей, содержит в среднем около N/\n2~ 1.44 узлов.

Изменив аргумент для леммы 15.3, можно записать выражение для среднего количества узлов в trie-дереве с N ключами (см. упражнение 15.27):

/>о

Математический анализ, позволяющий получить приблизительное значение этой суммы, значительно сложнее, чем приведенный для леммы 15.3, поскольку значения многих членов не равны О или 1 (см. раздел ссылок).

Полученный результат можно подтвердить эмпирически. Например, на рис. 15.9 показано большое дерево, имеющее на 44 процента больше узлов, чем DST-дерево или DST-дерево, построенные из этого же набора ключей. Тем не менее, оно хорошо сбалансировано и затраты на поиск в нем почти оптимальны. На первый взгляд могло бы показаться, что дополнительные узлы приведут к существенному повышению средних затрат на поиск, но в действительности это не так - например, средние затраты на поиск увеличились бы всего на 1 при увеличении вдвое количества узлов в сбалансированном trie-дереве.

Для удобства реализации в профаммах 15.2 и 15.3 предполагалось, что ключи различны и имеют фиксированную длину, дабы иметь уверенность, что рано или поздно ключи окажутся различными, а программы смогут обрабатывать по одному разряду одновременно и никогда не выйдут за пределы разрядов ключей. Для удобства в программах 15.2 и 15.3 также неявно предполагалось, что ключи имеют произвольное количество разрядов, дабы, в конце концов, если пренебречь очень малой (уменьшающейся по экспоненциальному закону) вероятностью, они оказывались различными. Прямым следствием этого допущения является то, что обе программы и их анализ, когда ключами являются строки разрядов переменной длины, требуют нескольких уточнений.

РИСУНОК 15.9 ПРИМЕР TRIE-ДЕРЕВА

Это trie-дерево, построенное в результате вставки около 200 случайных ключей, хорошо сбалансировано, но из-за однонаправленного ветвления содержит на 44 процента больше узлов, чем было бы необходимо в ином случае. (Нулевые связи в листьях не показаны.)

Для использования программ в приведенном виде в отношении ключей переменной длины офаничение различия ключей следует расширить, чтобы ни один из ключей не был префиксом другого ключа. Как будет показано в разделе 15.5, в некоторых приложениях подобное ограничение достигается автоматически. В противном случае такие ключи можно было бы обрабатывать, сохраняя информацию во внутренних узлах, поскольку каждый обрабатываемый префикс соответствует какому-либо внутреннему узлу в trie-дереве (см. упражнение 15.31).

Для достаточно длинных ключей, состоящих из случайных разрядов, утверждения из лемм 15.2 и 15.3 для среднего случая по-прежнему справедливы. В худшем случае высота trie-дерева по-прежнему офаничивается количеством разрядов в самых длинных ключах. Эти затраты могут оказаться весьма существенными, если ключи имеют очень большую длину и, возможно, определенное сходство, как в случае закодированных символьных данных. В следующих двух разделах рассматриваются методы снижения затрат в trie-деревьях для случая длинных ключей. Один из способов сокращения путей в trie-деревьях сводится к свертыванию однонаправленных ветвей в отдельные связи (изящный и эффективный метод выполнения этой задачи будет приведен в разделе 15.3). Другой способ уменьшения длин путей в trie-деревьях предполагает существование более двух связей для каждого узла; этот подход - тема раздела 15.4.

Упражнения

\> 15.11 Нарисуйте trie-дерево, образованное в результате вставки элементов с ключами EASYQUTIONb указанном порядке в первоначально пустое trie-дерево.

15.12 Что происходит в случае применения программы 15.3 для вставки записи, ключ которой равен какому-либо ключу, уже присутствующему в trie-дереве?

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

15.14 Эмпирически сравните высоту, количество узлов и длину внутреннего пути trie-дерева, посфоенного в результате вставки N случайных 32-разрядных ключей в первоначально пустое trie-дерево, с этими же характеристиками стандартного BST-дерева и RB-дерева (глава 13), построенных из тех же ключей, для N = 10, 10 10 и 10 (см. упражнение 15.6).

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

15.16 Реализуйте операцию remove для таблицы символов, основанной на lrie-де-реве.

о 15.17 Реализуйте операцию select для таблицы символов, основанной на trie-дереве.

15.18 Реализуйте операцию sort тя таблицы символов, основанной на trie-дереве.

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