package module
v0.0.0-...-868a049 Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Aug 31, 2017 License: MIT Imports: 3 Imported by: 0



Trie implementation in Go. Inspired by John Resig's trie-js.


The trie data structure is particularly interresting to me as it's surprisingly simple yet powerful.

The data structure is nothing more than the recursive type type Node map[rune]Node. With this simple type we're able to index words by prefix and perform fast lookups.


import ""

t := trie.New()
t.Index([]string{"ab", "ac", "ad", "abc"})
t.Search("ab") // ["ab" "abc"]

The API documentation is available at





This section is empty.


This section is empty.


This section is empty.


type Iter

type Iter func(r rune, n Node)

Iter is a function type used as an argument to ForEach. It's arguments are the same as what would be returned on each for loop cycle, namely a rune and a map of nodes.

type Node

type Node map[rune]Node

The Node type makes up the Trie data structure.

trie := New()
trie.Index([]string{"ab", "ac", "ad", "abc"})
fmt.Printf("%q", trie.Search("ab"))

["ab" "abc"]

func New

func New() Node

New allocates a new node.

func (Node) All

func (node Node) All(p string) (res []string)

All returns all the strings indexed by the current node and it's children in an array each item prefixed by p.

func (Node) ForEach

func (node Node) ForEach(f Iter)

ForEach wraps the for loop and additionally checks for the end rune and ignores it.

func (Node) Index

func (node Node) Index(d []string)

Index builds a Trie with the supplied dictionary d.

func (Node) Insert

func (node Node) Insert(s string)

Insert adds a new word to the Trie. It iterates over s and creates or appends a new Node for each rune.

func (Node) IsEnd

func (node Node) IsEnd() bool

IsEnd returns true if the current node is an end node.

func (Node) Search

func (node Node) Search(s string) (res []string)

Search looks for the string s inside the Trie structure. If s is matched and the node has mode children, its children are also returned as they all match the given prefix s.

func (Node) String

func (node Node) String() string

String satisfies the Stringer interface for easily printing a Trie.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL