avltree

README

avltree

A generic AVL tree for Go.

Most of the code in this package is an adaptation from the Python code in chapter 5 of the book Algorithms in a Nutshell, 2nd edition by George T. Heineman, Gary Pollice & Stanley Selkow, O'Reilly 2016, ISBN: 978-1-491-94892-7.

Documentation

Overview

Package avltree implements a generic AVL tree.

Index

• func CmpOrd[T cmp.Ordered](a, b T) int
• type Cmp
• type Tree
  • func New[T any](cmp Cmp[T], nodups bool) *Tree[T]
  • func (t *Tree[T]) Add(v T) bool
  • func (t *Tree[T]) Clone() *Tree[T]
  • func (t *Tree[T]) Contains(v T) bool
  • func (t *Tree[T]) Count() int
  • func (t *Tree[T]) Del(v T) bool
  • func (t *Tree[T]) Each(fn func(v T))
  • func (t *Tree[T]) Get(v T) (T, bool)
  • func (t *Tree[T]) GetAll(v T) []T
  • func (t *Tree[T]) IsEmpty() bool
  • func (t *Tree[T]) Slice() []T

Functions

func CmpOrd

func CmpOrd[T cmp.Ordered](a, b T) int

CmpOrd is an implementation of the Cmp type for ordered values.

Types

type Cmp

type Cmp[T any] func(a, b T) int

A Cmp function compares two values and returns 0 if a == b, -1 if a < b, and 1 if a > b.

type Tree

type Tree[T any] struct {
	// contains filtered or unexported fields
}

An AVL tree.

func New

func New[T any](cmp Cmp[T], nodups bool) *Tree[T]

New creates a new, empty AVL tree. The function cmp is used for comparing values while navigating the tree. If nodups is true, no duplicate values are allowed and Add() will return false if the value is already present. Panics if cmp is nil.

func (*Tree[T]) Add

func (t *Tree[T]) Add(v T) bool

Add adds a value to the tree.

func (*Tree[T]) Clone

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

Clone clones the tree. This method only makes shallow copies of the values.

func (*Tree[T]) Contains

func (t *Tree[T]) Contains(v T) bool

Contains reports whether the value is present.

func (*Tree[T]) Count

func (t *Tree[T]) Count() int

Count returns the count of values in the tree.

func (*Tree[T]) Del

func (t *Tree[T]) Del(v T) bool

Del removes a value from the tree. Returns false if the value was not found.

func (*Tree[T]) Each

func (t *Tree[T]) Each(fn func(v T))

Each traverses the tree in-order and applies fn to each value.

func (*Tree[T]) Get

func (t *Tree[T]) Get(v T) (T, bool)

Get gets the first value that is equal to v regarding the Cmp function.

func (*Tree[T]) GetAll

func (t *Tree[T]) GetAll(v T) []T

GetAll gets all values that are equal to v regarding the Cmp function.

func (*Tree[T]) IsEmpty

func (t *Tree[T]) IsEmpty() bool

IsEmpty returns true if the tree is empty.

func (*Tree[T]) Slice

func (t *Tree[T]) Slice() []T

Slice returns a slice with all values from the tree. The values will be sorted with regard to the Cmp function.