bbst

package module
v0.0.0-...-067d9b8 Latest Latest
Warning

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

 Go to latest Published: Jan 18, 2026 License: Apache-2.0 Imports: 2 Imported by: 0

README

bbst

balanced binary search tree library implementation in golang

avl.go: avl tree implementation without parent pointer

pavl.go: avl tree implementation with parent pointer

rb.go: red black tree implementation without parent pointer

prb.go: red black tree implementation with parent pointer

Example
set:
package main

import (
    "fmt"
    "math/rand"
    "time"

    "github.com/unixisevil/bbst"
)

func randRange(min, max int) int {
    return min + rand.Int()%(max-min+1)
}

var intCmp bbst.Compare = func(a, b interface{}, extraParam interface{}) int {
    ia := a.(int)
    ib := b.(int)
    if ia < ib {
        return -1
    } else if ia > ib {
        return 1
    } else {
        return 0
    }
}

func main() {
    rand.Seed(time.Now().Unix())

    set := bbst.NewAvlTree(intCmp, nil)
    for i := 0; i < 10; i++ {
        set.Insert(randRange(100, 200))
    }

    it := set.Iter()
    for item := it.First(); item != nil; {
        num := item.(int)
        fmt.Printf("got: %d\n", num)
        //skip to next element before delete current element, avoid using invalid iterator
        item = it.Next()
        if num%2 == 0 {
            set.Delete(num)
        }
    }
    fmt.Println()
    for item := it.Last(); item != nil; item = it.Prev() {
        fmt.Printf("got: %d\n", item)
    }
}
map:
package main

import (
    "fmt"

    "github.com/unixisevil/bbst"
)

type kv struct {
    k string
    v int
}

var mapCmp bbst.Compare = func(a, b interface{}, extraParam interface{}) int {
    akv := a.(kv)
    bkv := b.(kv)
    if akv.k < bkv.k {
        return -1
    } else if akv.k > bkv.k {
        return 1
    } else {
        return 0
    }
}

func main() {
    m := bbst.NewAvlTree(mapCmp, nil)
    m.Insert(kv{"GPU", 15})
    m.Insert(kv{"RAM", 20})
    m.Insert(kv{"CPU", 10})

    it := m.Iter()
    for item := it.First(); item != nil; item = it.Next() {
        e := item.(kv)
        fmt.Printf("k = %v, v = %v\n", e.k, e.v)
    }
    fmt.Println()
    m.Replace(kv{"CPU", 25})
    m.Insert(kv{"SSD", 30})
    for item := it.First(); item != nil; item = it.Next() {
        e := item.(kv)
        fmt.Printf("k = %v, v = %v\n", e.k, e.v)
    }

}
multi-map:
package main

import (
    "fmt"

    "github.com/unixisevil/bbst"
)

type mkv struct {
    char rune
    pos  []int
}

var multiMapCmp bbst.Compare = func(a, b interface{}, extraParam interface{}) int {
    akv := a.(mkv)
    bkv := b.(mkv)
    if akv.char < bkv.char {
        return -1
    } else if akv.char > bkv.char {
        return 1
    } else {
        return 0
    }
}

func main() {
    m := bbst.NewAvlTree(multiMapCmp, nil)
    str := "this is it"
    for pos, char := range str {
        if char == ' ' {
            continue
        }
        if item := m.Find(mkv{char: char}); item == nil {
            posArr := []int{pos}
            m.Replace(mkv{char: char, pos: posArr})
        } else {
            kv := item.(mkv)
            kv.pos = append(kv.pos, pos)
            m.Replace(kv)
        }
    }

    it := m.Iter()
    for item := it.First(); item != nil; item = it.Next() {
        e := item.(mkv)
        fmt.Printf("char = %c, pos = %v\n", e.char, e.pos)
    }
}
running the tests:
go test -v  -run 'Int' -insOrder 0  -delOrder 0 -type 1 -size 1000  -verbose 3

go test -v  -run 'Map'  -type 3
running the benchmarks:
go test    -bench=.   -benchtime=10000x  -size 1000

Documentation

Index

Constants

View Source 
const (
	Left = iota
	Right
	ChildNum
)

Variables

This section is empty.

Functions

This section is empty.

Types

type AvlIter 

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

func NewAvlIter 

func NewAvlIter[T any]() *AvlIter[T]

func (*AvlIter[T]) CopyFrom 

func (it *AvlIter[T]) CopyFrom(other *AvlIter[T]) (T, bool)

func (*AvlIter[T]) Current 

func (it *AvlIter[T]) Current() (T, bool)

func (*AvlIter[T]) Find 

func (it *AvlIter[T]) Find(item T) (T, bool)

func (*AvlIter[T]) First 

func (it *AvlIter[T]) First() (T, bool)

func (*AvlIter[T]) HookWith 

func (it *AvlIter[T]) HookWith(tree *AvlTree[T]) *AvlIter[T]

func (*AvlIter[T]) Insert 

func (it *AvlIter[T]) Insert(item T) (*T, bool)

func (*AvlIter[T]) Last 

func (it *AvlIter[T]) Last() (T, bool)

func (*AvlIter[T]) Next 

func (it *AvlIter[T]) Next() (T, bool)

func (*AvlIter[T]) Prev 

func (it *AvlIter[T]) Prev() (T, bool)

func (*AvlIter[T]) Replace 

func (it *AvlIter[T]) Replace(new T) (T, bool)

Replace replaces the current item. Don't change the key part of item.

type AvlTree 

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

func NewAvlTree 

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

NewAvlTree creates a new AVL tree for cmp.Ordered types (int, string, float64, etc.)

func NewAvlTreeFunc 

func NewAvlTreeFunc[T any](cmpFn Compare[T]) *AvlTree[T]

NewAvlTreeFunc creates a new AVL tree with a custom comparison function.

func (*AvlTree[T]) All 

func (t *AvlTree[T]) All() iter.Seq[T]

All returns a forward iterator for use with range-over-function.

func (*AvlTree[T]) Backward 

func (t *AvlTree[T]) Backward() iter.Seq[T]

Backward returns a reverse iterator for use with range-over-function.

func (*AvlTree[T]) Copy 

func (t *AvlTree[T]) Copy() *AvlTree[T]

func (*AvlTree[T]) Count 

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

func (*AvlTree[T]) Delete 

func (t *AvlTree[T]) Delete(item T) (T, bool)

Delete deletes item from tree. Returns the deleted item and true if found, zero value and false otherwise.

func (*AvlTree[T]) Find 

func (t *AvlTree[T]) Find(target T) (T, bool)

Find searches for target in tree. Returns the item and true if found, zero value and false otherwise.

func (*AvlTree[T]) Insert 

func (t *AvlTree[T]) Insert(item T) bool

Insert inserts item in tree. Returns true if item was successfully inserted, false if item already in tree.

func (*AvlTree[T]) Iter 

func (t *AvlTree[T]) Iter() *AvlIter[T]

func (*AvlTree[T]) Replace 

func (t *AvlTree[T]) Replace(item T) (T, bool)

Replace replaces item in tree with same key. Returns the old item and true if replaced, zero value and false otherwise.

type Compare 

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

Compare is the comparison function signature for custom types. Returns negative if a < b, positive if a > b, zero if a == b.

func OrderedCompare 

func OrderedCompare[T cmp.Ordered]() Compare[T]

OrderedCompare returns the standard comparison function for cmp.Ordered types.

type Iterator 

type Iterator[T any] interface {
	First() (T, bool)
	Last() (T, bool)
	Prev() (T, bool)
	Next() (T, bool)
	Current() (T, bool)
}

Iterator provides bidirectional iteration over tree elements.

type PAvlIter 

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

func NewPAvlIter 

func NewPAvlIter[T any]() *PAvlIter[T]

func (*PAvlIter[T]) CopyFrom 

func (it *PAvlIter[T]) CopyFrom(other *PAvlIter[T]) (T, bool)

func (*PAvlIter[T]) Current 

func (it *PAvlIter[T]) Current() (T, bool)

func (*PAvlIter[T]) Find 

func (it *PAvlIter[T]) Find(item T) (T, bool)

func (*PAvlIter[T]) First 

func (it *PAvlIter[T]) First() (T, bool)

func (*PAvlIter[T]) HookWith 

func (it *PAvlIter[T]) HookWith(tree *PAvlTree[T]) *PAvlIter[T]

func (*PAvlIter[T]) Insert 

func (it *PAvlIter[T]) Insert(item T) (*T, bool)

func (*PAvlIter[T]) Last 

