Editing Radix tree (section)

=== 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);
 }