trie

Documentation

Overview

Package trie provides Trie data structures in golang.

Wikipedia: https://en.wikipedia.org/wiki/Trie

Index

• type Node
  • func NewNode() *Node
  • func (n *Node) Capacity() int
  • func (n *Node) Compact() (remove bool)
  • func (n *Node) Find(s string) bool
  • func (n *Node) Insert(s ...string)
  • func (n *Node) Remove(s ...string)
  • func (n *Node) Size() int

Examples

• Node

Types

type Node

type Node struct {
	// contains filtered or unexported fields
}

Node represents each node in Trie.

Example

// creates a new node
node := NewNode()

// adds words
node.Insert("nikola")
node.Insert("tesla")

// check size and capacity
fmt.Println(node.Size())     // 2 words
fmt.Println(node.Capacity()) // 12 nodes

// finds words
fmt.Println(node.Find("thomas")) // false
fmt.Println(node.Find("edison")) // false
fmt.Println(node.Find("nikola")) // true

// remove a word, and check it is gone
node.Remove("tesla")
fmt.Println(node.Find("tesla")) // false

// size and capacity have changed
fmt.Println(node.Size())     // 1 word left
fmt.Println(node.Capacity()) // 12 nodes remaining

Output:

2
12
false
false
true
false
1
12

func NewNode

func NewNode() *Node

NewNode creates a new Trie node with initialized children map.

func (*Node) Capacity

func (n *Node) Capacity() int

Capacity returns the number of nodes in the Trie

func (*Node) Compact

func (n *Node) Compact() (remove bool)

Compact will remove unecessay nodes, reducing the capacity, returning true if node n itself should be removed.

func (*Node) Find

func (n *Node) Find(s string) bool

Find words at a Trie node.

func (*Node) Insert

func (n *Node) Insert(s ...string)

Insert zero, one or more words at a Trie node.

func (*Node) Remove

func (n *Node) Remove(s ...string)

Remove zero, one or more words lazily from the Trie, no node is actually removed.

func (*Node) Size

func (n *Node) Size() int

Size returns the number of words in the Trie