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 15 November 2021.
HTML page formatted Wed Oct 30 12:15:31 2024.

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