tree

README

tree

Package tree contains simple Tree implementations for academic purposes.

BST description

A basic implementation of a Binary Search Tree with nodes: key(int), value(interface{}).

Documentation

Overview

Package tree contains simple Tree implementations for academic purposes.

Package tree ...package tree

Index

• type BST
  • func (b *BST) Inorder() []int
  • func (b *BST) Insert(key int, value interface{}) (n *Node, err error)
  • func (b *BST) InsertKeys(keys ...int) (int, error)
  • func (b *BST) Remove(key int) error
  • func (b *BST) Search(key int) (n *Node)
  • func (b *BST) SearchParent(key int) (n *Node, p *Node)
  • func (b *BST) Size() int
• type Node

Examples

• BST

Types

type BST

type BST struct {
	Root *Node
	// contains filtered or unexported fields
}

BST Binary Search Tree simple implementation. it does NOT have auto balance algorithm.

Example

b := BST{}

_, err := b.Insert(42, nil)

if err != nil {
	//do something
}

b.InsertKeys(30, 50, 24, 60)
fmt.Printf("elements in order:%+v\n", b.Inorder())

b.Remove(50)
fmt.Printf("elements in order:%+v\n", b.Inorder())

fmt.Printf("root is:%v\n", b.Root.K)
fmt.Printf("left of root is:%v\n", b.Root.Left.K)

Output:

elements in order:[24 30 42 50 60]
elements in order:[24 30 42 60]
root is:42
left of root is:30

func (*BST) Inorder

func (b *BST) Inorder() []int

Inorder Get the Inorder list of keys.

func (*BST) Insert

func (b *BST) Insert(key int, value interface{}) (n *Node, err error)

Insert Add a new element.

func (*BST) InsertKeys

func (b *BST) InsertKeys(keys ...int) (int, error)

InsertKeys Add multiple elements. Doesn't support adding values, only keys.

func (*BST) Remove

func (b *BST) Remove(key int) error

Remove Delete an element with a specific key.

func (*BST) Search

func (b *BST) Search(key int) (n *Node)

Search Find a node with a specific key.

func (*BST) SearchParent

func (b *BST) SearchParent(key int) (n *Node, p *Node)

SearchParent Return the node with a specific key, and it's parent.

func (*BST) Size

func (b *BST) Size() int

Size How many elements are now.

type Node

type Node struct {
	K     int
	V     interface{}
	Left  *Node
	Right *Node
}

Node An element of the tree.