avl

avl

import "github.com/zyedidia/generic/avl"

Package avl provides an implementation of an AVL tree. An AVL tree is a self-balancing binary search tree. It stores key-value pairs that are sorted based on the key, and maintains that the tree is always balanced, ensuring logarithmic-time for all operations.

Example

package main

import (
	"fmt"

	g "github.com/zyedidia/generic"
	"github.com/zyedidia/generic/avl"
)

func main() {
	tree := avl.New[int, string](g.Less[int])

	tree.Put(42, "foo")
	tree.Put(-10, "bar")
	tree.Put(0, "baz")
	tree.Put(10, "quux")
	tree.Remove(10)

	tree.Each(func(key int, val string) {
		fmt.Println(key, val)
	})

}

Output

-10 bar
0 baz
42 foo

Index

• type Tree
  • func New[K, V any](less g.LessFn[K]) *Tree[K, V]
  • func (t *Tree[K, V]) Each(fn func(key K, val V))
  • func (t *Tree[K, V]) Get(key K) (V, bool)
  • func (t *Tree[K, V]) Height() int
  • func (t *Tree[K, V]) Put(key K, value V)
  • func (t *Tree[K, V]) Remove(key K)
  • func (t *Tree[K, V]) Size() int

type Tree

Tree implements an AVL tree.

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

func New

func New[K, V any](less g.LessFn[K]) *Tree[K, V]

New returns an empty AVL tree.

func (*Tree[K, V]) Each

func (t *Tree[K, V]) Each(fn func(key K, val V))

Each calls 'fn' on every node in the tree in order

func (*Tree[K, V]) Get

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

Get returns the value associated with 'key'.

func (*Tree[K, V]) Height

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

Height returns the height of the tree.

func (*Tree[K, V]) Put

func (t *Tree[K, V]) Put(key K, value V)

Put associates 'key' with 'value'.

func (*Tree[K, V]) Remove

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

Remove removes the value associated with 'key'.

func (*Tree[K, V]) Size

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

Size returns the number of elements in the tree.

Generated by gomarkdoc