CODEWITHSUNDEEP
algorithmdata-structureslanguage-agnostictriepatricia-trie
Siler
Siler

Reputation: 9504

Uses of (non-compressed) Trie

I'm studying various "prefix-lookup" data structures, such as Tries and Radix Tries (Patricia Tries).

At this point, I have a solid understanding of both tries and radix tries, as well as a good understanding of their use cases.

However, one question jumps out at me: is there any advantage to using a regular trie over a compressed trie (such as a radix trie)?

A regular trie is simple to implement: it stores one character per node. A Patricia Trie is a bit more difficult to implement: it is "compressed" in the sense that each node contains an entire string, and prefix comparisons are done using bitwise matching.

Since a Patricia Trie is more space efficient, and doesn't sacrifice lookup speed, is there any use case for using a regular (non-compressed) Trie where every node contains a single letter?

The only use case I can think of is if your "strings" are something other than regular strings of characters (like arrays of more complex objects), and therefore cannot be compared using bit by bit comparisons.

Is there any other use case for a regular (non-compressed) Trie?

Upvotes: 0

Views: 193

Answers (2)

piotrek
piotrek

Reputation: 14550

i'm guessing they are just easier to understand and make analysis/design of algorithms easier. So they are perfect for educational purpose before compressed trees are introduced

Upvotes: 0

Cybercartel
Cybercartel

Reputation: 12592

Most likely when insertion in compressed trie is too expensive.

Upvotes: 1

Related Questions