A k-ary tree gives each node up to k child links, with links distinguished by symbols from an alphabet. In a trie, paths encode strings and shared prefixes are stored once. section 6.2
A trie-based k-ary tree represents strings through:
- Edges labeled with individual alphabet characters. section 6.2
- Paths whose joined labels identify prefixes or complete strings. section 6.2
- Key-node markers indicating that a path represents a stored string; other nodes represent intermediate prefixes. section 6.2
- Child storage implemented as alphabet-indexed links, with a hash map offering a more compact representation than a full array of links. section 6.2
Encoding words
A trie can contain “a”, “an”, “at”, and “I”. The root represents the empty string; shared paths represent shared prefixes, while filled key nodes mark stored words.
