NIST

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).

More information

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 Black.

Entry modified 12 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Stefan Edelkamp, "Patricia tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/patriciatree.html