Unlike regular trees (where whole keys are compared *en masse* from their beginning up to the point of inequality), the key at each node is compared chunk-of-bits by chunk-of-bits, where the quantity of bits in that chunk at that node is the radix r of the radix trie. When the r is 2, the radix trie is binary (i.e., compare that node's 1-bit portion of the key), which minimizes sparseness at the expense of maximizing trie depth—i.e., maximizing up to conflation of nondiverging bit-strings in the key. When r is an integer power of 2 greater or equal to 4, then the radix trie is an r-ary trie, which lessens the depth of the radix trie at the expense of potential sparseness.

As an optimization, edge labels can be stored in constant size by using two pointers to a string (for the first and last elements).^{}

Note that although the examples in this article show strings as sequences of characters, the type of the string elements can be chosen arbitrarily; for example, as a bit or byte of the string representation when using multibyte character encodings or Unicode.

Radix trees are useful for constructing associative arrays with keys that can be expressed as strings. They find particular application in the area of IP routing,^{} where the ability to contain large ranges of values with a few exceptions is particularly suited to the hierarchical organization of IP addresses.^{} They are also used for inverted indexes of text documents in information retrieval.

Radix trees support insertion, deletion, and searching operations. Insertion adds a new string to the trie while trying to minimize the amount of data stored. Deletion removes a string from the trie. Searching operations include (but are not necessarily limited to) exact lookup, find predecessor, find successor, and find all strings with a prefix. All of these operations are O(*k*) where k is the maximum length of all strings in the set, where length is measured in the quantity of bits equal to the radix of the radix trie.

This page was last edited on 15 May 2018, at 01:40.

Reference: https://en.wikipedia.org/wiki/Patricia_tree under CC BY-SA license.

Reference: https://en.wikipedia.org/wiki/Patricia_tree under CC BY-SA license.

- Computer Science
- Prefix Tree
- Data Structure
- Trie
- Radix
- Multibyte Character
- Unicode
- Associative Arrays
- IP
- Routing
- IP Addresses
- Inverted Indexes
- Information Retrieval

- Patricia Tree
- Tolima Department
- Ancaster, Ontario
- Toleration
- Washington State Book Award
- Fortingall
- Toledo, Spain
- Alburni
- Charles W. Johnson (naturalist)
- Tokyo Shimbun
- UN Commissioner For Namibia
- Tokugawa Ieyasu
- Autostrada A2 (Italy)
- Louis XIII
- 1927 Ohio State Highway Renumbering
- Auletta
- Toke Atoll
- Jodhpur State Railway
- Pashtuns
- Sant%27Angelo A Fasanella
- Tokaji
- Together For Yes
- Gram-negative
- Toffee
- Lord-Lieutenant Of County Kildare
- Tofa%C5%9F S.K.
- Toei Animation
- Ultrahydrophobicity
- Fact (United Kingdom Magazine)
- Levy Gerzberg