> 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 counting, a crit-bit tree is worse on this input than a balanced search tree.
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) comparison of the key value - for a total of O(string-length).
A balanced tree does O(log-n) comparisons, of O(string-length) each (the final one giving the confirmation, which was an independent step for both hash and critbit trees).
This is true even on this specific input. It boils down to how the amortized single-character comparison compares to a cache miss.
If crit-bit trees leafs are packed in a cache-friendly way (they are constant size, so this might actually be easy to arrange), they are likely to perform at least as well as balanced trees.
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.
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 counting, a crit-bit tree is worse on this input than a balanced search tree.