From "Implementing a dynamic compressed trie" by Stefan Nilsson
In this section we give a brief overview of binary tries and compression techniques. We start with the de nition of a binary trie. We say that a string w is the i-suffix of the string u, if there is a string v of length i such that u = vw.
De nition 2.1. A binary trie containing n elements is a tree with the fol lowing properties:
If n = 0, the trie is empty.
If n = 1, the trie consists of a node that contains the element.
If n > 1, the trie consists of a node with two children. The left child is a binary trie containing the 1-suffixes of all elements starting with 0 and the right child is a binary trie containing the 1-suffixes of all elements starting with 1.
Figure 1a depicts a binary trie storing 15 elements. In the gure, the nodes storing the actual binary strings are numbered starting from 0. For example, node 14 stores a binary string whose pre x is 11101001.
We assume that all strings in a trie are pre x-free: no string can be a pre x of another. In particular, this implies that duplicate strings are not allowed. If all strings stored in the trie are unique, it is easy to insure that the strings are pre x-free by appending a special marker at the end of each string. For example, we can append the string 1000::: to the end of each string. A nite string that has been extended in this way is often referred to as a semi-in nite string or sistring. A path compressed binary trie is a trie where all subtries with an empty child have been removed. Implementing a dynamic compressed trie De nition 2.2. A path compressed binary trie, or Patricia trie, containing n elements is a tree
with the fol lowing properties:
If n = 0, the trie is empty.
If n = 1, the trie consists of a node that contains the element.
If n > 1, the trie consists of a node containing two children and a binary string s of length |s|. This string equals the longest prefi x common to all elements stored in the trie. The left child is a path compressed binary trie containing the (|s| + 1)-suffixes of all elements starting with s0 and the right child is a path compressed binary trie containing the (|s| + 1)-suffixes of all elements starting with s1.
Figure 1b depicts the path compressed binary trie corresponding to the binary trie of Figure 1a. A natural extension of the path compressed trie is to use more than one bit for branching. We refer to this structure as a level and path compressed trie. De nition 2.3. A level and path compressed trie, or an LPC-trie, containing n elements is a tree
with the fol lowing properties:
If n = 0, the trie is empty.
If n = 1, the trie consists of a node that contains the element.
If n > 1, the trie consists of a node containing 2i children for some i >= 1, and a binary string s of length |s|. This string equals the longest pre x common to all elements stored in the trie. For each binary string x of length |x| = i, there is a child containing the (|s| + |x|)-suffixes of all elements starting with sx. A perfect LPC-trie is an LPC-trie where no empty nodes are allowed.
De nition 2.4. A perfect LPC-trie is an LPC-trie with the following properties:
The root of the trie holds 2i subtries, where i >= 1 is the maximum number for which all of the subtries are non-empty.
Each subtrie is an LPC-trie.
Figure 1c provides an example of a perfect LPC-trie corresponding to the path compressed trie in Figure 1b. Its root is of degree 8 and it has four subtries storing more than one element: a child of degree 4 and three children of degree 2
