Radix tree

In computer science, a Patricia trie (derived from the Engl. Retrieval) a data structure more precisely, a special type of a trie for the simultaneous storage of multiple strings. Its name comes from the acronym PATRICIA, which stands for Practical Algorithm to Retrieve Information Coded in Alphanumeric. It was published by Donald R. Morrison 1968.

The Patricia trie stands in contrast to the ordinary trie by the fact that the data is stored compressed. These are characters that no branch in the tree is created, simply skipped and the number of omitted nodes stored before the next occurring characters. This ensures that a search term can be clearly assigned.

The size of the Patricia trie is therefore not dependent on the length of the stored key values ​​and new records can be added only by creating a new node and the new edge. Thus, they grow slowly, even when a large number of new elements will be inserted.

Patricia trie can be used to construct an associative array of strings as keys. This saves memory for the keys.