tree

README

goulash/tree

Package tree provides a binary search tree for arbitrary values.

Documentation

Overview

Package tree provides a binary search tree implementation.

There are a few more functions in the coming, when I have time.

Index

• type Node
  • func (t *Node) Contains(v Value) bool
  • func (t *Node) Find(v Value) *Node
  • func (t *Node) Height() int
  • func (t *Node) Max() *Node
  • func (t *Node) Min() *Node
  • func (n *Node) Next() *Node
  • func (n *Node) Prev() *Node
  • func (t *Node) String() string
  • func (n *Node) Val() Value
• type Tree
  • func New(lessFn func(a, b Value) bool) *Tree
  • func (t *Tree) Contains(v Value) bool
  • func (t *Tree) Delete(v Value) bool
  • func (t *Tree) Find(v Value) *Node
  • func (t *Tree) Height() int
  • func (t *Tree) Init(vs []Value)
  • func (t *Tree) Insert(v Value) *Node
  • func (t *Tree) Len() int
  • func (t *Tree) Max() *Node
  • func (t *Tree) Min() *Node
  • func (t *Tree) RandInit(vs []Value)
  • func (t *Tree) Root() *Node
  • func (t *Tree) Slice() []Value
  • func (t *Tree) String() string
• type Value

Types

type Node

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

Node represents the internal nodes of a binary search tree.

If a node is not nil, then it must store a value, and may contain links to one or two subtrees (left and right). A node always has a pointer to the parent node, unless it is the root node.

func (*Node) Contains

func (t *Node) Contains(v Value) bool

Contains searches the (sub)tree for the value v and returns true if it is found.

func (*Node) Find

func (t *Node) Find(v Value) *Node

Find searches the (sub)tree for the value v and returns the node if it is found.

func (*Node) Height

func (t *Node) Height() int

Height calculates the maximum height of the (sub)tree.

Note: a tree with 0 elements has a height of 0; a tree with 1 element must have a height of 1; a tree with 2 elements a height of 2; and a tree with n elements must have a height >= lg n.

func (*Node) Max

func (t *Node) Max() *Node

Max returns the maximum value found in the (sub)tree, or nil if the (sub)tree is empty.

func (*Node) Min

func (t *Node) Min() *Node

Min returns the minimum value found in the (sub)tree, or nil if the (sub)tree is empty.

func (*Node) Next

func (n *Node) Next() *Node

Next returns the next node after n, or nil if n is the last node.

func (*Node) Prev

func (n *Node) Prev() *Node

Prev returns the previous node before n, or nil if n is the first node.

func (*Node) String

func (t *Node) String() string

String provides a string representation of the elements in the (sub)tree, in ascending order.

func (*Node) Val

func (n *Node) Val() Value

Val returns the value stored by the node.

type Tree

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

Tree represents a binary search tree.

The zero value of a Tree is a ready to use tree. Do note however, that you will need a pointer to the tree to use any of the methods.

func New

func New(lessFn func(a, b Value) bool) *Tree

New returns a new Tree to use, with lessFn as the function that gives a < b.

A Tree must be created with this function, otherwise trying to insert into it will cause a panic.

func (*Tree) Contains

func (t *Tree) Contains(v Value) bool

func (*Tree) Delete

func (t *Tree) Delete(v Value) bool

Delete removes the value v from the tree, returning true if successful.

func (*Tree) Find

func (t *Tree) Find(v Value) *Node

func (*Tree) Height

func (t *Tree) Height() int

func (*Tree) Init

func (t *Tree) Init(vs []Value)

Init initializes the tree with elements from vs in the given order.

In the general case, RandInit should be used, as Init cannot hope to have a logarithmic height if vs is sorted in any way.

func (*Tree) Insert

func (t *Tree) Insert(v Value) *Node

Insert inserts a value v into the tree if it does not exist and returns the node containing it.

Note: if the value v already is in the tree, nothing happens. If you really want to know if it succeeded, check Len() before and after.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the size of the tree.

func (*Tree) Max

func (t *Tree) Max() *Node

func (*Tree) Min

func (t *Tree) Min() *Node

func (*Tree) RandInit

func (t *Tree) RandInit(vs []Value)

RandInit initializes the tree with elements from vs in random order.

If you know that vs is already random, then you should use Init instead, as it will be slightly more efficient (about twice as fast).

Note: you are responsible for seeding math/rand.

func (*Tree) Root

func (t *Tree) Root() *Node

Root returns the root node of the tree, which is nil if the tree is empty.

func (*Tree) Slice

func (t *Tree) Slice() []Value

Slice returns the tree as a slice.

The slice is completely disconnected from the tree, you can do whatever you want with it.

func (*Tree) String

func (t *Tree) String() string

type Value

type Value interface{}