Skip to content

Instantly share code, notes, and snippets.

@drgarcia1986
Created June 5, 2018 02:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save drgarcia1986/94b0d1ebd41b5fdddfefd6cdfa012e22 to your computer and use it in GitHub Desktop.
Save drgarcia1986/94b0d1ebd41b5fdddfefd6cdfa012e22 to your computer and use it in GitHub Desktop.
Trie Data Structure
KEY: b
-KEY: o
--KEY: b
KEY: c
-KEY: a
--KEY: r
-KEY: u
--KEY: t
---KEY: e
KEY: t
-KEY: o
package main
import "fmt"
type Node struct {
Value string
Childrens map[string]*Node
}
type Trie struct {
Root *Node
}
func (t *Trie) Insert(word string) {
node := t.Root
for _, v := range word {
c := string(v)
if cn, ok := node.Childrens[c]; ok {
node = cn
} else {
newNode := NewNode(c)
node.Childrens[c] = newNode
node = newNode
}
}
}
func NewNode(v string) *Node {
return &Node{Value: v, Childrens: make(map[string]*Node)}
}
func NewTrie() *Trie {
return &Trie{NewNode("")}
}
func printNode(n *Node, level int) {
for k, v := range n.Childrens {
for i := 0; i < level; i++ {
fmt.Printf("-")
}
fmt.Printf("KEY: %s\n", k)
printNode(v, level+1)
}
}
func main() {
t := NewTrie()
t.Insert("car")
t.Insert("cute")
t.Insert("to")
t.Insert("bob")
printNode(t.Root, 0)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment