patternMinor
Why aren't tries generally used?
Viewed 0 times
whyusedtriesarengenerally
Problem
To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers.
I believe we can convert numbers to string and store them in tries for fast retrieval.
Is it a bad idea to use tries?
We don't use them because they are hard to code and there are libraries for BSTs or is there some other reason?
I believe we can convert numbers to string and store them in tries for fast retrieval.
Is it a bad idea to use tries?
We don't use them because they are hard to code and there are libraries for BSTs or is there some other reason?
Solution
This is an interesting question. Certainly worth asking.
The choice of a data structure is very much dependent on what you want
to do with it. A more costly sophisticated structure, no matter how
smart, is a bad choice if you can meet your need with something
cheaper in space or time.
As I was writing this answer, I discovered that the wikipedia article
on tries does discuss to a significant extent comparison of tries with other
data structures.
One advantage of binary search trees (BST) is that they keep ordered
lists, for some arbitrary order that can be tested. Actually the
order is often used only to help organization and retrieval, but there
are applications where you want to actually access the elements of your
ordered subset following the order of elements. BST will provide you
with such an order.
I do not see any obvious way of doing it with
tries for an arbitrary order (but I did not try hard). However, tries
do work with lexicographic order, and can be used for lexicographic
enumeration of the keys, using simply a preorder traversal of the
tree implementing it.
Similarly, asking for the current rank of an element in the set
represented by a BST , or accessing an element by its current rank is
fairly easy to implement in $\log n$ time (by keeping track of the
weight of subtrees). It seems not so tractable on a trie, except
again if one is interested in lexicographic order, in which case the
solution is similar to that used for BST.
Another point to consider is cost of basic operations (insertions,
deletions, search). With a balanced BST it is done in $\log n$ time,
where $n$ is the number of elements. For a trie, the cost is linear in
the size of the element representation. It is hard to compare the two
kinds of cost, and one would think the choice is very much problem
dependent. This also applies to such operation as access by rank, or
rank retrieval.
The cost of number representation in a BST or in a trie may also be an
issue, as a trie will represent each digit separately (up to some
optimizations). It is possible that, for very large numbers, expressed
with a large base, the trie representation would be a better choice. I
am not sure.
There is probably more to say. The conclusion is that it is probably
worth thinking whether tries can be used, but it may be actually limited.
The choice of a data structure is very much dependent on what you want
to do with it. A more costly sophisticated structure, no matter how
smart, is a bad choice if you can meet your need with something
cheaper in space or time.
As I was writing this answer, I discovered that the wikipedia article
on tries does discuss to a significant extent comparison of tries with other
data structures.
One advantage of binary search trees (BST) is that they keep ordered
lists, for some arbitrary order that can be tested. Actually the
order is often used only to help organization and retrieval, but there
are applications where you want to actually access the elements of your
ordered subset following the order of elements. BST will provide you
with such an order.
I do not see any obvious way of doing it with
tries for an arbitrary order (but I did not try hard). However, tries
do work with lexicographic order, and can be used for lexicographic
enumeration of the keys, using simply a preorder traversal of the
tree implementing it.
Similarly, asking for the current rank of an element in the set
represented by a BST , or accessing an element by its current rank is
fairly easy to implement in $\log n$ time (by keeping track of the
weight of subtrees). It seems not so tractable on a trie, except
again if one is interested in lexicographic order, in which case the
solution is similar to that used for BST.
Another point to consider is cost of basic operations (insertions,
deletions, search). With a balanced BST it is done in $\log n$ time,
where $n$ is the number of elements. For a trie, the cost is linear in
the size of the element representation. It is hard to compare the two
kinds of cost, and one would think the choice is very much problem
dependent. This also applies to such operation as access by rank, or
rank retrieval.
The cost of number representation in a BST or in a trie may also be an
issue, as a trie will represent each digit separately (up to some
optimizations). It is possible that, for very large numbers, expressed
with a large base, the trie representation would be a better choice. I
am not sure.
There is probably more to say. The conclusion is that it is probably
worth thinking whether tries can be used, but it may be actually limited.
Context
StackExchange Computer Science Q#43795, answer score: 6
Revisions (0)
No revisions yet.