I'm currently trying to get my head around the variations of Trie and was wondering if anyone would be able to clarify a couple of points. (I got quite confused with the answer to this question Tries versus ternary search trees for autocomplete?, especially within the first paragraph).
From what I have read, is the following correct? Supposing we have stored n elements in the data structures, and L is the length of the string we are searching for:
A Trie stores its keys at the leaf nodes, and if we have a positive hit for the search then this means that it will perform O(L) comparisons. For a miss however, the average performance is O(log2(n)).
Similarly, a Radix tree (with R = 2^r) stores the keys at the leaf nodes and will perform O(L) comparisons for a positive hit. However misses will be quicker, and occur on average in O(logR(n)).
A Ternary Search Trie is essentially a BST with operations <,>,= and with a character stored in every node. Instead of comparing the whole key at a node (as with BST), we only compare a character of the key at that node. Overall, supposing our alphabet size is A, then if there is a hit we must perform (at most) O(L*A) = O(L) comparisons. If there is not a hit, on average we have O(log3(n)).
With regards to the Radix tree, if for example our alphabet is {0,1} and we set R = 4, for a binary string 0101 we would only need two comparisons right? Hence if the size of our alphabet is A, we would actually only perform L * (A / R) comparisons? If so then I guess this just becomes O(L), but I was curious if this was correct reasoning.
Thanks for any help you folks can give!
