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

Expand ▾ Collapse ▴

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

    Constants

    This section is empty.

    Variables

    This section is empty.

    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

                  Source Files