Программа 15.8 Поиск и ваавка в TST-дерево сущеавования

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

d; node *1, *m, *r; 0; г = 0;

0; m

private: struct node { Item item; int node(int k) { d = k; 1 =

typedef node *llnk; llnk head; Item nullltem;

Item searchR (link h. Key v, int d) { int i =s digit (v, d) ;

if (h s= 0) return nullltem; if (i == NULLdigit)

{ Item dummy(v); return dummy; } if (i < h->d) return searchR(h->l, v, if (i 8= h->d) return searchR(h->m, v, if (i > h->d) return searchR(h->r, v.

d) ;

d+1) d);

i (h (i (i (i (i

void insertR (links h. Item x, int d) = digit (X.keyO , d) ; = 0) h = new node(i); == NULLdigit) return; < h->d) insertR(h->l, x, == h->d) insertR(h->m, x > h->d) insertR(h->r, x,

public: ST(int maxN)

{ head = 0; } Item search (Key v)

{ return searchR(head, void insert(Item x)

{ insertR(head, x, 0);

d+1) d) ;

V, 0); } 1

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

Лемма 15.7 Для выполнения поиска или вставки в полное TST-дерево требуется время, пропорциональное длине ключа. Количество связей в TST-дереве превышает кqлuчecmвo символов во всех ключах не более чем в три раза.

В худшем случае каждый символ ключа соответствует полному несбалансированному /?-арному узлу, вытянутому наподобие односвязного списка. Вероятность возникновения этого худшего случая в случайном дереве исключительно мала. Скорее можно ожидать, что придется выполнить InT? или менее сравнений на первом уровне (поскольку корневой узел ведет себя подобно BST-дереву, состояще-

РИСУНОК 15.17 TST-ДЕРЕВЬЯ СУЩЕСТВОВАНИЯ

TST-дерево существования содержит по одному узпу для каждой буквы, но каждый узел имеет только 3 дочерних узла, а не 26. Деревья на трех верхних рисунках - это TST-деревья, соответствующие примеру вставки из рис. 15.15, за исключением того, что к каждому ключу дописывается завершающий символ. Это позволяет снять ограничение, связанное с тем, что ни один ключ не может быть префиксом другого. В таком случае можно, например, вставить ключ theory (рисунок внизу).

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

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

LDS-361-Н-4 LDS-485-М.4-Н-317 LDS-625 D-73-1986 LJN-679-М-48 1985 LQP-425-М-56-1991 LTK-6Q15-P-63-1988 LVM-455Л-67-1974

WAFR 5054 33

WKG -6875

WLSOC----2542----30

WPHIL -4060 2-55

WPHYS 39--1-30

WROM 5350-.65 5

WUS. WUS-

.10706-.12692.

-7-10 -4-27

РИСУНОК 15.18 ПРИМЕР СТРОКОВЫХ КЛЮЧЕЙ (НОМЕРОВ БИБЛИОТЕЧНЫХ ФУНКЦИЙ)

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

Главное достоинство использования TST-деревьев заключается в том, что они легко приспосабливаются к неодно-родностям в ключах, возникновение которых весьма вероятно в реальных приложениях. Это является следствием двух основных эффектов. Во-первых, ключи в реальных приложениях образуются из больших наборов символов, а использование конкретных символов в наборах далеко от однородного - например, в конкретном наборе строк, скорее всего, будет использоваться только небольшая часть возможных символов. При использовании TST-деревьев можно задействовать 128- или 256-символьное кодирование, не беспокоясь о лишних затратах для узлов с 128- или 256-путевым ветвлением и не будучи вынужденными определять, какие наборы символов действительно имеют значение. Наборы символов алфавитов, отличных от латинского, могут содержать тысячи символов - TST-деревья особенно подходят для строковых ключей, состоящих из таких символов. Во-вторых, ключи в практических приложениях часто имеют структурированный формат, различающийся от приложения к приложению, когда в одной части ключа используются только буквы, в другой - только цифры, а специальные символы служат разделителями (см. упражнение 15.72). Например, на рис. 15.18 приведен список кодов для базы данных онлайновой библиотеки. В случае таких ключей некоторые из узлов trie-дерева могут быть представлены унарными узлами в TST-дереве (для мест, где все ключи содержат разделители), другие могут быть представлены 10-узловыми BST-деревьями (для мест, где все ключи содержат цифры).

10 программой FinePnnt - KynHTbWrtw finepnnt с(

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

Второе практическое преимущество поиска, основанного на TST-деревьях, по сравнению со множеством других алгоритмов заключается в том, что обнаружение промахов при поиске, скорее всего, будет исключительно эффективным даже при длинных ключах. Часто для обнаружения промаха при поиске в алгоритме используется лишь несколько сравнений байтов (и поддерживается несколько указателей). Как было показано в разделе 15.3, для обнаружения промаха при поиске в хеш-таблице, которая содержит N ключей, требуется время, пропорциональное длине ключа (для вычисления хеш-функции); для выполнения той же операции в дереве поиска требуется, по меньшей, мере IgiV сравнений ключей. Даже в patricia-дереве для обнаружения случайного промаха при поиске требуется Ig/V сравнений разрядов.

В табл. 15.2 приведены экспериментальные данные, подтверждающие выводы, приведенные в двух предьщущих абзацах.

Таблица 15.2 Экспериментальные данные исследования поиска

с использованием строковых ключей

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

конструирование промахи при поиске

Ключ:

В Стандартное BST-дерево (программа 12.8)

Н Хеширование с раздельным связыванием (М = N/5) (программа 14.3)

Т TST-дерево (программа 15.8)

Т* TST-дерево с R-путевым ветвлением в корне (программы 15.11 и 15.12)

Третья причина привлекательности TST-деревьев заключается в том, что они поддерживают более общие операции, нежели рассмотренные операции таблиц символов. Например, программа 15.9 разрешает не указывать отдельные символы в искомом ключе и выводит все ключи в структуре данных, которые соответствуют указанным цифрам ключа поиска. Подобный пример показан на рис. 15.19. Очевидно, что за счет внесения небольших изменений, эту программу можно приспособить к посещению всех соответствующих ключей, как это делается для выполнения операции sorf, а не просто для их вывода (см. упражнение 15.58).