avltrees

package module
v0.0.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 26, 2025 License: MIT Imports: 2 Imported by: 0

README

avltrees GoDoc Go Report Card

A generic self-balancing AVL tree for Go with rank, k-th, and range queries.

✨ Features

  • Self-balancing AVL Tree with O(log n) insert/delete/search
  • Order-statistics support: rank, k-th element, and range queries
  • Generic (Go generics)
  • In-order iterator
  • Memory-efficient (no extra allocations on lookup)

✅ Use When

  • You need fast and predictable search performance
  • You want rank or k-th queries
  • Your workload is read-heavy or search-dominant

🚫 Avoid If

  • You need frequent insertions and deletions with minimal balancing overhead → use Red-Black Tree
  • You need concurrent access (not thread-safe)

📦 Installation

go get github.com/byExist/avltrees

🚀 Quick Start

package main

import (
	"fmt"
	avlt "github.com/byExist/avltrees"
)

func main() {
	tree := avlt.New[int, string]()
	avlt.Insert(tree, 10, "ten")
	avlt.Insert(tree, 5, "five")
	avlt.Insert(tree, 20, "twenty")

	if node, found := avlt.Search(tree, 10); found {
		fmt.Println("Found:", node.Value())
	}

	for n := range avlt.InOrder(tree) {
		fmt.Println(n.Key(), "->", n.Value())
	}
}

📊 Performance

Benchmarked on Apple M1 Pro:

Operation Time (ns/op) Memory (B/op) Allocations
Insert (Random) 669.3 26 B 0
Insert (Sequential) 151.6 64 B 1
Search (Hit) 11.52 0 B 0
Search (Miss) 7.58 0 B 0
Delete (Random) 2.90 0 B 0

🪪 License

MIT License. See LICENSE.

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Clear 

func Clear[K cmp.Ordered, V any](t *Tree[K, V])

Clear removes all nodes from the AVL tree.

func Delete 

func Delete[K cmp.Ordered, V any](t *Tree[K, V], key K) bool

Delete removes the node with the specified key from the AVL tree. Returns true if the key existed and was deleted.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 10, "ten")
	avlts.Delete(tree, 10)
	fmt.Println(avlts.Len(tree))
}

Output:

0

func InOrder 

func InOrder[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq[Node[K, V]]

InOrder returns an iterator for in-order traversal of the AVL tree.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 20, "")
	avlts.Insert(tree, 10, "")
	avlts.Insert(tree, 30, "")
	for n := range avlts.InOrder(tree) {
		fmt.Print(n.Key(), " ")
	}
	fmt.Println()
}

Output:

10 20 30

func Insert 

func Insert[K cmp.Ordered, V any](t *Tree[K, V], key K, value V) bool

Insert inserts a key-value pair into the AVL tree. Returns true if the key was inserted, or false if it replaced an existing key.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 10, "ten")
	avlts.Insert(tree, 5, "five")
	avlts.Insert(tree, 15, "fifteen")
	fmt.Println(avlts.Len(tree))
}

Output:

3

func Len 

func Len[K cmp.Ordered, V any](t *Tree[K, V]) int

Len returns the number of nodes in the AVL tree.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	fmt.Println(avlts.Len(tree))
}

Output:

0

func Range 

func Range[K cmp.Ordered, V any](t *Tree[K, V], from, to K) iter.Seq[Node[K, V]]

Range returns an iterator for nodes with keys in the range [from, to).

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 10, "")
	avlts.Insert(tree, 20, "")
	avlts.Insert(tree, 30, "")
	for n := range avlts.Range(tree, 15, 25) {
		fmt.Print(n.Key(), " ")
	}
	fmt.Println()
}

Output:

20

func Rank 

func Rank[K cmp.Ordered, V any](t *Tree[K, V], key K) int

Rank returns the number of nodes with keys less than the given key.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 10, "")
	avlts.Insert(tree, 20, "")
	rank := avlts.Rank(tree, 15)
	fmt.Println(rank)
}

Output:

1

Types

type Node 

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

Node represents a node in the AVL tree.

func Ceiling 

