Hacker News Reader

For critbit trees the entire string _up to_ the critical bit where the string differs from all others already in the datastructure needs to be scanned.

critbit trees degenerate badly if you store strings and their prefixes, e.g. storing a, aa, aaa, ...

View on HN

True, but that's not worse than "standard" tries, and big O()-wise, not even worse than hashing - you do have to scan through the string to hash it.

Worst case data for a critbit tree is also worst case for any other kind of trie, and better than worst case for a classic hash (which is O(items in table) and can often be triggered by an adversary). Constants are different, though.

Reply on news.ycombinator.com