Три против Radix Tree против Патрисии Три
Как я понимаю (также отсюда), сложность памяти этих DS можно заказать как Trie > Radix > Patricia. Но как насчет сложности времени? Я предполагаю, что они почти одинаковы.
Если упомянуть мою проблему, я хочу сделать много поисковых запросов с префиксами из предварительно созданного словаря. Память не большая проблема для меня. Я хочу использовать самый быстрый DS.
HAT-Trie лучше всего подходит для меня, но он слишком сложен для реализации. Должен ли я использовать троичные поисковые деревья вместо любых DS, упомянутых выше?
Большое спасибо!
1 ответ
Хет-три может быть не так сложно. Посмотрите на конечный автомат и ахорадушный алгоритм. По сути, это поиск по дереву в ширину.