static

Documentation

Index

• func Ancestor(i, tiersUp int) int
• func Left(i int) int
• func Parent(i int) int
• func Right(i int) int
• type BST
  • func (b *BST) Copy() interface{}
  • func (b *BST) InOrderTraverse() []search.Node
  • func (b *BST) Search(key interface{}) (bool, interface{})
  • func (b *BST) SearchDown(key interface{}, down int) (search.Comparable, interface{})
  • func (b *BST) SearchUp(key interface{}, up int) (search.Comparable, interface{})
  • func (b *BST) Size() int
• type Node
  • func NewNode(k search.Comparable, v search.Equalable) *Node
  • func (n Node) Key() search.Comparable
  • func (n Node) Val() search.Equalable

Functions

func Ancestor

func Ancestor(i, tiersUp int) int

Ancestor returns the index representing this node's ancestor of N generations equivalent to calling Parent tiersUp times

func Left

func Left(i int) int

Left returns the index representing this node's left child.

func Parent

func Parent(i int) int

Parent returns the index represeting this node's direct parent.

func Right

func Right(i int) int

Right returns the index representing this node's right child.

Types

type BST

type BST []*Node

BST in static is an array-based BST, as opposed to a pointer-based BST.

func (*BST) Copy

func (b *BST) Copy() interface{}

func (*BST) InOrderTraverse

func (b *BST) InOrderTraverse() []search.Node

InOrderTraverse : There are multiple ways to traverse a tree. The most useful of these is the in-order traverse, and that's what we provide here. Other traversal methods can be added as needed.

func (*BST) Search

func (b *BST) Search(key interface{}) (bool, interface{})

Search : Search returns the first value of the given key found in the tree. No guarantee is made about what is returned if multiple nodes share the input key. If no key is found, returns (false, nil).

Value vs pointer reciever was benchmarked. Result: maybe pointer is better

func (*BST) SearchDown

func (b *BST) SearchDown(key interface{}, down int) (search.Comparable, interface{})

SearchDown performs a search and rounds down by 'down' steps.

func (*BST) SearchUp

func (b *BST) SearchUp(key interface{}, up int) (search.Comparable, interface{})

SearchUp performs a search and rounds up by 'up' steps.

func (*BST) Size

func (b *BST) Size() int

Size : Return the number of elements in this static tree

type Node

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

Node is a data structures which just contain a key and value

func NewNode

func NewNode(k search.Comparable, v search.Equalable) *Node

NewNode returns a node constructed from the input key and value.

func (Node) Key

func (n Node) Key() search.Comparable

Key returns the key of this node.

func (Node) Val

func (n Node) Val() search.Equalable

Val returns the value of this node.