Author: Andrew Miller 2012-06-19 18:29:45
Published on: 2012-06-19T18:29:45+00:00
Alan Reiner suggests that a PATRICIA tree/trie would be ideal for the purpose as it has a completely deterministic structure and is more space-efficient than other options. However, he has been unable to find satisfactory implementations of this structure. PATRICIA Tries, also known as Radix trees, have worst-case O(k) complexity, where k is the number of bits in the key. The number of elements stored must be less than 2^k to avoid hash collisions, which would result in O(log N) complexity.
Updated on: 2023-06-06T05:51:41.366580+00:00