Я изучаю различные структуры данных «префикс-поиск», такие как Tries и Trix Trix (Patricia Tries).Использование (без сжатия) Trie
На данный момент у меня есть четкое понимание попыток и попыток radix, а также хорошее понимание их вариантов использования.
Однако, один вопрос выпрыгивает на меня: есть ли какое-либо преимущество в использовании регулярного trie над сжатым trie (например, radix trie)?
Обычное trie просто реализовать: оно хранит один символ на узел. Patricia Trie немного сложнее реализовать: он «сжат» в том смысле, что каждый узел содержит целую строку, а сравнения префикса выполняются с помощью побитового сопоставления.
Поскольку Patricia Trie больше экономит пространство и не жертвует скоростью поиска, существует ли какой-либо прецедент для использования регулярной (не сжатой) Trie, где каждый узел содержит одну букву?
Единственный случай использования, о котором я могу думать, - это то, что ваши «строки» - это нечто иное, чем обычные строки символов (например, массивы более сложных объектов), и поэтому их нельзя сравнивать с помощью побитовых сравнений.
Есть ли другой вариант использования для обычной (несжатой) Trie?
Я бы сказал, что «немного сложнее реализовать» - отличная причина. –