avl

Documentation

Index

• Variables
• type Node
  • func (n *Node[K, V]) Key() K
  • func (n *Node[K, V]) MostLeft() *Node[K, V]
  • func (n *Node[K, V]) MostRight() *Node[K, V]
  • func (n *Node[K, V]) NextLeft() *Node[K, V]
  • func (n *Node[K, V]) NextRight() *Node[K, V]
  • func (n *Node[K, V]) Value() V
• type Tree
  • func NewOrderedTree[K typ.Ordered, V any]() Tree[K, V]
  • func NewTree[K, V any](compare func(a, b K) int) Tree[K, V]
  • func NewTreePooled[K, V any](compare func(a, b K) int, pool *sync.Pool) Tree[K, V]
  • func (t *Tree[K, V]) Add(key K, value V) (node *Node[K, V], err error)
  • func (t *Tree[K, V]) Clear()
  • func (t *Tree[K, V]) Contains(key K) bool
  • func (t *Tree[K, V]) Find(key K) *Node[K, V]
  • func (t *Tree[K, V]) IterateInOrder(f func(value V) bool)
  • func (t *Tree[K, V]) IteratePostOrder(f func(value V) bool)
  • func (t *Tree[K, V]) IteratePreOrder(f func(value V) bool)
  • func (t *Tree[K, V]) MostLeft() *Node[K, V]
  • func (t *Tree[K, V]) MostRight() *Node[K, V]
  • func (t *Tree[K, V]) Remove(key K) (value V, err error)
  • func (t *Tree[K, V]) Size() int

Variables

var (
	ErrorTreeNodeDuplicate = errors.New("tree node is duplicated")
	ErrorTreeNodeNotFound  = errors.New("tree node is not found")
)

Types

type Node

type Node[K, V any] struct {
	// contains filtered or unexported fields
}

func (*Node[K, V]) Key

func (n *Node[K, V]) Key() K

Value returns key of the tree node.

func (*Node[K, V]) MostLeft

func (n *Node[K, V]) MostLeft() *Node[K, V]

func (*Node[K, V]) MostRight

func (n *Node[K, V]) MostRight() *Node[K, V]

func (*Node[K, V]) NextLeft

func (n *Node[K, V]) NextLeft() *Node[K, V]

func (*Node[K, V]) NextRight

func (n *Node[K, V]) NextRight() *Node[K, V]

func (*Node[K, V]) Value

func (n *Node[K, V]) Value() V

Value returns value of the tree node.

type Tree

type Tree[K, V any] struct {
	// contains filtered or unexported fields
}

Tree is a binary search tree (BST) for ordered Go types (numbers & strings), implemented as an AVL tree (Adelson-Velsky and Landis tree), a type of self-balancing BST. This guarantees O(log t) operations on insertion, searching, and deletion.

func NewOrderedTree

func NewOrderedTree[K typ.Ordered, V any]() Tree[K, V]

NewOrderedTree creates a new AVL tree using a default comparator function for any ordered type (ints, uints, floats, strings).

func NewTree

func NewTree[K, V any](compare func(a, b K) int) Tree[K, V]

NewTree creates a new AVL tree using a comparator function that is expected to return 0 if a == b, -1 if a < b, and +1 if a > b.

func NewTreePooled

func NewTreePooled[K, V any](compare func(a, b K) int, pool *sync.Pool) Tree[K, V]

NewTreePooled creates a new AVL tree using a comparator function that is expected to return 0 if a == b, -1 if a < b, and +1 if a > b. Pooled tree uses given pool for nodes creating/releasing.

func (*Tree[K, V]) Add

func (t *Tree[K, V]) Add(key K, value V) (node *Node[K, V], err error)

Add inserts a node with given key and value to the tree. Duplicate keys are not allowed so error will be returned on duplicate.

func (*Tree[K, V]) Clear

func (t *Tree[K, V]) Clear()

Clear will reset this tree to an empty tree.

func (*Tree[K, V]) Contains

func (t *Tree[K, V]) Contains(key K) bool

Contains checks if node with given key exists in the tree by iterating the binary search tree.

func (*Tree[K, V]) Find

func (t *Tree[K, V]) Find(key K) *Node[K, V]

Find finds the node with given key in the tree by iterating the binary search tree.

func (*Tree[K, V]) IterateInOrder

func (t *Tree[K, V]) IterateInOrder(f func(value V) bool)

IterateInOrder will iterate all values in this tree by first visiting each node's left branch, followed by the its own value, and then its right branch.

This is useful when reading a tree's values in order, as this guarantees iterating them in a sorted order.

func (*Tree[K, V]) IteratePostOrder

func (t *Tree[K, V]) IteratePostOrder(f func(value V) bool)

IteratePostOrder will iterate all values in this tree by first visiting each node's left branch, followed by the its right branch, and then its own value.

This is useful when deleting values from a tree, as this guarantees to always delete leaf nodes.

func (*Tree[K, V]) IteratePreOrder

func (t *Tree[K, V]) IteratePreOrder(f func(value V) bool)

IteratePreOrder will iterate all values in this tree by first visiting each node's value, followed by the its left branch, and then its right branch.

This is useful when copying binary search trees, as inserting back in this order will guarantee the clone will have the exact same layout.

func (*Tree[K, V]) MostLeft

func (t *Tree[K, V]) MostLeft() *Node[K, V]

MostLeft returns most left node.

func (*Tree[K, V]) MostRight

func (t *Tree[K, V]) MostRight() *Node[K, V]

MostRight returns most right node.

func (*Tree[K, V]) Remove

func (t *Tree[K, V]) Remove(key K) (value V, err error)

Remove removes a node with given value from the tree.

func (*Tree[K, V]) Size

func (t *Tree[K, V]) Size() int

Size returns the amount of nodes in the tree.