avl

Documentation

Overview

Package avl - an AVL balanced tree with the addition of parent pointers to allow iteration through the nodes

Note: an individual tree is not thread safe, so either access only

in a single go routine or use mutex/rwmutex to restrict
access.

The base algorithm was described in an old book by Niklaus Wirth called Algorithms + Data Structures = Programs.

This version allows for data associated with key, which can be overwritten by an insert with the same key. Also delete no does not copy data around so that previous nodes can be deleted during iteration.

Index

• type Item
• type Node
  • func (p *Node) Depth() uint
  • func (p *Node) GetChildrenByDepth(depth uint) []*Node
  • func (p *Node) Key() Item
  • func (tree *Node) Next() *Node
  • func (p *Node) Parent() *Node
  • func (tree *Node) Prev() *Node
  • func (p *Node) Value() interface{}
• type Tree
  • func New() *Tree
  • func (tree *Tree) CheckCounts() bool
  • func (tree *Tree) CheckUp() bool
  • func (tree *Tree) Count() int
  • func (tree *Tree) Delete(key Item) interface{}
  • func (tree *Tree) First() *Node
  • func (tree *Tree) Get(index int) *Node
  • func (tree *Tree) Insert(key Item, value interface{}) bool
  • func (tree *Tree) IsEmpty() bool
  • func (tree *Tree) Last() *Node
  • func (tree *Tree) Print(printData bool) int
  • func (tree *Tree) Root() *Node
  • func (tree *Tree) Search(key Item) (*Node, int)

Types

type Item

type Item interface {
	Compare(interface{}) int // for left/right ordering of items
}

Item - a key item must implement the Compare function

type Node

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

Node - a node in the tree

func (*Node) Depth

func (p *Node) Depth() uint

Depth - get the depth of a node

func (*Node) GetChildrenByDepth

func (p *Node) GetChildrenByDepth(depth uint) []*Node

GetChildrenByDepth - returns all children in a specific depth of a tree

func (*Node) Key

func (p *Node) Key() Item

Key - read the key from a node item

func (*Node) Next

func (tree *Node) Next() *Node

Next - given a node, return the node with the next highest key value or nil if no more nodes.

func (*Node) Parent

func (p *Node) Parent() *Node

Parent - return parent node of a node

func (*Node) Prev

func (tree *Node) Prev() *Node

Prev - given a node, return the node with the lowest key value or nil if no more nodes

func (*Node) Value

func (p *Node) Value() interface{}

Value - read the value from a node item

type Tree

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

Tree - type to hold the root node of a tree

func New

func New() *Tree

New - create an initially empty tree

func (*Tree) CheckCounts

func (tree *Tree) CheckCounts() bool

CheckCounts - check left and right node counts are ok

func (*Tree) CheckUp

func (tree *Tree) CheckUp() bool

CheckUp - check the up pointers for consistency

func (*Tree) Count

func (tree *Tree) Count() int

Count - number of nodes currently in the tree

func (*Tree) Delete

func (tree *Tree) Delete(key Item) interface{}

Delete - removes a specific item from the tree

func (*Tree) First

func (tree *Tree) First() *Node

First - return the node with the lowest key value

func (*Tree) Get

func (tree *Tree) Get(index int) *Node

Get - access specific item by index

func (*Tree) Insert

func (tree *Tree) Insert(key Item, value interface{}) bool

Insert - insert a new node into the tree returns the possibly updated root

func (*Tree) IsEmpty

func (tree *Tree) IsEmpty() bool

IsEmpty - true if tree contains some data

func (*Tree) Last

func (tree *Tree) Last() *Node

Last - return the node with the highest key value

func (*Tree) Print

func (tree *Tree) Print(printData bool) int

Print - display an ASCII graphic representation of the tree

func (*Tree) Root

func (tree *Tree) Root() *Node

Root - return the root node of the tree

func (*Tree) Search

func (tree *Tree) Search(key Item) (*Node, int)

Search - find a specific item