The Practical Algorithm to Retrieve Information Coded in Alphanumeric (PATRICIA) trie, also known as a Radix tree, is a digital tree data structure for storing a dataset - such as strings over an alphabet. In a Patricia trie, a node that is the only node of a parent node is merged with its parent, making it a very compact data structure that uses a small amount of memory. The keys of the nodes represent the path to reach a node. The nodes that have the same prefixes share the same paths.
Tries allow nodes to be inserted and deleted, making them the perfect data structure for building dictionaries, e.g., English words or telephone yellow pages. They are also used in spell-checking programs because of their effective prefix-based search operations.
References
- Bashir, I. (2023) Mastering Blockchain: Inner workings of blockchain, from cryptography and decentralized identities, to DeFi, NFTs and Web3. Packt Publishing Ltd. https://books.google.com?id=PiC2EAAAQBAJ.