РИСУНОК 15.5 ПРИМЕР DST-ДЕРЕВА

Это DST-дерево, построенное в результате вставки около 200 случайных ключей, хорошо сбалансировано.

Упражнения

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

15.2 Покажите последовательность вставки ключей А В С D Е F G, приводящую к образованию полностью сбалансированного DST-дерева, одновременно являющегося допустимым BST-деревом.

15.3 Покажите последовательность вставки ключей А В С D Е F G, приводящую к образованию полностью сбалансированного DST-дерева, характеризующегося тем, что каждый его узел имеет ключ, который меньще ключей всех узлов в его поддереве.

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

15.5 Можно ли в DST-деревьях хранить записи с дублированными ключами, как это возможно в BST-деревьях? Обоснуйте свой ответ.

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

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

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

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

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

15.2 Trie-деревья

в этом разделе мы рассмотрим деревья поиска, которые позволяют использовать разряды ключей для проведения поиска подобно DST-деревьям, но ключи которых упорядочены, что позволяет поддерживать рекурсивные реализации функции sort и других функций таблиц символов, как это делалось в отношении BST-деревьев. Основная идея заключается в хранении ключей только в нижней части дерева, в листьях. Результирующая структура данных обладает рядом полезных свойств и служит основой для нескольких эффективных алгоритмов поиска. Впервые структура была создана Брианде (Briandais) в 1959 г., и поскольку она оказалась удобной для поиска (re/r/eval), в 1960 г. Фредкин (Fredkin) применил к ней специальное название trie. С некоторой долей юмора обычно это слово произносится как трай-и (try - попытка, англ.), дабы отличать его от tree . Вероятно, в соответствии с принятой в книге терминологией, подобного рода деревья следовало бы называть trie-деревьями бинарного поиска , тем не менее, повсеместно используется термин trie-дерево и все его понимают. В этом разделе рассматривается базовая бинарная версия, в разделе 15.3 - важную вариацию, а в разделах 15.4 и 15.5 - базовую версию trie-деревьев со многими путями и ее вариации.

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

В trie-дереве ключи хранятся в листьях бинарного дерева. Вспомните из раздела 5.4, что лист в дереве - это узел, не имеющий дочерних узлов, что отличает его от внешнего узла, который интерпретируется как нулевой дочерний узел. В бинарнЬм дереве под листом понимается внутренний узел, левая и правая связи которого являются нулевыми. Хранение ключей в листьях, а не во внутренних узлах позволяет использовать разряды ключей для проведения поиска, как это делалось применительно к DST-деревьям в разделе 15.1, сохраняя при этом свойство, что все ключи, текущий разряд которых равен О, попадают в левое поддерево, а все ключи, текущий разряд которых равен 1 - в правое.

Определение 15.1 Под trie-деревом понимается бинарное дерево, имеющее ключи, связанные с каждым из его листьев, и рекурсивно определенное следующим образом. Trie-дерево, состоящее из пустого набора ключей, представляет собой нулевую связь. Trie-дерево, состоящее из единственного ключа - это лист, содержащий данный ключ. И, наконец, trie-дерево, содержащее намного больше одного ключа - это внутренний узел, левая связь которого ссылается на trie-дерево с ключами, начинающимися с О разряда, а правая - на trie-дерево с ключами, начинающимися с 1 разряда, причем для конструирования поддеревьев ведущий разряд такого дерева должен быть удален.

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

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

Программа 15.2 Поиск в trie-дереве

В этой функции разряды ключа используются для управления переходом по ветвям при перемещении вниз по дереву, как это делается в программе 15.1 для DST-деревьев. Возможны три варианта: если поиск достигает листа (с обоими нулевыми связями), значит, это уникальный узел trie-дерева, который может содержать запись с ключом V. В такой ситуации выполняется проверка, действительно ли этот узел содержит V (попадание при поиске) или какой-либо ключ, ведущие разряды которого совпадают с v (промах при поиске). Если поиск достигает нулевой связи, то вторая связь родительского узла не должна быть нулевой и, следовательно, в trie-дереве существует какой-либо другой ключ, соответствующий разряд которого отличается от ключа поиска, и имеет место промах при поиске. В программе предполагается, что ключи являются различными и (если ключи могут иметь различную длину) ни один ключ не является префиксом другого ключа. Член item не используется в узлах, которые не являются листьями.

private:

Item searchR (link h, Key v, int d) { if (h == 0) return nullltem;

if (h->l == 0 && h->r = 0) { Key w = h->item.lcey 0 ;

return (v == w) ? h->item : nullltem; } if (digit (v, d) ==0)

return searchR(h->l, v, d+1); else return searchR(h->r, v, d+1) ;

public: Item search (Key v)

{ return searchR(head, v, 0) ; }

Для вставки ключа в trie-дерево вначале, как обычно, выполняется поиск. Если поиск завершается на нулевой связи, она, как обычно, заменяется связью с новым содержащим ключ листом. Но если поиск заканчивается в листе, необходимо продолжить перемещение вниз по дереву, добавляя внутренний узел для каждого разряда, значение которого для искомого и найденного ключей совпадает; этот процесс должен завершиться тем, что оба ключа в листьях, являющихся дочерними узлами внутреннего узла, будут соответствовать первому разряду, в котором они отличаются. Пример поиска и вставки в trie-дереве показан на рис. 15.6; процесс построения trie-дерева за счет вставки ключей в первоначально пустое дерево представлен на рис. 15.7. Программа 15.3 представляет собой полную реализацию алгоритма вставки.