avl

README

Go-Avl

• AVL Tree for Golang

Install

• go get github.com/cs3238-tsuzu/go-avl

Usage

• import "github.com/cs3238-tsuzu/go-avl"
• Creates a new tree with avl.NewTree(comp)
  • The 1st argument of avl.NewTree() is to compare two keys, Comparator.
  • The value Comparator must returns
    • 1st == 2nd: 0
    • 1st < 2nd: 1
    • 1st > 2nd: -1

License

• Under the MIT License
• Copyright (c) 2017 Tsuzu

Benchmark

goos: darwin
goarch: arm64
pkg: github.com/tsuzu/go-avl
BenchmarkInsertLinearNumbers-10          4092988               319.3 ns/op
BenchmarkGetLinearNumbers-10             9983720               163.5 ns/op
BenchmarkIndexLinearNumbers-10          13540413               130.3 ns/op
BenchmarkEraseLinearNumbers-10           7530286               203.8 ns/op
BenchmarkRankLinearNumbers-10            8986261               173.8 ns/op
PASS
ok      github.com/tsuzu/go-avl 23.888s

Documentation

Index

• type Comparator
• type Node
• type Tree
  • func NewTree[Key any, Value any](comp Comparator[Key]) *Tree[Key, Value]
  • func NewTreeOrdered[Key constraints.Ordered, Value any]() *Tree[Key, Value]
  • func (t *Tree[Key, Value]) Erase(key Key) bool
  • func (t *Tree[Key, Value]) Get(key Key) (*Node[Key, Value], bool)
  • func (t *Tree[Key, Value]) Index(rank int) (*Node[Key, Value], bool)
  • func (t *Tree[Key, Value]) Insert(key Key, val Value) bool
  • func (t *Tree[Key, Value]) Rank(key Key) int
  • func (t *Tree[Key, Value]) Set(key Key, val Value)
  • func (t *Tree[Key, Value]) Size() int

Types

type Comparator

type Comparator[Key any] func(a, b Key) int

Comparator is to compare keys

type Node

type Node[Key any, Value any] struct {
	Key Key
	Val Value
	// contains filtered or unexported fields
}

Node : node for AVL tree

type Tree

type Tree[Key any, Value any] struct {
	// contains filtered or unexported fields
}

Tree : AVL tree

func NewTree

func NewTree[Key any, Value any](comp Comparator[Key]) *Tree[Key, Value]

NewTree creates a new AVL tree

func NewTreeOrdered

func NewTreeOrdered[Key constraints.Ordered, Value any]() *Tree[Key, Value]

NewTree creates a new AVL tree for comparable key types

func (*Tree[Key, Value]) Erase

func (t *Tree[Key, Value]) Erase(key Key) bool

Erase erases the node whose key is 'key' If the key is not found, it returns false.

func (*Tree[Key, Value]) Get

func (t *Tree[Key, Value]) Get(key Key) (*Node[Key, Value], bool)

Get returns the node whose key is 'key' and true. If the key is not found, it returns nil and false.

func (*Tree[Key, Value]) Index

func (t *Tree[Key, Value]) Index(rank int) (*Node[Key, Value], bool)

Index returns the node whose key is 'rank' th and true. If the key is not found, it returns nil and false.

func (*Tree[Key, Value]) Insert

func (t *Tree[Key, Value]) Insert(key Key, val Value) bool

Insert adds a new node with 'key' and 'val' if a node with the key isn't found. Insert do nothing if a node with the key is found.

func (*Tree[Key, Value]) Rank

func (t *Tree[Key, Value]) Rank(key Key) int

Rank returns the index of the node whose key is 'key'. If the key is not found, it returns -1.

func (*Tree[Key, Value]) Set

func (t *Tree[Key, Value]) Set(key Key, val Value)

Set adds a new node with 'key' and 'val' if a node with the key isn't found. Set updates the node with 'key' and 'val' if a node with the key is found.

func (*Tree[Key, Value]) Size

func (t *Tree[Key, Value]) Size() int

Size returns the size of the tree