In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent. The number of children of every internal node is at most the radix r of the radix tree, where r = 2x for some integer x ≥ 1. Unlike regular trees, edges can be labeled with sequences of elements as well as single elements. This makes radix trees much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes. Unlike regular trees (where whole keys are compared en masse from their beginning up to the point of inequality), the key at each node is compared chunk-of-bits by chunk-of-bits, where the quantity of bits in that chunk at that node is the radix r of the radix trie. When r is 2, the radix trie is binary (i.e., compare that node's 1-bit portion of the key), which minimizes sparseness at the expense of maximizing trie depth—i.e., maximizing up to conflation of nondiverging bit-strings in the key. When r ≥ 4 is a power of 2, then the radix trie is an r-ary trie, which lessens the depth of the radix trie at the expense of potential sparseness. As an optimization, edge labels can be stored in constant size by using two pointers to a string (for the first and last elements). Note that although the examples in this article show strings as sequences of characters, the type of the string elements can be chosen arbitrarily; for example, as a bit or byte of the string representation when using multibyte character encodings or Unicode.
Applications Radix trees are useful for constructing associative arrays with keys that can be expressed as strings. They find particular application in the area of IP routing, where the ability to contain large ranges of values with a few exceptions is particularly suited to the hierarchical organization of IP addresses. They are also used for inverted indexes of text documents in information retrieval.
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 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()
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. 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.)
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.
History The data structure was invented in 1968 by Donald R. Morrison, with whom it is primarily associated, and by Gernot Gwehenberger. Donald Knuth, pages 498–500 in Volume III of The Art of Computer Programming, calls these "Patricia's trees", presumably after the acronym in the title of Morrison's paper: "PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric". Today, Patricia trees are seen as radix trees with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch.
… excerpt ends here. Continue reading the full article.
