5
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Welcome to SE Computer Science. Have you done any reasearch on this (interesting) question? What have you found? You are expected to ask after documenting a bit, if possible, the context of your question (work sharing, if you wish). $\endgroup$
    – babou
    Jun 21, 2015 at 10:35
  • $\begingroup$ A possible point here is that the ordering between numbers is not the same as the ordering on strings. Whereas we have $12 < 104$ as numbers, we have $104< 12$ alphabetically. $\endgroup$ Jun 21, 2015 at 10:53
  • $\begingroup$ You say "we prefer to use red black BSTs". Who is we? You seem to be assuming no one uses a trie. Where did this assumption come from? Do you have any evidence for it? As they say on Wikipedia, "citation needed". $\endgroup$
    – D.W.
    Jun 21, 2015 at 23:07
  • $\begingroup$ Well, I was in general referring to programmers (and in particular competitive programmers). $\endgroup$
    – Aman Goel
    Jun 22, 2015 at 10:51

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you for you answer. Well, what if I need just insert, delete and find queries. Is it advisable to use tries in that case (assuming my data is a 32 bit integer)? I discussed with my friend about this and he said that the comparisons of keys in BST (integer keys) is implemented at hardware level and might be faster. Does that correlate to this ? $\endgroup$
    – Aman Goel
    Jun 22, 2015 at 10:53
  • $\begingroup$ @AmanGoel I think your friend is probably right. A trie could possibly be considered if you used almost all the 32 bits integers (big memory :). Recall that the number of comparison in a trie operation is the length of the representation of one element (32), while it is the log of the number of element stored in a BST. Of course, if the trie comparisons are very fast, while the BST comparisons are slow, you might reconsider. But I doubt it. It might be interesting to do some measurements, with two good implementations, and see when the costs balance. There is also the issue of space. $\endgroup$
    – babou
    Jun 22, 2015 at 12:30
  • $\begingroup$ @AmanGoel But if you were using very long integers, implemented as linked lists of, say, 16 bits integers, i.e. in base $2^{16}$. Then you would probably consider using a trie rather than a BST. The cost of $\log_2 n$ long integer comparisons would probably be a lot more expensive than the lexicographic access of the trie. $\endgroup$
    – babou
    Jun 22, 2015 at 12:36
  • 1
    $\begingroup$ @AmanGoel and of course you have the right to show whether you consider answers useful by upvote, downvote and acceptance. For more details see .cs.stackexchange.com/tour $\endgroup$
    – babou
    Jul 3, 2015 at 22:30
  • $\begingroup$ I am a new user and so my vote will be publically shown when I cross a minimum reputation sir, which I do not have because I am not a very active user. $\endgroup$
    – Aman Goel
    Jul 5, 2015 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.