I'm currently trying to figure out the Trie variations and wondered if anyone could clarify a couple of points. (I was very confused with the answer to this question. I tried against triple search trees for autocompletion?, Especially in the first paragraph).
From what I read, the following is true: Suppose that we have stored n elements in data structures, and L is the length of the string we are looking for:
Trie stores its keys on leaf nodes, and if we have a positive hit for the search, it means that it will perform O (L) comparisons. However, for a miss, the average performance is O (log2 (n)).
Similarly, the Radix tree (with R = 2 ^ r) stores keys in leaf nodes and will perform O (L) comparisons for a positive hit. However, misses will be faster and will occur on average in O (logR (n)).
A Trainary Search Trie is essentially a BST with operations <,>, = and with a character stored in each node. Instead of comparing the entire key on a node (as with BST), we only compare the key symbol with this node. In general, if we assume that our alphabet size is A, then if there is a blow, we must perform the (at most) comparison O (L * A) = O (L). If there is no hit, on average we have O (log3 (n)).
As for the Radix tree, if, for example, our alphabet is {0,1}, and we set R = 4, for binary string 0101 we need only two comparisons on the right? Therefore, if the size of our alphabet is A, will we actually perform only comparisons of L * (A / R)? If so, I think it just becomes O (L), but I was curious if that was the correct reasoning.
Thanks for any help you can give people!
source
share