avl

README

go-avltree

A golang AVL tree implementation. Accepts Ordered (integer, float, and string) types as defined by the constraints package.

Example

package main

import (
	"fmt"

	avl "github.com/al-ce/go-avltree"
)

func main() {
	tree := avl.NewAvlTree[int]()

	for i := 1; i <= 10; i++ {
		tree.Add(i)
	}

	tree.Remove(5)
	tree.Contains(5) // false
	tree.IsEmpty()   // false

	minVal, _ := tree.GetMin() // returns error if tree is empty
	fmt.Println(minVal)  // 1

	fmt.Println(tree.Size()) // 9

	fmt.Println("Traverse (get slice)")
	inorder := tree.InOrderTraverse() // returns []T
	for _, val := range inorder {
		fmt.Printf("%v ", val) // [1 2 3 4 6 7 8 9 10]
	}
	fmt.Println()

	// iter.Next() returns (val T, index int)
	// When index == -1, the iterator has reached the end of the tree
	iter := tree.NewIterator()

	fmt.Println("Iterator:")
	for {
		val, index := iter.Next()
		if index == -1 {
			break
		}
		fmt.Printf("%v ", val) // [1 2 3 4 6 7 8 9 10]
	}
	fmt.Println()

	tree.Clear()
	tree.IsEmpty() // true

	// String example
	stringTree := avl.NewAvlTree[string]()
	p := []string{"tahini", "za'atar", "chickpeas"}
	for _, v := range p {
		stringTree.Add(v)
	}
	ordered := stringTree.InOrderTraverse()
	fmt.Println(ordered) // [chickpeas tahini za'atar]
}

Documentation

Index

• type AvlTree
  • func NewAvlTree[T constraints.Ordered]() *AvlTree[T]
  • func (tree *AvlTree[T]) Add(value T)
  • func (tree *AvlTree[T]) Clear()
  • func (tree *AvlTree[T]) Contains(value T) bool
  • func (tree *AvlTree[T]) GetMax() (T, error)
  • func (tree *AvlTree[T]) GetMin() (T, error)
  • func (tree *AvlTree[T]) InOrderTraverse() []T
  • func (tree *AvlTree[T]) IsEmpty() bool
  • func (tree *AvlTree[T]) NewIterator() *AvlTreeIterator[T]
  • func (tree *AvlTree[T]) Remove(value T) bool
  • func (tree *AvlTree[T]) Size() int
• type AvlTreeIterator
  • func (iter *AvlTreeIterator[T]) Next() (T, int)
• type Node

Types

type AvlTree

type AvlTree[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

func NewAvlTree

func NewAvlTree[T constraints.Ordered]() *AvlTree[T]

func (*AvlTree[T]) Add

func (tree *AvlTree[T]) Add(value T)

Insert a node with the given value and rebalance the tree.

func (*AvlTree[T]) Clear

func (tree *AvlTree[T]) Clear()

Clear the tree, removing all nodes

func (*AvlTree[T]) Contains

func (tree *AvlTree[T]) Contains(value T) bool

Returns a bool indicating whether the value exists in the tree

func (*AvlTree[T]) GetMax

func (tree *AvlTree[T]) GetMax() (T, error)

Return the maximum value in the tree

func (*AvlTree[T]) GetMin

func (tree *AvlTree[T]) GetMin() (T, error)

Return the minimum value in the tree

func (*AvlTree[T]) InOrderTraverse

func (tree *AvlTree[T]) InOrderTraverse() []T

Returns a slice of the tree's values in-order. Appends to the provided pointer to a slice. If the pointer is nil, a new slice is created.

func (*AvlTree[T]) IsEmpty

func (tree *AvlTree[T]) IsEmpty() bool

Returns a bool indicating whether the tree is empty

func (*AvlTree[T]) NewIterator

func (tree *AvlTree[T]) NewIterator() *AvlTreeIterator[T]

Returns a new iterator for the tree. Call Next() on the iterator to get the next value in the tree in-order.

func (*AvlTree[T]) Remove

func (tree *AvlTree[T]) Remove(value T) bool

Remove a node by value lookup and rebalance the tree. Returns true on successful removal, false if value was not found.

func (*AvlTree[T]) Size

func (tree *AvlTree[T]) Size() int

Return the number of nodes in the tree

type AvlTreeIterator

type AvlTreeIterator[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

func (*AvlTreeIterator[T]) Next

func (iter *AvlTreeIterator[T]) Next() (T, int)

Returns the next value in the tree and its index in the in-order traversal from the iterator. If the end of the tree is reached, the zero value of the type is returned and -1 is returned as the index.

type Node

type Node[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}