avl

Documentation

Overview

Package avl contains a AVL-tree (Adelson-Velsky and Landis tree) implementation, which is a binary search tree (BST) that performs self-balancing on insertion and deletion.

Index

• type Tree
  • func New[T any](compare func(a, b T) int) Tree[T]
  • func NewFunc[T any, K typ.Ordered](key func(value T) K) Tree[T]
  • func NewOrdered[T typ.Ordered]() Tree[T]
  • func (n *Tree[T]) Add(value T)
  • func (n *Tree[T]) Clear()
  • func (n *Tree[T]) Clone() Tree[T]
  • func (n *Tree[T]) Contains(value T) bool
  • func (n *Tree[T]) Len() int
  • func (n *Tree[T]) Remove(value T) bool
  • func (n *Tree[T]) SliceInOrder() []T
  • func (n *Tree[T]) SlicePostOrder() []T
  • func (n *Tree[T]) SlicePreOrder() []T
  • func (n Tree[T]) String() string
  • func (n *Tree[T]) WalkInOrder(walker func(value T))
  • func (n *Tree[T]) WalkPostOrder(walker func(value T))
  • func (n *Tree[T]) WalkPreOrder(walker func(value T))

Examples

• New
• NewOrdered

Types

type Tree

type Tree[T 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 n) operations on insertion, searching, and deletion.

func New

func New[T any](compare func(a, b T) int) Tree[T]

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

Example

type Name struct {
	First string
	Last  string
}

// Sort first on first name, then on last name
tree := avl.New(func(a, b Name) int {
	v := typ.Compare(a.First, b.First)
	if v == 0 {
		v = typ.Compare(a.Last, b.Last)
	}
	return v
})

// Unordered input
tree.Add(Name{"Bert", "Screws"})
tree.Add(Name{"John", "Doe"})
tree.Add(Name{"Anchor", "Shippie"})
tree.Add(Name{"Bert", "Horton"})
tree.Add(Name{"Jane", "Doe"})

// Sorted output
fmt.Println(tree.Len(), tree)

Output:

5 [{Anchor Shippie} {Bert Horton} {Bert Screws} {Jane Doe} {John Doe}]

func NewFunc

func NewFunc[T any, K typ.Ordered](key func(value T) K) Tree[T]

NewFunc creates a new AVL tree using a key-extractor that should return the key used when comparing and to check equality.

func NewOrdered

func NewOrdered[T typ.Ordered]() Tree[T]

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

Example

package main

import (
	"fmt"

	"gopkg.in/typ.v4/avl"
)

func main() {
	tree := avl.NewOrdered[string]()

	// Unordered input
	tree.Add("E")
	tree.Add("B")
	tree.Add("D")
	tree.Add("C")
	tree.Add("A")

	// Sorted output
	fmt.Println(tree.Len(), tree)

}

Output:

5 [A B C D E]

func (*Tree[T]) Add

func (n *Tree[T]) Add(value T)

Add will add another value to this tree. Duplicate values are allowed and are not dismissed.

func (*Tree[T]) Clear

func (n *Tree[T]) Clear()

Clear will reset this tree to an empty tree.

func (*Tree[T]) Clone

func (n *Tree[T]) Clone() Tree[T]

Clone will return a copy of this tree, with a new set of nodes. The values are copied as-is, so no pointers inside your value type gets a deep clone.

func (*Tree[T]) Contains

func (n *Tree[T]) Contains(value T) bool

Contains checks if a value exists in this tree by iterating the binary search tree.

func (*Tree[T]) Len

func (n *Tree[T]) Len() int

Len returns the number of nodes in this tree.

func (*Tree[T]) Remove

func (n *Tree[T]) Remove(value T) bool

Remove will try to remove the first occurrence of a value from the tree.

func (*Tree[T]) SliceInOrder

func (n *Tree[T]) SliceInOrder() []T

SliceInOrder returns a slice of values by walking the tree in in-order. This returns all values in sorted order. See WalkInOrder for more details.

func (*Tree[T]) SlicePostOrder

func (n *Tree[T]) SlicePostOrder() []T

SlicePostOrder returns a slice of values by walking the tree in post-order. See WalkPostOrder for more details.

func (*Tree[T]) SlicePreOrder

func (n *Tree[T]) SlicePreOrder() []T

SlicePreOrder returns a slice of values by walking the tree in pre-order. See WalkPreOrder for more details.

func (Tree[T]) String

func (n Tree[T]) String() string

func (*Tree[T]) WalkInOrder

func (n *Tree[T]) WalkInOrder(walker func(value T))

WalkInOrder 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[T]) WalkPostOrder

func (n *Tree[T]) WalkPostOrder(walker func(value T))

WalkPostOrder 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[T]) WalkPreOrder

func (n *Tree[T]) WalkPreOrder(walker func(value T))

WalkPreOrder 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.