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) 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 Node

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

a node in the tree

func (*Node) Depth

func (p *Node) Depth() uint

get the depth of a node

func (*Node) GetChildrenByDepth

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

GetChildrenByDepth will returns all children in a specific depth of a 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) Parent

func (p *Node) Parent() *Node

return parent node of a node

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) CheckCounts

func (tree *Tree) CheckCounts() bool

check left and right node counts are ok

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) Get

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

index to specific item

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) 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)

find a specific item