Editing Radix tree (section)

== Operations ==

Radix trees support insertion, deletion, and searching operations. Insertion adds a new string to the trie while trying to minimize the amount of data stored. Deletion removes a string from the trie. Searching operations include (but are not necessarily limited to) exact lookup, find predecessor, find successor, and find all strings with a prefix. All of these operations are O(''k'') where k is the maximum length of all strings in the set, where length is measured in the quantity of bits equal to the radix of the radix trie.

=== Lookup ===
[[File:An example of how to find a string in a Patricia trie.png|Finding a string in a Patricia trie|thumb|313x313px]] The lookup operation determines if a string exists in a trie. Most operations modify this approach in some way to handle their specific tasks. For instance, the node where a string terminates may be of importance. This operation is similar to tries except that some edges consume multiple elements.

The following pseudo code assumes that these methods and members exist.

''Edge''
* ''Node'' targetNode
* ''string'' label

''Node''
* ''Array of Edges'' edges
* ''function'' isLeaf()

{{clear}}
 '''function''' lookup(''string'' x)
 {
     ''// Begin at the root with no elements found''
     '''Node''' traverseNode := ''root'';
     '''int''' elementsFound := 0;
     
     ''// Traverse until a leaf is found or it is not possible to continue''
     '''while''' (traverseNode != ''null'' && !traverseNode.isLeaf() && elementsFound < x.length)
     {
         ''// Get the next edge to explore based on the elements not yet found in x''
         '''Edge''' nextEdge := '''select''' edge
                          '''from''' traverseNode.edges 
                          '''where''' edge.label ''is a prefix of'' x.suffix(elementsFound)
             ''// x.suffix(elementsFound) returns the last (x.length - elementsFound) elements of x''
     
         ''// Was an edge found?''
         '''if''' (nextEdge != ''null'')
         {
             ''// Set the next node to explore''
             traverseNode := nextEdge.targetNode;
     
             ''// Increment elements found based on the label stored at the edge''
             elementsFound += nextEdge.label.length;
         }
         '''else'''
         {
             ''// Terminate loop''
             traverseNode := ''null'';
         }
     }
     
     ''// A match is found if we arrive at a leaf node and have used up exactly x.length elements''
     '''return''' (traverseNode != ''null'' && traverseNode.isLeaf() && elementsFound == x.length);
 }

=== 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>

=== Deletion ===

To delete a string x from a tree, we first locate the leaf representing x. Then, assuming x exists, we remove the corresponding leaf node. If the parent of our leaf node has only one other child, then that child's incoming label is appended to the parent's incoming label and the child is removed.

=== Additional operations ===
* Find all strings with common prefix: Returns an array of strings that begin with the same prefix.
* Find predecessor: Locates the largest string less than a given string, by lexicographic order.
* Find successor: Locates the smallest string greater than a given string, by lexicographic order.