In computer science, a radix tree (also patricia trie or radix trie or compact prefix tree) is a space-optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike in regular tries, edges can be labeled with sequences of elements as well as single elements. This makes them much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes.
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).
Read more about Radix Tree: Applications, Operations, History, Comparison To Other Data Structures, Variants
Famous quotes containing the word tree:
“There is hardly an American male of my generation who has not at one time or another tried to master the victory cry of the great ape as it issued from the androgynous chest of Johnny Weissmuller, to the accompaniment of thousands of arms and legs snapping during attempts to swing from tree to tree in the backyards of the Republic.”
—Gore Vidal (b. 1925)