That's why C++ STL's std::map and std::set are typically implemented using (some flavor of) binary trees.
I always wondered why. In my coding experience, for most generic coding tasks, key-value dictionary backed by a hash was a better go-to construct. I wonder if it has something to do with processor branch prediction; a random guess would be that it would be hard to do b-tree branch prediction on a well balanced tree, while hash is constant.
Its a very good point that when it comes to hashing a very long key string this crit-bit tree structure has interesting properties. I wonder if this structure could be used to implement a good(better?) average case implementation of the LCS problem. http://en.wikipedia.org/wiki/Longest_common_subsequence_prob...