avl

Documentation

Overview

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 Node
  • func (p *Node) Key() item
  • func (tree *Node) Next() *Node
  • func (tree *Node) Prev() *Node
  • func (p *Node) Value() interface{}
• type Tree
  • func New() *Tree
  • 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) 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) Search(key item) *Node

Types

type Node

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

a node in the tree

func (*Node) Key

func (p *Node) Key() item

read the key from a node

func (*Node) Next

func (tree *Node) Next() *Node

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

func (*Node) Prev

func (tree *Node) Prev() *Node

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{}

read the value from a node

type Tree

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

type to hold the root node of a tree

func New

func New() *Tree

create an initially empty tree

func (*Tree) CheckUp

func (tree *Tree) CheckUp() bool

check the up pointers for consistency

func (*Tree) Count

func (tree *Tree) Count() int

number of nodes currently in the tree

func (*Tree) Delete

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

delete a specific item

func (*Tree) First

func (tree *Tree) First() *Node

return the node with the lowest key value

func (*Tree) Insert

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

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

func (*Tree) IsEmpty

func (tree *Tree) IsEmpty() bool

true if tree contains some data

func (*Tree) Last

func (tree *Tree) Last() *Node

return the node with the highest key value

func (*Tree) Print

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

print an ASCII graphic representation of the tree

func (*Tree) Search

func (tree *Tree) Search(key item) *Node

find a specific item