tree

README

tree

This project now requires go 1.1 to build!

A strongly typed binary search tree in Go without casts or reflection

godoc documentation here: http://godoc.org/github.com/natefinch/tree

The basic idea is simply to separate data storage from data organization. The tree stores the organization, you store the data in a slice or other indexable data structure.

The organization tree uses a compare function similar to that of the standard library's package sort to compare using indexes into your data structure.

See https://github.com/natefinch/treesample for a working sample

License:

MIT License

Documentation

Overview

Package tree implements a very simple binary tree without any balancing. This is mainly intended as a proof of concept for a strongly typed tree in Go without using reflection or casts.

Index

• func Walk(n *Node, f func(*Node) bool) bool
• type Compare
• type Node
• type Tree
  • func (t *Tree) Delete(i int, cmp Compare) (int, error)
  • func (t *Tree) Insert(i int, cmp Compare) (*Node, error)
  • func (t *Tree) Search(i int, cmp Compare) (*Node, error)

Functions

func Walk

func Walk(n *Node, f func(*Node) bool) bool

Walk implements an in-order walk of a tree using recursion.

function f should return false if it wants the walk to stop Walk returns false if f ever returns false, otherwise true

Types

type Compare

type Compare func(i, j int) int8

Comparer is a comparison function that should return -1 if data[i] < data[i], 0 if equal, and 1 if greater than

type Node

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

Node is a node in the tree Val is an index into an external data structure.

type Tree

type Tree struct {
	Head *Node
}

Tree holds a binary tree data organization.

Note that Tree is not intended to hold data itself, it just maintains a structure, and data is retrieved using a node's Val as the index into another data structure that holds the actual values

func (*Tree) Delete

func (t *Tree) Delete(i int, cmp Compare) (int, error)

Delete removes the node of the tree with the value at index i

Delete returns the index of rhte item if the value was found, otherwise will return an error

func (*Tree) Insert

func (t *Tree) Insert(i int, cmp Compare) (*Node, error)

Insert adds the value to the tree.

The value should already exist in the backing datastore at index i returns the node created in the tree and nil, or nil and and error if there was a problem

func (*Tree) Search

func (t *Tree) Search(i int, cmp Compare) (*Node, error)

Search returns the node of the tree with the value at index i if it exists, otherwise nil