Заключение

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

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

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