func Ceiling[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Ceiling returns the node with the smallest key greater than or equal to the given key. Returns the node and true if such a key exists, or nil and false otherwise.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		avlts.Insert(tree, v, "")
	}

	n, _ := avlts.Ceiling(tree, 15)
	fmt.Println(n.Key())
	n, _ = avlts.Ceiling(tree, 20)
	fmt.Println(n.Key())
}

Output:

20
20

func Floor 

func Floor[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Floor returns the node with the largest key less than or equal to the given key. Returns the node and true if such a key exists, or nil and false otherwise.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		avlts.Insert(tree, v, "")
	}

	n, _ := avlts.Floor(tree, 25)
	fmt.Println(n.Key())
	n, _ = avlts.Floor(tree, 20)
	fmt.Println(n.Key())
}

Output:

20
20

func Higher 

func Higher[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Higher returns the node with the smallest key greater than the given key. Returns the node and true if such a key exists, or nil and false otherwise.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		avlts.Insert(tree, v, "")
	}

	n, _ := avlts.Higher(tree, 15)
	fmt.Println(n.Key())
	n, _ = avlts.Higher(tree, 20)
	fmt.Println(n.Key())
}

Output:

20
30

func Kth 

func Kth[K cmp.Ordered, V any](t *Tree[K, V], k int) (*Node[K, V], bool)

Kth returns the node with the given 0-based rank. Returns the node and true if such rank exists, or nil and false otherwise.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 10, "")
	avlts.Insert(tree, 20, "")
	n, _ := avlts.Kth(tree, 1)
	fmt.Println(n.Key())
}

Output:

20

func Lower 

func Lower[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Lower returns the node with the largest key less than the given key. Returns the node and true if such a key exists, or nil and false otherwise.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		avlts.Insert(tree, v, "")
	}

	n, _ := avlts.Lower(tree, 15)
	fmt.Println(n.Key())
	n, _ = avlts.Lower(tree, 20)
	fmt.Println(n.Key())
}

Output:

10
10

func Max 

func Max[K cmp.Ordered, V any](t *Tree[K, V]) (*Node[K, V], bool)

Max returns the node with the largest key in the AVL tree. Returns the node and true if the tree is not empty, or nil and false otherwise.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 20, "")
	avlts.Insert(tree, 30, "")
	max, ok := avlts.Max(tree)
	if ok {
		fmt.Println(max.Key())
	}
}

Output:

30

func Min 

func Min[K cmp.Ordered, V any](t *Tree[K, V]) (*Node[K, V], bool)

Min returns the node with the smallest key in the AVL tree. Returns the node and true if the tree is not empty, or nil and false otherwise.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 20, "")
	avlts.Insert(tree, 10, "")
	min, ok := avlts.Min(tree)
	if ok {
		fmt.Println(min.Key())
	}
}

Output:

10

func Predecessor 

func Predecessor[K cmp.Ordered, V any](n *Node[K, V]) (*Node[K, V], bool)

Predecessor returns the in-order predecessor of the given node, if any.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 20, "")
	avlts.Insert(tree, 10, "")
	node, _ := avlts.Search(tree, 20)
	pred, ok := avlts.Predecessor(node)
	if ok {
		fmt.Println(pred.Key())
	}
}

Output:

10

func Search[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Search finds and returns the node with the given key in the AVL tree. Returns the node and true if found, or nil and false otherwise.

func Successor 

func Successor[K cmp.Ordered, V any](n *Node[K, V]) (*Node[K, V], bool)

Successor returns the in-order successor of the given node, if any.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	avlts.Insert(tree, 20, "")
	avlts.Insert(tree, 30, "")
	node, _ := avlts.Search(tree, 20)
	succ, ok := avlts.Successor(node)
	if ok {
		fmt.Println(succ.Key())
	}
}

Output:

30

func (*Node[K, V]) Key 

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

Key returns the key of the node.

func (*Node[K, V]) Value 

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

Value returns the value of the node.

type Tree 

type Tree[K cmp.Ordered, V any] struct {
	Root *Node[K, V]
}

Tree represents an AVL tree.

func New 

func New[K cmp.Ordered, V any]() *Tree[K, V]

New returns a new empty AVL Tree.

Example 
package main

import (
	"fmt"

	avlts "github.com/byExist/avltrees"
)

func main() {
	tree := avlts.New[int, string]()
	fmt.Println(avlts.Len(tree))
}

Output:

0

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.