Cтраница 3
Скорее всего, для типовых приложений это решение должно обеспечивать хорошую производительность. Один из побочных эффектов взаимной зависимости ключей - особенно, при построении строкового индекса для каждой позиции символа - то, что худший случай BST-деревьев не порождает особые проблемы в очень больших текстах, поскольку несбалансированные BST-деревья возникают только в исключительно причудливых конструкциях. [31]
Выбор подходящего значения / немедленно приводит к необходимости отыскания компромисса между временем выполнения и занимаемым объемом памяти. При / 2 в списках пропусков требуется в среднем около IgjV сравнений и 2N связей - этот уровень производительности сравним с лучшей производительностью при использовании BST-деревьев. Для больших значений / время поиска и вставки удлиняется, но дополнительный объем памяти, требуемый для связей, уменьшается. [32]
Как и в случае ряда других методов, упомянутых в этой главе, трудно точно определить производительность метода вставки в корень по сравнению со стандартным методом вставки, поскольку производительность настолько зависит от комбинации различных операций с таблицей символов, что ее трудно проанализировать аналитически. Невозможность проанализировать алгоритм не обязательно должна удерживать от использования вставки в корень, когда известно, что основная масса поисков будет связана с недавно вставленными данными, однако всегда требуются гарантии в отношении производительности; основной темой в главе 13 являются такие методы конструирования BST-деревьев, которые могут предоставить такие гарантии. [33]
В идеальном случае можно было бы сохранять деревья полностью сбалансированными, подобно дереву, показанному на рис. 13.1. Эта структура соответствует бинарному поиску и, следовательно, все поиски могут быть выполнены с использованием менее 7V 1 сравнений, но при этом поддержка динамических вставок и удалений сопряжена с большими затратами. Высокая производительность поиска гарантируется для любого BST-дерева, в котором все внешние узлы расположены в одном, в крайнем случае в двух, нижних уровнях. Существует большое множество таких BST-деревьев, поэтому в плане поддержки сбалансированности дерева имеется некоторая свобода. Если нас устраивают деревья, близкие к оптимальным, возможности еще больше расширяются. [34]
Несмотря на все описанные преимущества, имеется одно важное обстоятельство, которым мы пренебрегли при рассмотрении использования BST-деревьев, patricia - деревьев или TST-деревьев для типичных приложений индексирования текста: сам по себе текст фиксирован, поэтому нет необходимости поддерживать динамические операции insert, как мы привыкли это делать. То есть, как правило, индекс строится один раз, а затем без каких-либо изменений используется для выполнения огромного объема поисков. Следовательно, динамические структуры данных типа BST-деревьев, patricia - деревьев или TST-деревьев могут оказаться вообще не нужными. [35]
Несмотря на гарантию производительности, которую можно обеспечить при использовании рандомизованных и расширенных BST-деревьев, в обоих случаях не исключается вероятность того, что время выполнения отдельной операции поиска может определяться линейной зависимостью. Следовательно, эти методы не помогают ответить на основной вопрос в отношении сбалансированных деревьев: существует ли тип BST-дерева, для которого можно гарантировать логарифмическую зависимость времени выполнения каждой операции insert и search от размеров дерева. В этом и следующем разделах мы рассмотрим абстрактное обобщение BST-деревьев и абстрактное представление этих деревьев в виде типа BST-дерева, которые позволяют утвердительно ответить на этот вопрос. [36]
В остальной части этого раздела рассматривается альтернативное представление trie - деревьев, построенных программой 15.7: trie - дерево тернарного поиска ( ternary search trie - TST), или просто TST-дерево, полная форма которого показана на рис. 15.16. В TST-дереве каждый узел содержит символ и три связи, соответствующие ключам, текущие цифры которых меньше, равны и больше символа узла. Подход эквивалентен реализации узлов trie - дерева в виде BST-деревьев, в который в качестве ключей используются символы, соответствующие ненулевым связям. В соответствующем TST-дереве существования все символы, соответствующие ненулевым связям, явно появляются в узлах - мы находим символы, соответствующие ключам, только при прохождении по средним связям. [37]
На рис. 12.15 и 12.16 показано создание BST-дерева путем вставки последовательности ключей в первоначально пустое дерево с использованием метода вставки в корень. Если последовательность ключей произвольна, построенное таким образом BST-дерево обладает совершенно теми же стохастическими свойствами, что BST-дерево, построенное стандартным методом. Например, леммы 12.6 и 12.7 справедливы и для BST-деревьев, построенных при помощи вставки в корень. [38]
Приведенное описание достаточно для определения алгоритма поиска с использованием 2 - 3 - 4-деревьев, который гарантирует достаточно высокую производительность для худшего случая. Хотя можно было бы создать алгоритмы, действительно выполняющие преобразования с различными типами данных, представляющими 2 -, 3 - и 4-узлы, для большинства встречающихся задач это непосредственное представление не очень удобно в плане реализации. Как и в случае расширенных BST-деревьев, накладные расходы, связанные с манипулированием более сложными структурами узлов, могли бы сделать алгоритмы более медленными, чем стандартный поиск с использованием BST-деревьев. [39]
Приведенное описание достаточно для определения алгоритма поиска с использованием 2 - 3 - 4-деревьев, который гарантирует достаточно высокую производительность для худшего случая. Хотя можно было бы создать алгоритмы, действительно выполняющие преобразования с различными типами данных, представляющими 2 -, 3 - и 4-узлы, для большинства встречающихся задач это непосредственное представление не очень удобно в плане реализации. Как и в случае расширенных BST-деревьев, накладные расходы, связанные с манипулированием более сложными структурами узлов, могли бы сделать алгоритмы более медленными, чем стандартный поиск с использованием BST-деревьев. [40]
Интересно сравнить TST-деревья без многопутевых ветвей в корне со стандартными BST-деревьями при использовании случайных ключей. В соответствии с леммой 15.8, для выполнения поиска в TST-дереве потребуется около InTV сравнений байтов, в то время как в стандартных BST-деревьях требуется около InTV сравнений ключей. В верхней части BST-дерева сравнения ключей могут быть выполнены путем сравнения всего одного байта, но в нижней части для выполнения сравнения ключа может потребоваться несколько сравнений байтов. Это различие в производительности не является решающим. Причины, по которым при использовании строковых ключей TST-деревья предпочтительнее стандартных BST-деревьев, таковы: они обеспечивают быстрое обнаружение промаха при поиске; они непосредственно приспособлены для многопутевого ветвления в корне; и ( что наиболее важно) они хорошо подходят для ключей в виде строк байтов, не являющихся случайными, поэтому длина поиска не превышает длину ключа в TST-дереве. [41]
Для удаления узла с данным ключом из BST-дерева вначале необходимо проверить, находится ли он в одном из поддеревьев. Если да, мы заменяем это поддерево результатом удаления ( рекурсивного) из него узла. Если удаляемый узел находится в корне, дерево заменяется результатом объединения двух поддеревьев в одно. Для выполнения такого объединения существует несколько возможностей. Один из возможных подходов проиллюстрирован на рис. 12.18, а реализация представлена в программе 12.16. Для объединения двух BST-деревьев, все ключи второго из которых заведомо больше ключей первого, ко второму дереву применяется операция partition с целью перемещения в корень наименьшего элемента в этом дереве. На данном этапе левое поддерево корня должно быть пустым ( иначе в нем располагался бы элемент, который меньше элемента в корне - явное противоречие), и задачу можно завершить, заменив эту связь связью с первым деревом. На рис. 12.19 показана последовательность удалений в примере дерева, которая иллюстрирует некоторые из возможных ситуаций. [42]
Последняя операция с АТД таблиц символов, которую мы рассмотрим - операция join. В реализации с использованием BST-дерева это сводится к объединению двух деревьев. Существуют различные алгоритмы для выполнения этой задачи, но каждому из них присущи определенные недостатки. Время выполнения подобного решения не линейно, поскольку для каждой вставки может требоваться линейное время. Другой подход связан с обходом обоих BST-деревьев с целью помещения элементов в массив, объединения их и затем построения нового BST-дерева. [43]
По тем же соображениям, утверждение, аналогичное лемме 13.2, справедливо и по отношению к времени выполнения быстрой сортировки. Но в данном случае это еще более важно, поскольку отсюда следует, что затраты на поиск в дереве близки к усредненным. Независимо от дополнительных затрат на построение деревьев, стандартную реализацию BST-дерева можно использовать для выполнения операций search при затратах, которые зависят только от формы деревьев, при отсутствии вообще каких-либо дополнительных затрат на балансировку. Это свойство важно в типовых приложениях, в которых операции search гораздо более многочисленны, нежели любые другие. Например, описанное в предыдущем абзаце BST-дерево, состоящее из 100000 узлов, могло бы содержать телефонный справочник и использоваться для выполнения миллионов поисков. Можно быть почти уверенным, что каждый поиск потребует затрат, которые отличаются от усредненных затрат, равных приблизительно 23 сравнениям, лишь небольшим постоянным коэффициентом. Поэтому на практике можно не беспокоиться, что для большого количества поисков потребуется количество сравнений, приближающееся к 100000, в то время как при использовании стандартных BST-деревьев это было бы весьма актуально. [44]