Patricia tree

(data structure)

Definition: A compact representation of a trie in which any node that is an only child is merged with its parent.

Also known as radix tree.

Generalization (I am a kind of ...)
trie.

Specialization (... is a kind of me.)
suffix tree.

See also compact DAWG.

Note: A compact directed acyclic word graph (DAWG) merges common suffix trees to save additional space.

A radix tree is taken to be a binary Patricia tree.

Author: SE

Implementation

Net-Patricia (Perl and C) is a C implementation with a Perl API. C prototyping tools, cprops (C), is a threaded implementation (find trie.c). py-radix (Python). insert (C), search (C). Herbert Glarner's implementation in (Linoleum).

More information

A McGill class note has explanations of and comparisons between tries and suffix trees. Dictionary Automaton in Optimal Space.

Donald R. Morrison, PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric, Journal of the ACM, 15(4):514-534, October 1968.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 18 December 2007.
HTML page formatted Tue Dec 18 16:22:27 2007.

Cite this as:
Stefan Edelkamp, "Patricia tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 18 December 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/patriciatree.html