ternary_search_tree

Documentation

Overview

https://en.wikipedia.org/wiki/Ternary_search_tree In computer science, a ternary search tree is a type of trie (sometimes called a prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Like other prefix trees, a ternary search tree can be used as an associative map structure with the ability for incremental string search. However, ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. Common applications for ternary search trees include spell-checking and auto-completion.

Index

• Constants
• type Handler
• type HandlerFunc
  • func (f HandlerFunc) Handle(prefix []byte, value any) (goon bool)
• type TernarySearchTree
  • func New(prefixes ...string) *TernarySearchTree
  • func NewWithBytes(prefixes ...[]byte) *TernarySearchTree
  • func (l *TernarySearchTree) Contains(key string) bool
  • func (l *TernarySearchTree) ContainsPrefix(prefix string) bool
  • func (l *TernarySearchTree) Count() int
  • func (l *TernarySearchTree) Depth() int
  • func (l *TernarySearchTree) Follow(prefix string) (key string, value any, ok bool)
  • func (l *TernarySearchTree) Left() *node
  • func (l *TernarySearchTree) Load(key string) (value any, ok bool)
  • func (l *TernarySearchTree) Middle() *node
  • func (l *TernarySearchTree) Remove(key string, shrinkToFit bool) (old any, ok bool)
  • func (l *TernarySearchTree) RemoveAll(prefix string) (old any, ok bool)
  • func (l *TernarySearchTree) Right() *node
  • func (l *TernarySearchTree) Store(key string, value any)
  • func (l *TernarySearchTree) String() string
  • func (l *TernarySearchTree) Traversal(order traversal.Order, handler Handler)

Examples

• New
• TernarySearchTree.Count
• TernarySearchTree.Load
• TernarySearchTree.RemoveAll
• TernarySearchTree.Store
• TernarySearchTree.Traversal

Constants

const (
	NilKey = 0
)

Types

type Handler

type Handler interface {
	Handle(prefix []byte, value any) (goon bool)
}

type HandlerFunc

type HandlerFunc func(prefix []byte, value any) (goon bool)

The HandlerFunc type is an adapter to allow the use of ordinary functions as traversal handlers. If f is a function with the appropriate signature, HandlerFunc(f) is a Handler that calls f.

func (HandlerFunc) Handle

func (f HandlerFunc) Handle(prefix []byte, value any) (goon bool)

ServeHTTP calls f(w, r).

type TernarySearchTree

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

TernarySearchTree represents a Ternary Search Tree. The zero value for List is an empty list ready to use.

func New

func New(prefixes ...string) *TernarySearchTree

New creates a tenary search tree, which is a trie tree.

Example

package main

import (
	"fmt"

	"github.com/searKing/golang/go/container/trie_tree/ternary_search_tree"
)

func main() {
	tree := ternary_search_tree.New("abcdef")
	fmt.Println("count:	", tree.Count())
	fmt.Println("depth:	", tree.Depth())
	fmt.Printf("contains key %q:	%v\n", "abcdef", tree.Contains("abcdef"))
	fmt.Printf("contains key prefix %q:	%v\n", "ab", tree.ContainsPrefix("ab"))
	val, _ := tree.Load("test")
	fmt.Printf("load key %q's value:	%v\n", "test", val)

}

Output:

count:	 1
depth:	 6
contains key "abcdef":	true
contains key prefix "ab":	true
load key "test"'s value:	<nil>

func NewWithBytes

func NewWithBytes(prefixes ...[]byte) *TernarySearchTree

NewWithBytes behaves like New, but receive ...[]byte

func (*TernarySearchTree) Contains

func (l *TernarySearchTree) Contains(key string) bool

return true if the node matched with key, with value nonempty

func (*TernarySearchTree) ContainsPrefix

func (l *TernarySearchTree) ContainsPrefix(prefix string) bool

return true if any node exists with key prefix, no matter value is empty or not

func (*TernarySearchTree) Count

func (l *TernarySearchTree) Count() int

Count returns the number of elements of list l, excluding (this) sentinel node.

Example

package main

import (
	"fmt"

	"github.com/searKing/golang/go/container/trie_tree/ternary_search_tree"
)

