Использование (без сжатия) Trie

Question

Я изучаю различные структуры данных «префикс-поиск», такие как Tries и Trix Trix (Patricia Tries).

На данный момент у меня есть четкое понимание попыток и попыток radix, а также хорошее понимание их вариантов использования.

Однако, один вопрос выпрыгивает на меня: есть ли какое-либо преимущество в использовании регулярного trie над сжатым trie (например, radix trie)?

Обычное trie просто реализовать: оно хранит один символ на узел. Patricia Trie немного сложнее реализовать: он «сжат» в том смысле, что каждый узел содержит целую строку, а сравнения префикса выполняются с помощью побитового сопоставления.

Поскольку Patricia Trie больше экономит пространство и не жертвует скоростью поиска, существует ли какой-либо прецедент для использования регулярной (не сжатой) Trie, где каждый узел содержит одну букву?

Единственный случай использования, о котором я могу думать, - это то, что ваши «строки» - это нечто иное, чем обычные строки символов (например, массивы более сложных объектов), и поэтому их нельзя сравнивать с помощью побитовых сравнений.

Есть ли другой вариант использования для обычной (несжатой) Trie?

Answer 1

Скорее всего, если вставка в сжатом три слишком дорогая.

Answer 2

i угадывание их проще понять и упростить анализ/дизайн алгоритмов. Поэтому они идеально подходят для образовательных целей до введения сжатых деревьев.