Radix tree is a uni-bit binary tree used for longest prefix matching. This page describes insertion, deletion, and lookup algorithms of radix tree. An implementation of radix tree is on my github repository.

Let's think about the following five entries as the example of the radix tree.

This figure depicts the radix tree of the five entries above. Radix tree is a uni-bit binary tree. Each node is placed so that the depth of each node is the prefix length plus one.

The lookup procedure is just traversing the binary tree according to a bit in the given key corresponding to the depth of the tree. The d-th bit of the given key will be checked when traversing from a node at the depth of d to that at the depth of d+1 in the tree.

For example, the lookup procedure of the key 10101 to the example shown above will be

1. checking the first bit of the key (=1), then traversing to the right (node a to node d),
2. checking the second bit of the key (=0), then traversing to the left (node d to node e),
3. checking the third bit of the key (=1), then traversing to the right (node e to node i),
4. checking the fourth bit of the key (=0), then traversing to the left,
5. and reaching at an empty (null) node, then backtracking to the parents to find a node with valid prefix information (node i in this case). Thus, it finds the resultant node, P2, corresponding to the given key 10101.

Insertion of a node to a radix tree is very simple. As the position of a node is at the depth of the prefix length plus one, the same procedure as lookup can be used to find the position to insert. We add a new node without valid prefix information, illustrated as gray fill-in circles in the example figure, when it reaches an empty node.

As an eample, assuming P1, P2, P3, and P4 are already inserted as shown in the following figure, and P5 is to be inserted to this radix tree.

The position of a node is at the depth of the prefix length plus one. Therefore, the depth of P5 will be at the depth of 6. To find the position to be inserted, the same procedure as lookup can be used. In case that it reaches an empty node, we add a new node without valid prefix information (illustrated as orange fill-in circle in the figure below).

Deletion of a node from a radix tree is also simple. We can remove prefix information from the corresponding node. We recursively remove nodes without valid prefix information and any descendant nodes.

For example, to remove P5 from the example figure above, we first remove the prefix information from node h. We then remove node h as it has no descendant node and no prefix information. We then traverse the tree backward to remove useless nodes. Nodes g and f are removed as they will have no descendant node as well as no prefix information.