tree

Documentation

Index

• func VisitInOrder(node *Node, call func(interface{}))
• type BST
  • func NewBST(orderFunc lib.OrderFunc) *BST
  • func (bst *BST) Ceiling(elem interface{}) *Node
  • func (bst *BST) Floor(elem interface{}) *Node
  • func (bst *BST) Insert(elem interface{}) *Node
  • func (bst *BST) Search(elem interface{}) *Node
  • func (bst *BST) ToSlice() []interface{}
  • func (bst *BST) Traverse(call func(interface{}))
• type BSTInterface
• type BinaryIndexTree
  • func (bit BinaryIndexTree) Query(x int) int
  • func (bit BinaryIndexTree) Update(x, val int)
• type BinaryIndexTreeInterface
  • func NewBinaryIndexTree(size int) BinaryIndexTreeInterface
• type Node
  • func NewNode(data interface{}) *Node
• type SegmentTree
  • func (st SegmentTree) QueryRange(start, end int) interface{}
  • func (st SegmentTree) UpdateRange(start, end int, updateFunc lib.UpdateFunc)
• type SegmentTreeInterface
  • func NewSegmentTree(qFunc lib.QueryEvalFunc, dFunc lib.DisjointValFunc) SegmentTreeInterface

Functions

func VisitInOrder

func VisitInOrder(node *Node, call func(interface{}))

in-order visit of node

Types

type BST

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

func NewBST

func NewBST(orderFunc lib.OrderFunc) *BST

func (*BST) Ceiling

func (bst *BST) Ceiling(elem interface{}) *Node

func (*BST) Floor

func (bst *BST) Floor(elem interface{}) *Node

func (*BST) Insert

func (bst *BST) Insert(elem interface{}) *Node

func (*BST) Search

func (bst *BST) Search(elem interface{}) *Node

func (*BST) ToSlice

func (bst *BST) ToSlice() []interface{}

func (*BST) Traverse

func (bst *BST) Traverse(call func(interface{}))

type BSTInterface

type BSTInterface interface {
	// Adds new elem to the tree, will not check if same val already exists
	Insert(interface{}) *Node

	// Returns the first node that matches
	Search(interface{}) *Node

	// In-order traversal of tree copied to slice
	ToSlice() []interface{}

	// In-order traversal of tree, calling the func for each element visited
	Traverse(func(interface{}))

	// Returns the largest value node that is smaller than or equal to the given value.
	Floor(interface{}) *Node

	// Returns the smallest value node that is larger than or equal to the given value.
	Ceiling(interface{}) *Node
}

Binary Search Tree implementation https://en.wikipedia.org/wiki/Binary_search_tree Element comparison is based on OrderFunc provided to NewBST method

type BinaryIndexTree

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

func (BinaryIndexTree) Query

func (bit BinaryIndexTree) Query(x int) int

func (BinaryIndexTree) Update

func (bit BinaryIndexTree) Update(x, val int)

type BinaryIndexTreeInterface

type BinaryIndexTreeInterface interface {
	//add "val" at index "x"
	Update(x, val int)

	//returns the sum of first x elements
	Query(x int) int
}

func NewBinaryIndexTree

func NewBinaryIndexTree(size int) BinaryIndexTreeInterface

type Node

type Node struct {
	Left  *Node
	Right *Node
	Data  interface{}
}

func NewNode

func NewNode(data interface{}) *Node

type SegmentTree

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

func (SegmentTree) QueryRange

func (st SegmentTree) QueryRange(start, end int) interface{}

func (SegmentTree) UpdateRange

func (st SegmentTree) UpdateRange(start, end int, updateFunc lib.UpdateFunc)

type SegmentTreeInterface

type SegmentTreeInterface interface {
	UpdateRange(start, end int, updateFunc lib.UpdateFunc)
	QueryRange(start, end int) interface{}
}

func NewSegmentTree

func NewSegmentTree(qFunc lib.QueryEvalFunc, dFunc lib.DisjointValFunc) SegmentTreeInterface