Radix tree

A prefix trie in which each node that is the only child is merged with its parent.

By Claudio Rocchini - Own work, CC BY 2.5, wikimedia

result: number of all internal nodes is at most the radix $r$ of the tree, where $r=2^{x} \forall x \in \mathbb{R}^d \cap x \ge 1$

Edge can be labelled with sequences of elements as well as single elements.

key at each node is compared chunk-of-bits, where quantity of bits in any given chunk is the radix $r$ of the radix tree:

• $r=2$ then radix trie is binary, which minimise sparsity at the expense of maximising trie-depth
• $r \ge 4$ is a power of two, then it is a r-ary trie, which lessen the depth at the expense of some sparseness

Lookup pseudocode:

$"\\begin{algorithm}\n\\caption{Lookup}\n\\begin{algorithmic}\n\\State $\\text{traverseNode} \\gets \\text{root}$\n\\State $\\text{elementsFound} \\gets 0$\n\\While{traverseNode $\\neq \\text{null} \\land \\neg \\text{traverseNode}.\\text{isLeaf}() \\land \\text{elementsFound} < \\text{length}(x)$}\n \\State nextEdge $\\gets$ select edge from traverseNode.edges where edge.label is a prefix of $x.\\text{suffix}(\\text{elementsFound})$\n \\If{nextEdge $\\neq \\text{null}$}\n \\State traverseNode $\\gets$ nextEdge.targetNode\n \\State elementsFound $\\gets$ elementsFound + length(nextEdge.label)\n \\Else\n \\State traverseNode $\\gets$ null\n \\EndIf\n\\EndWhile\n\\State \\Return traverseNode $\\neq \\text{null} \\land \\text{traverseNode}.\\text{isLeaf}() \\land \\text{elementsFound} = \\text{length}(x)$\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 4 Lookup

1:$\text{traverseNode} \gets \text{root}$

2:$\text{elementsFound} \gets 0$

3:while traverseNode $\neq \text{null} \land \neg \text{traverseNode}.\text{isLeaf}() \land \text{elementsFound} < \text{length}(x)$ do

4:nextEdge $\gets$ select edge from traverseNode.edges where edge.label is a prefix of $x.\text{suffix}(\text{elementsFound})$

5:if nextEdge $\neq \text{null}$ then

6:traverseNode $\gets$ nextEdge.targetNode

7:elementsFound $\gets$ elementsFound + length(nextEdge.label)

8:else

9:traverseNode $\gets$ null

10:end if

11:end while

12:

13:return traverseNode $\neq \text{null} \land \text{traverseNode}.\text{isLeaf}() \land \text{elementsFound} = \text{length}(x)$

complexity

Permits lookup, deletion, insertion in $O(k)$ rather than $O(\log n)$

Normally $k \ge \log n$, but in a balanced tree every comparison is a string comparison requires $O(k)$ worse-case time. Whereas in a trie all comparison require constant times, but takes $m$ comparisons to look up a string length $m$