Описание тега patricia-trie

Описание тега Вопросы с тегом

Patricia trees are a term for a specialised kind of Radix tree. A radix tree is a space-optimized trie data structure where each node with only one child is merged with its child. This means every internal node has at least two children. Unlike in regular tries, edges can be labeled with sequences of characters as well as single characters. This makes them much more efficient for small sets and for sets of strings that share long prefixes.

According to the Wikipedia article on Radix trees

Donald R. Morrison first described what he called "Patricia trees" in 1968; the name comes from the acronym PATRICIA, which stands for "Practical Algorithm To Retrieve Information Coded In Alphanumeric". Gernot Gwehenberger independently invented and described the data structure at about the same time.

The formal specification for PATRICIA, located in the Journal of ACM Volume 15 Issue 4, Oct. 1968 Pages 514-534 specifies a group of algorithms that produce a tree with very specific requirements. Some examples of those requirements, taken from this document are as follows:

... it was decided that the alphabet should be restricted to a binary one. A theorem which strongly influenced this decision is one which, in another form, is due to Euler. The theorem states that if the alphabet is binary, then the number of branches is exactly one less than the number of ends. Corollaries state that as the library grows, each new end brings into the library with it exactly one new branch, and each branch has exactly two exits. These facts are very useful in the allocation of storage for the index. They imply that the total storage required is completely determined by the number of ends, and all of the storage required will actually be used.

In summary:

A PATRICIA data structure has the same structure as a binary tree.
There are no 'internal nodes'; "the total storage required is completely determined by the number of ends".