Editing Radix tree (section)

== Comparison to other data structures ==

(In the following comparisons, it is assumed that the keys are of length ''k'' and the data structure contains ''n'' members.)

Unlike [[balanced trees]], radix trees permit lookup, insertion, and deletion in O(''k'') time rather than O(log ''n''). This does not seem like an advantage, since normally ''k'' ≥ log ''n'', but in a balanced tree every comparison is a string comparison requiring O(''k'') worst-case time, many of which are slow in practice due to long common prefixes (in the case where comparisons begin at the start of the string). In a trie, all comparisons require constant time, but it takes ''m'' comparisons to look up a string of length ''m''. Radix trees can perform these operations with fewer comparisons, and require many fewer nodes.

Radix trees also share the disadvantages of tries, however: as they can only be applied to strings of elements or elements with an efficiently reversible mapping to strings, they lack the full generality of balanced search trees, which apply to any data type with a [[total ordering]]. A reversible mapping to strings can be used to produce the required total ordering for balanced search trees, but not the other way around. This can also be problematic if a data type only [[Interface (computer science)|provides]] a comparison operation, but not a (de)[[serialization]] operation.

[[Hash table]]s are commonly said to have expected O(1) insertion and deletion times, but this is only true when considering computation of the hash of the key to be a constant-time operation.  When hashing the key is taken into account, hash tables have expected O(''k'') insertion and deletion times, but may take longer in the worst case depending on how collisions are handled.  Radix trees have worst-case O(''k'') insertion and deletion. The successor/predecessor operations of radix trees are also not implemented by hash tables.