# Multiset-Trie Data Structure
## 2 Multiset-Trie Data Structure  
Let \(\Sigma\) be a set of distinct symbols that define an alphabet, and let \(\sigma\) be the cardinality of \(\Sigma\). The _multiset-trie_ data structure stores multisets that are composed of symbols from the alphabet \(\Sigma\). It provides the basic tree data structure operations, such as insert, delete, and search, together with multiset containment operations for searching sub-multisets and super-multisets, which will be discussed in the next section in greater detail. A multiset ignores the ordering of its elements by definition, which allows us to define a bijective mapping \(\phi:\Sigma\to I\), where \(I\) is the set of integers \(\{1,2,3,\ldots,\sigma\}\). In this way, we obtain the indexing of elements from the alphabet \(\Sigma\), so we can work directly with integers rather than with specific symbols from \(\Sigma\). The multiset-trie is an \(n\)-ary tree-based data structure with the properties of the trie. A node in multiset-trie always has degree \(n\), i.e., \(n\) children. Some of the children may be _Null_ (non-existing), but the number of _Null_ children can be at most \(n-1\). All the children of a node, including the _Null_ children, are labeled from left to right with labels \(c_{j}\), where \(j\in\{0,1,\ldots,n-1\}\). Every pair of child nodes \(u\) and \(v\) that share the same parent node have different labels. Nodes that have equal height in a multiset-trie form a level. The height of a multiset-trie is always \(\sigma+1\) if at least one multiset is in the structure. The height of the root node (the first level) is defined to be \(1\). Levels in multiset-trie are enumerated by their height, i.e., a level \(L_{i}\) has height \(i\). The connection between level height in a multiset-trie and symbols from alphabet \(\Sigma\) is defined as follows. A level \(L_{i}\), where \(i\in\{1,2,\ldots,\sigma\}\) represents a symbol \(s\in\Sigma\), such that \(\phi^{-1}(i)=s\). The last level \(L_{\sigma+1}\) does not represent any symbol and is named the _leaf level_ (\(LL\) for short). Since every level, except \(LL\), represents a symbol from \(\Sigma\), we can define a transition between nodes that are located at different levels in a multiset-trie. Consider two nodes \(u,v\) in a multiset-trie at levels \(L_{i}\), \(L_{i+1}\), respectively, where \(i\in\{1,2,\ldots,\sigma\}\). Let a node \(u\) be a parent node of a node \(v\) and consequently a node \(v\) be a child node of a node \(u\). Suppose that a child node \(v\) is not _Null_ and has a label \(c_{j}\), where \(j\in\{0,1,\ldots,n-1\}\). Then, the _path_\(u\to v\) represents a symbol \(s\in\Sigma\) with multiplicity \(j\), such that \(\phi^{-1}(i)=s\). Such a transition \(u\to v\) is called a _path of length \(1\)_ and is allowed if and only if a node \(v\) is not _Null_ and \(u\) is a parent node of a node \(v\). If a node \(v\) has label \(c_{0}\), then the path \(u\to v\) represents a symbol with the multiplicity \(0\) respectively, i.e., an empty symbol. We define a _complete path_ to be the path of length \(\sigma\) in a multiset-trie with the endpoints at the root node (the first level) and \(LL\). Thus, a multiset \(m\) is inserted into a multiset-trie if and only if there exists a complete path in a multiset-trie that corresponds to \(m\). Note that every complete path in a multiset-trie is unique. Therefore, the multisets that share a common prefix in a multiset-trie can have a common path of length at most \(\sigma-1\). The complete path that passes through nodes labeled by \(c_{0}\) on all levels represents an empty multiset or an empty set. Thus, any multiset \(m\) that is composed of symbols from \(\Sigma\) with maximum multiplicity not greater than \(n-1\) can be represented by a complete path in a multiset-trie.