Попытки и троичные деревья поиска представляют собой компромисс между временем и пространством. Если в вашем алфавите есть k символов, то каждый узел в дереве содержит k указателей плюс один дополнительный бит, определяющий, кодирует ли узел слово. Поиск слова длины L всегда занимает время O(L). Троичное дерево поиска хранит три указателя на узел, плюс один символ и один бит, указывающий, кодирует ли узел слово. Поиск слова длины L занимает время O(L log k). (Если у вас есть статическое троичное дерево поиска, вы можете построить TST, используя деревья со сбалансированным весом, что сокращает время поиска до O(L + log k), но делает вставки непомерно дорогими.)
Для случаев, когда каждый узел в дереве использует большинство своих дочерних элементов, Trie значительно более эффективно использует пространство и время, чем троичное дерево поиска. Если каждый узел хранит сравнительно мало дочерних узлов, троичное дерево поиска занимает гораздо больше места. Как правило, попытки выполняются намного быстрее, чем троичные деревья поиска, потому что требуется меньше косвенных указателей.
Таким образом, ни одна из структур не является строго лучшей, чем другая. Это зависит от того, какие слова хранятся.
Чтобы немного перепутать вещи, краткие попытки начинают быть жизнеспособной альтернативой обоим вышеперечисленным подходам. Они используют пространство лучше, чем попытки, хотя время поиска, как правило, намного медленнее. Опять же, от приложения зависит, будут ли они лучше или хуже двух других вариантов.
Что касается того, как их строить - и попытки, и троичные деревья поиска поддерживают эффективную вставку одного слова. Их не нужно заранее строить из фиксированного набора слов.
Надеюсь это поможет!
person
templatetypedef
schedule
10.06.2012
