Попытка против тройных деревьев поиска для автозаполнения?

Я прошел через попытки и тройные поисковые деревья, и у меня есть некоторые вопросы по ним. У меня есть Googled для ответов, но я не могу получить конкретный ответ для них. Итак, вот мои вопросы.

Если попытки неэффективны по пространству, а TST объединяют лучшее из BST и пытается, то ли это означает, что попытки практически не используются вообще?
Предполагая, что TST используются для автозавершения, как это будет работать в случае Google? Я имею в виду, что практически у нас нет фиксированного набора слов и т.д., Так как будет построено дерево для TST?

Ответ 1

Tries и тройные деревья поиска представляют собой коммивояние времени/пространства. Если в вашем алфавите есть k символов, то каждый node в trie содержит k указателей плюс один дополнительный бит для того, кодирует ли слово node слово. Поиск слова длиной L всегда занимает время O (L). Тройное дерево поиска хранит три указателя на node, плюс один символ и один бит для того, кодирует ли слово node слово. Глядя на слово длины L, требуется время O (L log k). (Если у вас есть статическое тернарное дерево поиска, вы можете построить TST с помощью сбалансированных по весу деревьев, что улучшает время поиска до O (L + log k), но делает вставки непомерно дорогостоящими.)

В случаях, когда каждый node в trie имеет большую часть своих дочерних элементов, Trie значительно эффективнее и эффективнее по времени, чем тройное дерево поиска. Если каждый node хранит сравнительно мало дочерних узлов, троичное дерево поиска намного более эффективно. Как правило, попытки выполняются намного быстрее, чем тройные деревья поиска, потому что требуется меньше указателей.

Итак, в сортировке ни одна структура не лучше, чем другая. Это зависит от того, какие слова хранятся.

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

Что касается того, как их создавать - обе попытки и тройные деревья поиска поддерживают эффективную вставку одного слова. Они не должны быть построены из фиксированного набора слов заранее.

Надеюсь, это поможет!