func (it *PAvlIter[T]) Last() (T, bool)

func (*PAvlIter[T]) Next 

func (it *PAvlIter[T]) Next() (T, bool)

func (*PAvlIter[T]) Prev 

func (it *PAvlIter[T]) Prev() (T, bool)

func (*PAvlIter[T]) Replace 

func (it *PAvlIter[T]) Replace(new T) (T, bool)

Replace replaces the current item. Don't change the key part of item.

type PAvlTree 

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

func NewPAvlTree 

func NewPAvlTree[T cmp.Ordered]() *PAvlTree[T]

NewPAvlTree creates a new AVL tree with parent pointers for cmp.Ordered types.

func NewPAvlTreeFunc 

func NewPAvlTreeFunc[T any](cmpFn Compare[T]) *PAvlTree[T]

NewPAvlTreeFunc creates a new AVL tree with parent pointers using a custom comparison function.

func (*PAvlTree[T]) All 

func (t *PAvlTree[T]) All() iter.Seq[T]

All returns a forward iterator for use with range-over-function.

func (*PAvlTree[T]) Backward 

func (t *PAvlTree[T]) Backward() iter.Seq[T]

Backward returns a reverse iterator for use with range-over-function.

func (*PAvlTree[T]) Copy 

func (t *PAvlTree[T]) Copy() *PAvlTree[T]

func (*PAvlTree[T]) Count 

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

func (*PAvlTree[T]) Delete 

func (t *PAvlTree[T]) Delete(item T) (T, bool)

Delete deletes item from tree. Returns the deleted item and true if found, zero value and false otherwise.

func (*PAvlTree[T]) Find 

func (t *PAvlTree[T]) Find(target T) (T, bool)

Find searches for target in tree. Returns the item and true if found, zero value and false otherwise.

func (*PAvlTree[T]) Insert 

func (t *PAvlTree[T]) Insert(item T) bool

Insert inserts item in tree. Returns true if item was successfully inserted, false if item already in tree.

func (*PAvlTree[T]) Iter 

func (t *PAvlTree[T]) Iter() *PAvlIter[T]

func (*PAvlTree[T]) Replace 

func (t *PAvlTree[T]) Replace(item T) (T, bool)

Replace replaces item in tree with same key. Returns the old item and true if replaced, zero value and false otherwise.

type PRbIter 

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

func NewPRbIter 

func NewPRbIter[T any]() *PRbIter[T]

func (*PRbIter[T]) CopyFrom 

func (it *PRbIter[T]) CopyFrom(other *PRbIter[T]) (T, bool)

func (*PRbIter[T]) Current 

func (it *PRbIter[T]) Current() (T, bool)

func (*PRbIter[T]) Find 

func (it *PRbIter[T]) Find(item T) (T, bool)

func (*PRbIter[T]) First 

func (it *PRbIter[T]) First() (T, bool)

func (*PRbIter[T]) HookWith 

func (it *PRbIter[T]) HookWith(tree *PRbTree[T]) *PRbIter[T]

func (*PRbIter[T]) Insert 

func (it *PRbIter[T]) Insert(item T) (*T, bool)

func (*PRbIter[T]) Last 

func (it *PRbIter[T]) Last() (T, bool)

func (*PRbIter[T]) Next 

func (it *PRbIter[T]) Next() (T, bool)

func (*PRbIter[T]) Prev 

func (it *PRbIter[T]) Prev() (T, bool)

func (*PRbIter[T]) Replace 

func (it *PRbIter[T]) Replace(new T) (T, bool)

Replace replaces the current item. Don't change the key part of item.

type PRbTree 

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

func NewPRbTree 

func NewPRbTree[T cmp.Ordered]() *PRbTree[T]

NewPRbTree creates a new Red-Black tree with parent pointers for cmp.Ordered types.

func NewPRbTreeFunc 

func NewPRbTreeFunc[T any](cmpFn Compare[T]) *PRbTree[T]

NewPRbTreeFunc creates a new Red-Black tree with parent pointers using a custom comparison function.

func (*PRbTree[T]) All 

func (t *PRbTree[T]) All() iter.Seq[T]

All returns a forward iterator for use with range-over-function.

func (*PRbTree[T]) Backward 

func (t *PRbTree[T]) Backward() iter.Seq[T]

Backward returns a reverse iterator for use with range-over-function.

