Radix tree

Unlike regular trees (where whole keys are compared en masse from their beginning up to the point of inequality), the key at each node is compared chunk-of-bits by chunk-of-bits, where the quantity of bits in that chunk at that node is the radix r of the radix trie.

As an optimization, edge labels can be stored in constant size by using two pointers to a string (for the first and last elements).

Radix trees are useful for constructing associative arrays with keys that can be expressed as strings.

Insertion adds a new string to the trie while trying to minimize the amount of data stored.

Edge Node To insert a string, we search the tree until we can make no further progress.

[7] Donald Knuth, pages 498-500 in Volume III of The Art of Computer Programming, calls these "Patricia's trees", presumably after the acronym in the title of Morrison's paper: "PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric".

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.

The HAT-trie is a cache-conscious data structure based on radix trees that offers efficient string storage and retrieval, and ordered iterations.

During traversal the algorithm examines the indexed bit of the search key and chooses the left or right sub-tree as appropriate.

One major drawback of the usual radix trees is the use of space, because it uses a constant node size in every level.

This variant of radix tree achieves a higher space efficiency than the one which only allows internal nodes with at least two children.