func main() {
	tree := ternary_search_tree.New()
	tree.Store("a", nil)
	fmt.Println(tree.Count())
	tree.Store("ab", nil)
	fmt.Println(tree.Count())
	tree.Store("x", nil)
	fmt.Println(tree.Count())
	tree.Store("y", nil)
	fmt.Println(tree.Count())

	tree.Remove("abc", true)
	fmt.Println(tree.Count())
	tree.Remove("x", true)
	fmt.Println(tree.Count())
	tree.Remove("a", true)
	fmt.Println(tree.Count())

}

Output:

1
2
3
4
4
3
2

func (*TernarySearchTree) Depth

func (l *TernarySearchTree) Depth() int

Depth return max len of all prefixs

func (*TernarySearchTree) Follow

func (l *TernarySearchTree) Follow(prefix string) (key string, value any, ok bool)

Follow returns node info of longest subPrefix of prefix

func (*TernarySearchTree) Left

func (l *TernarySearchTree) Left() *node

Front returns the first node of list l or nil if the list is empty.

func (*TernarySearchTree) Load

func (l *TernarySearchTree) Load(key string) (value any, ok bool)

Load loads value by key

Example

package main

import (
	"fmt"

	"github.com/searKing/golang/go/container/trie_tree/ternary_search_tree"
)

func main() {
	tree := ternary_search_tree.New()
	tree.Store("key", "val")

	val, ok := tree.Load("key")
	fmt.Printf("%q:	%q, %v\n", "key", val, ok)
	val, ok = tree.Load("not exist key")
	fmt.Printf("%q:	%v, %v\n", "not exist key", val, ok)
}

Output:

"key":	"val", true
"not exist key":	<nil>, false

func (*TernarySearchTree) Middle

func (l *TernarySearchTree) Middle() *node

Middle returns the first node of list l or nil if the list is empty.

func (*TernarySearchTree) Remove

func (l *TernarySearchTree) Remove(key string, shrinkToFit bool) (old any, ok bool)

remove the node matched with key

func (*TernarySearchTree) RemoveAll

func (l *TernarySearchTree) RemoveAll(prefix string) (old any, ok bool)

remove all nodes started with key prefix

Example

package main

import (
	"fmt"

	"github.com/searKing/golang/go/container/trie_tree/ternary_search_tree"
)

func main() {
	tree := ternary_search_tree.New()
	tree.Store("a", nil)
	fmt.Println(tree.Count())
	tree.Store("ab", nil)
	fmt.Println(tree.Count())
	tree.Store("x", nil)
	fmt.Println(tree.Count())
	tree.Store("y", nil)
	fmt.Println(tree.Count())

	tree.RemoveAll("x")
	fmt.Println(tree.Count())
	tree.RemoveAll("a")
	fmt.Println(tree.Count())
	tree.RemoveAll("ab")
	fmt.Println(tree.Count())

}

Output:

1
2
3
4
2
1
1

func (*TernarySearchTree) Right

func (l *TernarySearchTree) Right() *node

Right returns the first node of list l or nil if the list is empty.

func (*TernarySearchTree) Store

func (l *TernarySearchTree) Store(key string, value any)

Store stores value by key

Example

package main

import (
	"fmt"

	"github.com/searKing/golang/go/container/trie_tree/ternary_search_tree"
)

func main() {
	tree := ternary_search_tree.New()
	tree.Store("key", "val")

	val, ok := tree.Load("key")
	fmt.Printf("%q:	%q, %v\n", "key", val, ok)
}

Output:

"key":	"val", true

func (*TernarySearchTree) String

func (l *TernarySearchTree) String() string

func (*TernarySearchTree) Traversal

func (l *TernarySearchTree) Traversal(order traversal.Order, handler Handler)

Example

package main

import (
	"fmt"

	"github.com/searKing/golang/go/container/traversal"
	"github.com/searKing/golang/go/container/trie_tree/ternary_search_tree"
)

func main() {
	tree := ternary_search_tree.New()
	tree.Store("test", 1)
	tree.Store("test", 11)
	tree.Store("testing", 2)
	tree.Store("abcd", 0)

	found := false
	tree.Traversal(traversal.Preorder, ternary_search_tree.HandlerFunc(
		func(key []byte, val any) bool {
			if string(key) == "test" && val.(int) == 11 {
				found = true
				return false
			}
			return true
		}))
	fmt.Printf("traversal for key %q, found:	%v\n", "test", found)

}

Output:

traversal for key "test", found:	true