27 Oct
2006
27 Oct
'06
7:27 p.m.
Nah. You assume branching factor of 2 (and not radix tree but rather a form of binary tree, i.e. AVL, r/b or Patricia - they have that O(log2(num_entries)) behaviour, while radix trees are traversed in O(key_length/branching_factor)).
I assumed a binary radix trie (not tree) because that's the normal cannonical version used by computer science students. Yes, as you outlined, there are many games you can play, if you're willing to make space/time tradeoffs. Regardless of the details, the point remains: if your data structures are largely constant, then you are more efficient searching a small data set vs. searching a large one. Tony