Patricia Trie

Patricia Trie is a data structure used to store strings where all the internal nodes have atleast two children. Instead of an edge having a single letter, the storage efficiency is maximized by grouping characters that have one child. Patricia trie is a variant of the radix trie, in which the nodes only store the position of the first bit that distinguishes two sub-trees, rather than explicitly storing every bit of every key. It is also known as binary radix trie.

Add operation:
Understanding addition with the help of the example shown in Figure 1. Here, once we add a word APPLES, the null terminator is put to the edge to indicate that APPLES is a word.
Next we add APPLICANT, as APPL is common between both words, so we branch off with null terminator ICANT from null terminator ES.
Further APPROX is added, it has APP in common, so we split and have RO with null terminator X, this adds the word APPROX to the trie. Further, we add APPROVE, as APPRO is common between both APPROX and APPROVE, so we branch off with null terminator VE. Same steps are followed for APPROACH, APPROPRIATE, AIDE and AIRY. If we have to add a word that is already existing in the trie, we will just add an edge with null terminator label to indicate that it is a word.
The time complexity for add operation is O(mN), where m is the size of word and n is the size of the alphabet.

Figure 1: A representation of add operation in patricia trie

Remove operation:
Considering the same example, we remove the word APPLICANT. We search A -> PP -> L -> ICANT. We begin by removing ICANT null terminator. Due to this, we end up with one child, so we stop there. It is important to note that all internal nodes of a patricia trie must have atleast two child. In order to achieve this, we must concatenate the edge label ES with the edge labeled L. The resulting edge would be null terminator LES to indicate APPLES is still a word. How a patricia trie looks before and after removal of a word can be seen in Figure 2.
The time complexity for removal is also O(mN), where m is the size of word and n is the size of the alphabet.

Note: We cannot have a null terminator in the internal edge.

Figure 2: The patricia trie before and after removal of a string

Search operation:
Considering the same trie as addition operation, search the string APPLES. Traverse from A -> PP -> L-> ES in Figure 3. If found, the word is returned true, otherwise false.
Time complexity of search operation: O(m), here, m is the size of word.

Figure 3: Search in patricia trie

Reference: Morin, Patrick. “Trie” ( url = https://www.youtube.com/watch?v=wcbrSyFjfEo&t=10s )