trie Algorithm
The trie algorithm, also known as the prefix tree or digital tree, is an efficient data structure used to store a dynamic set or associative array where the keys are strings. It is particularly useful for tasks involving searching and matching strings, such as word completion, dictionary searches, and IP routing. The trie structure is a tree-like structure where each node represents a single character in a string and each path from the root node to a leaf node represents a unique key in the trie. The key advantage of using a trie over other data structures, such as hash tables or binary search trees, is its ability to perform search operations quickly, as the time complexity is directly related to the length of the key.
In a trie, every node stores a character and may have multiple children, each representing the next character in a string. For instance, if the trie contains the words "bat", "batman", and "batwoman", the root node would have a child representing the character 'b', which in turn would have a child for 'a', followed by a child for 't'. From this point, the trie would branch to accommodate the unique characters in "batman" and "batwoman". To search for a word in a trie, we start at the root and traverse the tree following the path of characters in the target word. If the path exists and terminates at a leaf node or a node marked as a valid end-of-word, the search is successful. The trie algorithm is highly space-efficient as it shares storage for common prefixes of the keys, making it especially suited for large dictionaries and memory-constrained applications.
// Package trie provides Trie data structures in golang.
//
// Wikipedia: https://en.wikipedia.org/wiki/Trie
package trie
// Node represents each node in Trie.
type Node struct {
children map[rune]*Node // map children nodes
isLeaf bool // current node value
}
// NewNode creates a new Trie node with initialized
// children map.
func NewNode() *Node {
n := &Node{}
n.children = make(map[rune]*Node)
n.isLeaf = false
return n
}
// Insert inserts words at a Trie node.
func (n *Node) Insert(s string) {
curr := n
for _, c := range s {
next, ok := curr.children[c]
if !ok {
next = NewNode()
curr.children[c] = next
}
curr = next
}
curr.isLeaf = true
}
// Find finds words at a Trie node.
func (n *Node) Find(s string) bool {
curr := n
for _, c := range s {
next, ok := curr.children[c]
if !ok {
return false
}
curr = next
}
return true
}