func (*PRbTree[T]) Copy 

func (t *PRbTree[T]) Copy() *PRbTree[T]

func (*PRbTree[T]) Count 

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

func (*PRbTree[T]) Delete 

func (t *PRbTree[T]) Delete(item T) (T, bool)

Delete deletes item from tree. Returns the deleted item and true if found, zero value and false otherwise.

func (*PRbTree[T]) Find 

func (t *PRbTree[T]) Find(target T) (T, bool)

Find searches for target in tree. Returns the item and true if found, zero value and false otherwise.

func (*PRbTree[T]) Insert 

func (t *PRbTree[T]) Insert(item T) bool

Insert inserts item in tree. Returns true if item was successfully inserted, false if item already in tree.

func (*PRbTree[T]) Iter 

func (t *PRbTree[T]) Iter() *PRbIter[T]

func (*PRbTree[T]) Replace 

func (t *PRbTree[T]) Replace(item T) (T, bool)

Replace replaces item in tree with same key. Returns the old item and true if replaced, zero value and false otherwise.

type RbIter 

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

func NewRbIter 

func NewRbIter[T any]() *RbIter[T]

func (*RbIter[T]) CopyFrom 

func (it *RbIter[T]) CopyFrom(other *RbIter[T]) (T, bool)

func (*RbIter[T]) Current 

func (it *RbIter[T]) Current() (T, bool)

func (*RbIter[T]) Find 

func (it *RbIter[T]) Find(item T) (T, bool)

func (*RbIter[T]) First 

func (it *RbIter[T]) First() (T, bool)

func (*RbIter[T]) HookWith 

func (it *RbIter[T]) HookWith(tree *RbTree[T]) *RbIter[T]

func (*RbIter[T]) Insert 

func (it *RbIter[T]) Insert(item T) (*T, bool)

func (*RbIter[T]) Last 

func (it *RbIter[T]) Last() (T, bool)

func (*RbIter[T]) Next 

func (it *RbIter[T]) Next() (T, bool)

func (*RbIter[T]) Prev 

func (it *RbIter[T]) Prev() (T, bool)

func (*RbIter[T]) Replace 

func (it *RbIter[T]) Replace(new T) (T, bool)

Replace replaces the current item. Don't change the key part of item.

type RbTree 

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

func NewRbTree 

func NewRbTree[T cmp.Ordered]() *RbTree[T]

NewRbTree creates a new Red-Black tree for cmp.Ordered types (int, string, float64, etc.)

func NewRbTreeFunc 

func NewRbTreeFunc[T any](cmpFn Compare[T]) *RbTree[T]

NewRbTreeFunc creates a new Red-Black tree with a custom comparison function.

func (*RbTree[T]) All 

func (t *RbTree[T]) All() iter.Seq[T]

All returns a forward iterator for use with range-over-function.

func (*RbTree[T]) Backward 

func (t *RbTree[T]) Backward() iter.Seq[T]

Backward returns a reverse iterator for use with range-over-function.

func (*RbTree[T]) Copy 

func (t *RbTree[T]) Copy() *RbTree[T]

func (*RbTree[T]) Count 

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

func (*RbTree[T]) Delete 

func (t *RbTree[T]) Delete(item T) (T, bool)

Delete deletes item from tree. Returns the deleted item and true if found, zero value and false otherwise.

func (*RbTree[T]) Find 

func (t *RbTree[T]) Find(target T) (T, bool)

Find searches for target in tree. Returns the item and true if found, zero value and false otherwise.

func (*RbTree[T]) Insert 

func (t *RbTree[T]) Insert(item T) bool

Insert inserts item in tree. Returns true if item was successfully inserted, false if item already in tree.

func (*RbTree[T]) Iter 

func (t *RbTree[T]) Iter() *RbIter[T]

func (*RbTree[T]) Replace 

func (t *RbTree[T]) Replace(item T) (T, bool)

Replace replaces item in tree with same key. Returns the old item and true if replaced, zero value and false otherwise.

type SymTab 

type SymTab[T any] interface {
	Count() int
	Find(target T) (T, bool)
	Insert(item T) bool
	Replace(item T) (T, bool)
	Delete(item T) (T, bool)
	Iter() Iterator[T]
	All() iter.Seq[T]
	Backward() iter.Seq[T]
}

SymTab is a symbol table (ordered map) interface.

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.