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

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 30 September 2009.
HTML page formatted Wed Sep 30 13:22:29 2009.

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. 30 September 2009. (accessed TODAY) Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/patriciatree.html