Trie structure in Golang

Data structures are very efficient ways to managing and organizing information. A good example is the Trie, also known as a prefix tree. In this post, we will explore what a Trie is, how it works, and how to implement it in Golang.

What is a Trie?

A Trie is a tree where each node represents a character of a string. Unlike other data structures that store strings individually, a Trie organizes words in such a way that common characters are shared. This is particularly useful in various applications, such as:

• Auto-complete: Suggestions of words as you type.
• Spell checkers: Identifying similar words.
• Prefix search: Finding all words that start with a given prefix.

Structure of the Trie

To start implementing a Trie, we first need to define the structure of its nodes. Each node will have:

1. children: A map that stores child nodes, where each key is a character (of type rune in Golang).
2. isEnd: A boolean that indicates whether the node represents the end of a word.

Let's define these structures:

package main

import "fmt"

// Node structure and a flag for the end of the word.
type Node struct {
    children map[rune]*Node // Child nodes
    isEnd    bool           // Indicates if it's the end of a word
}

// NewNode creates and initializes a new node
func NewNode() *Node {
    return &Node{children: make(map[rune]*Node)}
}

// Trie represents the Trie structure
// containing a pointer to the root node
type Trie struct {
    root *Node 
}

// InitTrie initializes the trie structure and return its pointer.
func InitTrie() *Trie {
    return &Trie{root: NewNode()}
}

Operations

The Trie performs two main operations: inserting words and searching for words.
Inserting Words

Steps to insert a word into the Trie:

1. Start at the root of the Trie.
2. For each character in the word, check if a corresponding node already exists.
3. If it doesn't exist, create a new node and add it as a child of the current node.
4. At the end of the word, mark the node as the end of a word.

Here’s the implementation of the insertion function:

// Insert adds a word to the Trie
func (t *Trie) Insert(word string) {
    node := t.root // Start at the root
    for _, char := range word {
        if _, exists := node.children[char]; !exists {
            node.children[char] = NewNode() // Create a new node
        }
        node = node.children[char] // Move to the child node
    }
    node.isEnd = true // Mark the end of the word
}

Searching for Words

To search for a word in the Trie, we follow a similar process:

1. Start at the root.
2. For each character, check if a corresponding node exists.
3. If we find all the characters of the word, check if the last node is an end of a word.

Here’s how this function is implemented:

// Search checks if a word exists in the Trie
func (t *Trie) Search(word string) bool {
    node := t.root // Start at the root
    for _, char := range word { 
        if _, exists := node.children[char]; !exists { 
            return false // Word not found
        }
        node = node.children[char] // Move to the child node
    }
    return node.isEnd // Return true if it's an end of a word
}

Usage

func main() {
    trie := NewTrie() // Create a new Trie
    trie.Insert("golang") // Insert words
    trie.Insert("go")
    trie.Insert("gopher")

    // Search for words
    fmt.Println(trie.Search("go"))      // true
    fmt.Println(trie.Search("golang"))  // true
    fmt.Println(trie.Search("gopher"))   // true
    fmt.Println(trie.Search("gophers"))  // false
}

Advantages of the Trie

• Fast Searching: The search complexity is proportional to the length of the word, not the total number of words.
• Prefix Efficiency: Makes it easy to find words that share a common prefix.
• Memory Efficiency: Shares nodes for common characters, saving space.

Conclusion

The Trie is a powerful data structure for efficiently managing and searching strings. Its straightforward implementation in Golang makes it accessible for developers, allowing them to quickly integrate it into their applications. The Trie’s unique ability to share nodes for common prefixes not only saves memory but also enhances search performance, making it ideal for applications such as autocomplete systems and spell checkers. Whether you're building a search engine or a dictionary, the Trie offers a simple yet effective solution for handling text data.