3 ms·
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
by kryps 11y ago
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, ...
- beagle3 11y agoTrue, 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.