> Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data. Consider a crit-bit tree over variable-length bit strings. The set 1, 11, 111, ... (with n bit strings) has depth n. Depending on how you count, it can be argued that this is still substantially better than the worst-case of hash tables, but in all of the ways I think of count…
Big O notation, it isn't. The big question is the cost of different types of comparisons. The most important thing to remember is that a crit-bit lookup does O(string-length) "critical" bit lookups, and then an O(string-length) final comparison - for a total of O(string-length). Whereas a hash lookup usually does O(string-length) computation of the hash value, average case O(1) lookups, and then O(string-length) comp…
Given a query string of length k and cache lines that store B bits, the crit-bit trie for the bad input uses Theta(k) computations and causes Theta(k) cache misses, I think. A balanced tree holding the same set causes Theta(k * lg n) computations and O(lg n + (k * lg n / B)) cache misses, I think. My understanding is that lg n / B is frequently much less than 1, even for small cache line sizes, so that the balanced tree will generally use less I/O than a crit-bit tree but more computation.