Editing Radix tree (section)

=== Insertion ===

To insert a string, we search the tree until we can make no further progress. At this point we either add a new outgoing edge labeled with all remaining elements in the input string, or if there is already an outgoing edge sharing a prefix with the remaining input string, we split it into two edges (the first labeled with the common prefix) and proceed. This splitting step ensures that no node has more children than there are possible string elements.

Several cases of insertion are shown below, though more may exist. Note that r simply represents the root. It is assumed that edges can be labelled with empty strings to terminate strings where necessary and that the root has no incoming edge. (The lookup algorithm described above will not work when using empty-string edges.)

<gallery widths="300" heights="200" mode="nolines">
File:Inserting the string 'water' into a Patricia trie.png|Insert 'water' at the root
File:Insert 'slower' with a null node into a Patricia trie.png|Insert 'slower' while keeping 'slow'
File:Insert 'test' into a Patricia trie when 'tester' exists.png|Insert 'test' which is a prefix of 'tester'
File:Inserting the word 'team' into a Patricia trie with a split.png|Insert 'team' while splitting 'test' and creating a new edge label 'st'
File:Insert 'toast' into a Patricia trie with a split and a move.png|Insert 'toast' while splitting 'te' and moving previous strings a level lower
</gallery>