bstree

Documentation

Overview

Package Binary Search Tree functions

Example (BsTree)

package main

import (
	"fmt"
	"github.com/jenazads/gods/trees/bstree"
	"github.com/jenazads/goutils"
)

func main() {
	tree := bstree.NewBSTree(goutils.IntComparator, goutils.IntOperator)

	tree.Insert(5, "e")
	tree.Insert(2, "b")
	tree.Insert(3, "c")
	tree.Insert(1, "a")
	tree.Insert(4, "d")
	tree.Insert(6, "f")
	tree.Insert(7, "g")
	tree.Insert(8, "h")

	tree.PrintPreOrder()
	tree.PrintInOrder()
	tree.PrintPostOrder()

	fmt.Println(tree.Ceiling(4))
	fmt.Println(tree.Floor(5))
	tree.Print()

	fmt.Println(tree.Values())
	fmt.Println(tree.Keys())

	fmt.Print(tree)
	tree.Remove(3)
	fmt.Println(tree)
	tree.Remove(2)
	fmt.Println(tree)
	tree.Remove(7)
	fmt.Println(tree)
	tree.Remove(5)
	fmt.Println(tree)
	tree.Remove(4)
	fmt.Println(tree)
	tree.Remove(1)
	fmt.Println(tree)
	tree.Remove(6)
	fmt.Println(tree)
	tree.Remove(8)
	fmt.Println(tree)

	tree.Clear()
	tree.IsEmpty()
	tree.Size()
}

Index

• func IsLeaf(node *BSTNode) bool
• type BSTNode
  • func NewBSTNode(key interface{}, p *BSTNode) *BSTNode
  • func (node *BSTNode) Next() *BSTNode
  • func (node *BSTNode) Prev() *BSTNode
  • func (node *BSTNode) String() string
• type BSTree
  • func NewBSTree(comp goutils.TypeComparator, op goutils.TypeOperator) *BSTree
  • func (t *BSTree) Brother(key interface{}) *BSTNode
  • func (t *BSTree) Ceiling(key interface{}) *BSTNode
  • func (t *BSTree) Clear()
  • func (t *BSTree) Floor(key interface{}) *BSTNode
  • func (t *BSTree) FromJSON(data []byte) error
  • func (t *BSTree) Get(key interface{}) interface{}
  • func (t *BSTree) Height() int
  • func (t *BSTree) HeightOfNode(key interface{}) int
  • func (t *BSTree) Insert(key interface{}, value interface{})
  • func (t *BSTree) IsEmpty() bool
  • func (t *BSTree) IsSameAs(otherTree *BSTree) bool
  • func (t *BSTree) Iterator() goutils.ReverseIteratorKey
  • func (t *BSTree) Keys() []interface{}
  • func (t *BSTree) LeafCount() int
  • func (t *BSTree) Left() *BSTNode
  • func (t *BSTree) Mirror()
  • func (t *BSTree) Parent(key interface{}) *BSTNode
  • func (t *BSTree) Print()
  • func (t *BSTree) PrintInOrder()
  • func (t *BSTree) PrintPostOrder()
  • func (t *BSTree) PrintPreOrder()
  • func (t *BSTree) Remove(key interface{})
  • func (t *BSTree) Right() *BSTNode
  • func (t *BSTree) Search(key interface{}) *BSTNode
  • func (t *BSTree) Size() int
  • func (t *BSTree) String() string
  • func (t *BSTree) SumNodes() interface{}
  • func (t *BSTree) ToJSON() ([]byte, error)
  • func (t *BSTree) Values() []interface{}
• type Iterator
  • func (iterator *Iterator) Begin()
  • func (iterator *Iterator) End()
  • func (iterator *Iterator) First() bool
  • func (iterator *Iterator) Key() interface{}
  • func (iterator *Iterator) Last() bool
  • func (iterator *Iterator) Next() bool
  • func (iterator *Iterator) Prev() bool
  • func (iterator *Iterator) Value() interface{}

Examples

• Package (BsTree)

Functions

func IsLeaf

func IsLeaf(node *BSTNode) bool

Return true if the node is leaf

Types

type BSTNode

type BSTNode struct {
	Key      interface{}
	Value    []interface{}
	Count    int
	Parent   *BSTNode    // Parent node
	Children [2]*BSTNode // Children nodes, 0-> left, 1-> right
}

Node

func NewBSTNode

func NewBSTNode(key interface{}, p *BSTNode) *BSTNode

New BS Node

func (*BSTNode) Next

func (node *BSTNode) Next() *BSTNode

