avl

package
v0.15.7 Latest Latest
Warning

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

Go to latest
Published: Jun 17, 2024 License: ISC Imports: 2 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Item added in v0.11.0

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

func (p *Node) Depth() uint

Depth - get the depth of a node

func (*Node) GetChildrenByDepth added in v0.3.30

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

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

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

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

Search - find a specific item

Jump to

Keyboard shortcuts

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