avl

package
v0.10.6 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 2, 2019 License: ISC Imports: 2 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Node

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

a node in the tree

func (*Node) Depth added in v0.3.30

func (p *Node) Depth() uint

get the depth of a node

func (*Node) GetChildrenByDepth added in v0.3.30

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 added in v0.3.30

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 added in v0.7.0

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 added in v0.7.0

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 added in v0.3.30

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL