Multiway Trie

Abstract

A Trie (derived from “retrieval”) is a tree structure designed to store a set of strings. Unlike standard Binary Search Trees, the keys are not stored within the nodes themselves; instead, a key is defined by the concatenation of labels along the path from the root to a specific node.

• Category: Character-Path Digital Search Tree
• Input Constraints: Expands across an explicit alphabet size $|\Sigma |$ to map contiguous character paths.
• Key Advantage: Run times scale purely with string character length $k$, decoupling latency from total dictionary size $n$.

---

Structural Properties

The Multiway Trie expands the concept of a Binary Trie to support any arbitrary alphabet $\Sigma$ (such as English letters, DNA base pairs, or numerical digits).

• Edge Labels: Characters are assigned exclusively to the edges, not the nodes themselves.
• Word Nodes: Since a path can represent an internal prefix that isn’t a full standalone word (for example, the path ca is a valid prefix for the complete word car), specific nodes are marked with a boolean flag to indicate the end of a valid word. In layout diagrams, these are highlighted as distinct blue nodes.
• The Root: An empty Trie consists of a single root node with no outgoing edges. The root node represents an empty string.

---

Core Operations

Multiway Tries provide highly efficient operations based on the length of the string ($k$) rather than the number of stored items ($n$).

Find(word)

Starts at the root node and sequentially follows the edge labeled with each consecutive letter of the target word string.

• Success Condition: The search successfully evaluates all characters of the string and lands on an active node marked as a valid word node.
• Failure Condition: The tracking pointer hits a NULL edge (indicating the sequence path does not exist) or the final node reached lacks the explicit word node flag.

Algorithm 41 Multiway Trie Find Operation

procedure Find(word, root)

$curr \gets root$

for each character $c$ in word do

if curr does not have an outgoing edge labeled by $c$ then

return $\text{false}$

else

$curr \gets \text{child of curr along edge labeled by } c$

return curr.isWordNode

Insert(word)

Traces the character edge path from the root, creating a new child node and a labeled edge whenever a character transition is missing, and marks the final terminal node as a valid word node.

Algorithm 42 Multiway Trie Insertion

procedure Insert(word, root)

$curr \gets root$

for each character $c$ in word do

if curr does not have an outgoing edge labeled by $c$ then

CreateChildNode(curr, c)

$curr \gets \text{child of curr along edge labeled by } c$

if curr.isWordNode $\neq$ true then

curr.isWordNode $\gets$ true

The Edges-Not-Nodes Invariant

In a Multiway Trie, characters label the edges, not the nodes themselves. This is a crucial distinction: inserting a single-letter word like "a" into an empty root requires creating a second child node so the character "a" can label the connecting link edge between them.

Remove(word)

Locates the targeted word sequence using the standard find algorithm and unmarks its word-node flag.

• Structural Preservation: The physical node containers and character edges typically remain intact after removal to support other independent words that share those prefix branches.

Algorithm 43 Multiway Trie Removal

procedure Remove(word, root)

$curr \gets root$

for each character $c$ in word do

if curr does not have an outgoing edge labeled by $c$ then

return

else

$curr \gets \text{child of curr along edge labeled by } c$

if curr.isWordNode == true then

curr.isWordNode $\gets$ false

---

Physical Implementation: The Array Strategy

To ensure that each character transition is as fast as possible, Multiway Tries prioritize lookup speed over memory efficiency.

• The Node Array: Every individual node contains an array of raw pointer references equal to the total size of the alphabet ($|\Sigma |$). For the English alphabet, each node encapsulates 26 slots.
• Constant Time Access: Because each character maps directly to an array index via constant offset arithmetic (such as `‘a’ \to 0, \text{ ‘b’} \to 1$), the time to follow an edge is constant.
• Complexity Bounds: This structure results in a deterministic worst-case time complexity of $O(k)$ for search, insert, and remove operations.

---

Alphabetical Iteration and Auto-Complete

Because a Multiway Trie is naturally organized by character, it is inherently sorted. This allows us to perform operations that are impossible in an unordered structure like a Hash Table.

Alphabetical Iteration

By performing a recursive traversal, we can output all words in the lexicon in perfect alphabetical order:

• Ascending Order (A-Z): Use a Pre-Order Traversal. The engine checks if the current node is flagged as a word-node first, then visits the child branches in alphabetical order (from slot $0$ through $|\Sigma |-1$).
• Descending Order (Z-A): Use a Post-Order Traversal. The engine visits child branches in reverse alphabetical order (from slot $|\Sigma |-1$ down to $0$) before evaluating the current node.

Algorithm 44 Trie Sorted Iterations Preorder

procedure AscendingPreOrder(node)

if node.isWordNode then

Output(node.word)

for each child of node in ascending alphabetical order do

AscendingPreOrder(child)

Algorithm 45 Trie Sorted Iterations Preorder

procedure DescendingPostOrder(node)

for each child of node in descending alphabetical order do

DescendingPostOrder(child)

if node.isWordNode then

Output(node.word)

Auto-Complete (Prefix Search)

The Trie is often called a Prefix Tree because every node represents a distinct prefix shared by all its structural descendants. This makes prefix search highly efficient:

1. Traverse to Prefix: Start at the root and follow character edges to match the given prefix string (such as "cat").
2. Subtree Search: Once the pointer reaches the node representing that prefix, perform an AscendingPreOrder traversal on that isolated subtree.
3. Result: This routine outputs every word in the Trie that begins with those characters.

---

Architectural Trade-Offs Summary

Advantages

• Deterministic Speed: Operational performance depends entirely on the character count of the word ($k$), completely independent of the total word count ($n$).
• Alphabetical Ordering: A Pre-order traversal walks the structure in sorted sequence natively.
• Prefix Matching Efficiency: Uniquely optimized for auto-complete routines because all words sharing a common prefix cluster under the same subtree.

Disadvantages

• Space Inefficiency: This is the primary drawback of a Multiway Trie. Because every node allocates space for an entire alphabet’s worth of pointers, a sparse trie (where many characters don’t follow others) wastes a significant amount of memory on NULL pointers.

---

Related Notes

• Multiway Trie Implementation
• Aho-Corasick Automaton
• Binary Search Tree
• Ternary Search Tree