Tries in Go

A trie (pronounced "try") is a tree-like data structure used to store a dynamic set of strings, where each node represents a common prefix shared with other strings. Tries are particularly useful for efficient string search operations, such as prefix queries and auto-complete functionality.

Trie Structure

In a trie:

• Each node represents a character of a string.
• The root node represents an empty string.
• Edges connect nodes to form words or prefixes.
• Each path down the tree represents a unique prefix of the stored strings.

Tries allow for efficient insertion, deletion, and search operations, typically in O(m) time complexity, where m is the length of the key.

Implementation in Go

Here's a basic implementation of a trie in Go, including methods for inserting strings, searching for strings, and prefix queries.

go
package main

import "fmt"

// TrieNode represents each node in the Trie.
type TrieNode struct {
    children map[rune]*TrieNode
    isEndOfWord bool
}

// Trie represents the trie data structure.
type Trie struct {
    root *TrieNode
}

// NewTrieNode creates a new TrieNode.
func NewTrieNode() *TrieNode {
    return &TrieNode{
        children: make(map[rune]*TrieNode),
    }
}

// NewTrie creates a new Trie.
func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

// Insert inserts a word into the Trie.
func (t *Trie) Insert(word string) {
    currentNode := t.root
    for _, char := range word {
        if _, exists := currentNode.children[char]; !exists {
            currentNode.children[char] = NewTrieNode()
        }
        currentNode = currentNode.children[char]
    }
    currentNode.isEndOfWord = true
}

// Search searches for a word in the Trie.
func (t *Trie) Search(word string) bool {
    currentNode := t.root
    for _, char := range word {
        if _, exists := currentNode.children[char]; !exists {
            return false
        }
        currentNode = currentNode.children[char]
    }
    return currentNode.isEndOfWord
}

// StartsWith checks if there is any word in the Trie that starts with the given prefix.
func (t *Trie) StartsWith(prefix string) bool {
    currentNode := t.root
    for _, char := range prefix {
        if _, exists := currentNode.children[char]; !exists {
            return false
        }
        currentNode = currentNode.children[char]
    }
    return true
}

// Autocomplete returns all words in the Trie that start with the given prefix.
func (t *Trie) Autocomplete(prefix string) []string {
    var results []string
    currentNode := t.root
    for _, char := range prefix {
        if _, exists := currentNode.children[char]; !exists {
            return results
        }
        currentNode = currentNode.children[char]
    }
    t.collectWords(currentNode, prefix, &results)
    return results
}

// collectWords recursively collects all words from the given node.
func (t *Trie) collectWords(node *TrieNode, prefix string, results *[]string) {
    if node.isEndOfWord {
        *results = append(*results, prefix)
    }
    for char, childNode := range node.children {
        t.collectWords(childNode, prefix+string(char), results)
    }
}

func main() {
    trie := NewTrie()
    trie.Insert("hello")
    trie.Insert("hell")
    trie.Insert("heaven")
    trie.Insert("heavy")

    fmt.Println(trie.Search("hell"))    // true
    fmt.Println(trie.Search("helloa"))  // false
    fmt.Println(trie.Search("he"))      // false
    fmt.Println(trie.StartsWith("he"))  // true
    fmt.Println(trie.StartsWith("hello")) // true
    fmt.Println(trie.StartsWith("helloa")) // false

    fmt.Println(trie.Autocomplete("he"))  // ["hello", "hell", "heaven", "heavy"]
    fmt.Println(trie.Autocomplete("hell")) // ["hello", "hell"]
}

Explanation of Key Methods

1. Insert: Adds a word to the trie. It traverses each character of the word, creating new nodes if necessary, and marks the last node as the end of a word.

2. Search: Checks if a word is present in the trie. It traverses each character of the word and returns true if it reaches a node marked as the end of a word.

3. StartsWith: Checks if any word in the trie starts with the given prefix. It traverses the trie using the characters of the prefix.

4. Autocomplete: Returns all words in the trie that start with a given prefix. It first reaches the end of the prefix in the trie, then collects all words starting from that node using a recursive helper method collectWords.

5. collectWords: A recursive helper method used by Autocomplete to collect all words from a given node.

Use Cases

• Prefix Search: Efficiently find all words starting with a given prefix.
• Auto-complete: Suggest completions for a given prefix based on stored words.
• Spell Checking: Verify if a word exists in a dictionary or suggest corrections based on prefixes.

Conclusion

Tries are efficient data structures for string search operations, providing fast insert, search, and prefix query capabilities. They are especially useful for applications like auto-complete, spell checking, and implementing dictionary operations. By leveraging the trie structure in Go, you can efficiently manage and query large sets of strings.