Заключение

В разделах 3 и 4 использованы старые методы для единообразного представления и анализа быстрой сортировки и троичных деревьев поиска при работе с составными ключами. В следующих разделах описаны соответствующие коды.

Быстрая сортировка для составных ключей приводит к программе 1 и ее улучшенному варианту, который может конкурировать с лучшими из известных алгоритмов сортировки строк. Этим, однако, не исчерпываются возможные применения алгоритма, лежащего в основе программы. Мы полагаем, что быстрая сортировка для составных ключей может оказаться практичной в системах сортировок с составными полями – таких, как описанная Линдерманом [12]. Этот алгоритм можно использовать также для сортировки целых чисел, если сравнивать их побайтно.

В разделе 5 показано, что троичные деревья поиска обеспечивают эффективную реализацию таблиц имен, а в разделе 6, – что эти структуры могут быстро отвечать на более сложные запросы. Троичные деревья поиска особенно хорошо подходят для случая, когда ключами, по которым происходит поиск, являются длинные строки, и они уже используются в коммерческой системе. Продвинутые алгоритмы поиска обещают оказаться полезными в практических приложениях, кроме того, они представляют ряд интересных проблем алгоритмического анализа.

Глоссарий
 

Term	Термин
balanced tree	сбалансированное дерево
binary tree	бинарное дерево
divide-and-conquer algorithm	алгоритм декомпозиции; алгоритм типа "разделяй и властвуй"
external path length	длина внешнего пути (сумма длин путей от корня дерева к его листьям)
Hamming distance	расстояние Хемминга
hash function	хеширующая функция; функция расстановки
in-place	на месте (без дополнительной памяти)
internal path length	длина внутреннего пути (сумма длин путей от корня дерева ко всем его внутренним узлам)
key	ключ (значение, по которому производится поиск)
multikey data	данные с составными ключами
node	узел
partial match	частичное совпадение
partition	разбиение
query	запрос
Quicksort	быстрая сортировка
radix sort	поразрядная сортировка
search tree	дерево поиска
searching	поиск
sorting	сортировка
string key	текстовый ключ
suffix tree	суффиксное дерево
symbol table	таблица имен
ternary tree	троичное дерево
tournament tree	турнирное дерево
trie	бор; TRIE-структура