Return next or sucessor node

func (*BSTNode) Prev

func (node *BSTNode) Prev() *BSTNode

Return previous or predecessor node

func (*BSTNode) String

func (node *BSTNode) String() string

Print Node with fmt.Print*

type BSTree

type BSTree struct {
	Root *BSTNode // Root node
	// contains filtered or unexported fields
}

BSTree object

func NewBSTree

func NewBSTree(comp goutils.TypeComparator, op goutils.TypeOperator) *BSTree

New BS Tree

func (*BSTree) Brother

func (t *BSTree) Brother(key interface{}) *BSTNode

Return the brother of a specific value

func (*BSTree) Ceiling

func (t *BSTree) Ceiling(key interface{}) *BSTNode

Return the smallest node that is larger than or equal to the given node.

func (*BSTree) Clear

func (t *BSTree) Clear()

Removes all nodes

func (*BSTree) Floor

func (t *BSTree) Floor(key interface{}) *BSTNode

Return the largest node that is smaller than or equal to the given node.

func (*BSTree) FromJSON

func (t *BSTree) FromJSON(data []byte) error

FromJSON Convert to JSON format the elements

func (*BSTree) Get

func (t *BSTree) Get(key interface{}) interface{}

Get Value

func (*BSTree) Height

func (t *BSTree) Height() int

return BS Tree Height

func (*BSTree) HeightOfNode

func (t *BSTree) HeightOfNode(key interface{}) int

Return the height of a specific node

func (*BSTree) Insert

func (t *BSTree) Insert(key interface{}, value interface{})

Insert New Node by Key

func (*BSTree) IsEmpty

func (t *BSTree) IsEmpty() bool

IsEmpty, true if tree doesnt have nodes

func (*BSTree) IsSameAs

func (t *BSTree) IsSameAs(otherTree *BSTree) bool

Compare 2 BSTree

func (*BSTree) Iterator

func (t *BSTree) Iterator() goutils.ReverseIteratorKey

Iterator returns a stateful iterator whose elements are key/value pairs.

func (*BSTree) Keys

func (t *BSTree) Keys() []interface{}

Keys returns all keys in-order

func (*BSTree) LeafCount

func (t *BSTree) LeafCount() int

Return number of Leaf

func (*BSTree) Left

func (t *BSTree) Left() *BSTNode

Return minimum element

func (*BSTree) Mirror

func (t *BSTree) Mirror()

Return bst mirror

func (*BSTree) Parent

func (t *BSTree) Parent(key interface{}) *BSTNode

Return the parent node of a specific value

func (*BSTree) Print

func (t *BSTree) Print()

Print the BSTree

func (*BSTree) PrintInOrder

func (t *BSTree) PrintInOrder()

print inorder

func (*BSTree) PrintPostOrder

func (t *BSTree) PrintPostOrder()

print postorder

func (*BSTree) PrintPreOrder

func (t *BSTree) PrintPreOrder()

print preorder

func (*BSTree) Remove

func (t *BSTree) Remove(key interface{})

Remove Node by key

func (*BSTree) Right

func (t *BSTree) Right() *BSTNode

Return maximum element

func (*BSTree) Search

func (t *BSTree) Search(key interface{}) *BSTNode

Search Value, return the node

func (*BSTree) Size

func (t *BSTree) Size() int

Return Size of tree

func (*BSTree) String

func (t *BSTree) String() string

Print Tree with fmt.Print*

func (*BSTree) SumNodes

func (t *BSTree) SumNodes() interface{}

Return sum of all nodes

func (*BSTree) ToJSON

func (t *BSTree) ToJSON() ([]byte, error)

ToJSON return JSON format of elements

func (*BSTree) Values

func (t *BSTree) Values() []interface{}

Values returns all values in-order based on the key.

type Iterator

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

Iterator

func (*Iterator) Begin

func (iterator *Iterator) Begin()

Set pointer to Begin state

func (*Iterator) End

func (iterator *Iterator) End()

Set pointer to last state

func (*Iterator) First

func (iterator *Iterator) First() bool

Moves to the first element

func (*Iterator) Key

func (iterator *Iterator) Key() interface{}

Return current Key

func (*Iterator) Last

func (iterator *Iterator) Last() bool

Moves to the Last element

func (*Iterator) Next

func (iterator *Iterator) Next() bool

Moves to the next element

func (*Iterator) Prev

func (iterator *Iterator) Prev() bool

Move to the Prev element

func (*Iterator) Value

func (iterator *Iterator) Value() interface{}

Return current value