A Left-Leaning Red-Black (LLRB) implementation of balanced binary search trees for Google Go

Overview

GoLLRB

GoLLRB is a Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees in Go Language.

Overview

As of this writing and to the best of the author's knowledge, Go still does not have a balanced binary search tree (BBST) data structure. These data structures are quite useful in a variety of cases. A BBST maintains elements in sorted order under dynamic updates (inserts and deletes) and can support various order-specific queries. Furthermore, in practice one often implements other common data structures like Priority Queues, using BBST's.

2-3 trees (a type of BBST's), as well as the runtime-similar 2-3-4 trees, are the de facto standard BBST algoritms found in implementations of Python, Java, and other libraries. The LLRB method of implementing 2-3 trees is a recent improvement over the traditional implementation. The LLRB approach was discovered relatively recently (in 2008) by Robert Sedgewick of Princeton University.

GoLLRB is a Go implementation of LLRB 2-3 trees.

Maturity

GoLLRB has been used in some pretty heavy-weight machine learning tasks over many gigabytes of data. I consider it to be in stable, perhaps even production, shape. There are no known bugs.

Installation

With a healthy Go Language installed, simply run go get github.com/petar/GoLLRB/llrb

Example

package main

import (
	"fmt"
	"github.com/petar/GoLLRB/llrb"
)

func lessInt(a, b interface{}) bool { return a.(int) < b.(int) }

func main() {
	tree := llrb.New(lessInt)
	tree.ReplaceOrInsert(1)
	tree.ReplaceOrInsert(2)
	tree.ReplaceOrInsert(3)
	tree.ReplaceOrInsert(4)
	tree.DeleteMin()
	tree.Delete(4)
	c := tree.IterAscend()
	for {
		u := <-c
		if u == nil {
			break
		}
		fmt.Printf("%d\n", int(u.(int)))
	}
}

About

GoLLRB was written by Petar Maymounkov.

Follow me on Twitter @maymounkov!

Comments
  • Added iterator functions without channels and goroutines.

    Added iterator functions without channels and goroutines.

    Since I want to wrap this tree in sync.RWMutex and use in a thread safe way, I would much prefer the submitted form of iterators. Would it be ok to accept that in your project, or should I stick with a fork?

    regards, //Martin

    opened by zond 5
  • serializing llrb with gob causes a runtime error: invalid memory address

    serializing llrb with gob causes a runtime error: invalid memory address

    Hi Petar,

    Thanks for writing this data structure.

    I was giving it a drive, and the following throws a runtime panic

    
        func lessString(a, b interface{}) bool {
                return a.(string) < b.(string)
        }
    
    
            iofile, err := os.OpenFile("testfile.gob", os.O_RDWR|os.O_CREATE, 0666)                    
            if err != nil {                                                                                   
                    panic("Could not find, or create file:  error code:" + err.String())       
            }                                                                                                 
            enc := gob.NewEncoder(iofile)                                                                     
            //dec := gob.NewDecoder(iofile)                                                                   
    
            tree := llrb.New(lessString)                                                                    
            tree.ReplaceOrInsert("alex")                                                                    
            errdecode := enc.Encode(tree)                                                                                                                       
            if errdecode != nil {                                                                             
                    fmt.Printf("decode error:%s", err.String())                                               
            }                                                                                                 
    
    

    However, if you simply encode another struct like this one

        type Test struct {
            Test string
        }
    

    everything works fine.

    opened by emaxerrno 4
  • Add basic copy-on-write implementation

    Add basic copy-on-write implementation

    This allows llrb to provide snapshotting (at the cost of reduced performance when in copy-on-write mode). No substantial performance impact on non-cow implementation.

    opened by riannucci 3
  • Code assumes root node has been set

    Code assumes root node has been set

    Throughout the LLRB code it is assumed the root node has been set. But there is no sensible way to create a root node for a new instance of LLRB.

    By the way, the example is out of date.

    opened by nlfiedler 1
  • as discussed in email

    as discussed in email

    Requires the ability to get out the root node and set the root node. The pointer to function in Tree cannot be encoded with gob, so I just always use Node. All the fields of Node must be visible externally so gob encoder/decoder can mess with them.

    opened by iansmith 1
  • Example Code does not compile

    Example Code does not compile

    The example code in Readme.md does not compile. I had to convert it to the following to get it to work:

    package main
    
    import (
        "fmt"
        "github.com/petar/GoLLRB/llrb"
    )
    
    type IntItem int
    
    func IntLess(p, q interface{}) bool {
        return p.(int) < q.(int)
    }
    
    
    func main() {
        tree := llrb.New(IntLess)
        tree.ReplaceOrInsert(1)
        tree.ReplaceOrInsert(2)
        tree.ReplaceOrInsert(3)
        tree.ReplaceOrInsert(4)
        tree.DeleteMin()
        tree.Delete(4)
        c := tree.IterAscend()
        for {
            u := <-c
            if u == nil {
                break
            }
            fmt.Printf("%d\n", u.(int))
        }
    }
    
    opened by mickh 1
  • panic at GoLLRB/llrb/llrb.go:426

    panic at GoLLRB/llrb/llrb.go:426

    for i := 0; i < 1000000; i++ { rid, _ := utils.RandInt(100000, 999999) cnt++ tree.InsertNoReplace(NewMatchRoom(rid)) }

    for i := 0; i < 1000000; i++ {
    	rid, _ := utils.RandInt(100000, 999999)
    	cnt++
    	tree.Delete(NewMatchRoom(rid))
    }
    
    opened by lovelly 0
  • Panic in Delete

    Panic in Delete

    I've ran into a case where the delete code path appears to panic within the llrb package:

    panic: runtime error: invalid memory address or nil pointer dereference [recovered]
    	panic: runtime error: invalid memory address or nil pointer dereference
    [signal SIGSEGV: segmentation violation code=0x2 addr=0x20 pc=0x100bc7b40]
    
    goroutine 7 [running]:
    testing.tRunner.func1.2({0x100d5dd60, 0x100f44d30})
    	/usr/local/go/src/testing/testing.go:1209 +0x258
    testing.tRunner.func1(0x1400008d040)
    	/usr/local/go/src/testing/testing.go:1212 +0x284
    panic({0x100d5dd60, 0x100f44d30})
    	/usr/local/go/src/runtime/panic.go:1038 +0x21c
    github.com/petar/GoLLRB/llrb.flip(...)
    	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:417
    github.com/petar/GoLLRB/llrb.moveRedRight(0x1400016fa40)
    	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:434 +0x30
    github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400016fa40, {0x100da86c0, 0x14000067f80})
    	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:361 +0x25c
    github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400017eea0, {0x100da86c0, 0x14000067f80})
    	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
    github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018a0c0, {0x100da86c0, 0x14000067f80})
    	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
    github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018bda0, {0x100da86c0, 0x14000067f80})
    	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
    github.com/petar/GoLLRB/llrb.(*LLRB).Delete(0x140001567f0, {0x100da86c0, 0x14000067f80})
    	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:328 +0x40
    

    It seems that moveRedRight requires both the left and right children to exist https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L432, but here only the right child is tested https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L359-L362?

    opened by achille-roussel 0
  • Example docs became invalid

    Example docs became invalid

    Here you broke compatibly by removing comparator function from New

    https://github.com/petar/GoLLRB/commit/c08868e5ed436ed0ffd5125d2c952ef973f9c25a#diff-b47232007a3b6586df5152791ce99805

    opened by msinev 0
Releases(1.1.5)
Owner
Petar Maymounkov
Co-author of Kademlia, gocircuit.org and escher.io. Interested in languages for Mathematics. Rock climber, mountaineer, ashtangi.
Petar Maymounkov
A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees

radixs A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees. This implemen

Bruno Moura 0 Feb 14, 2022
Golang implementation of Radix trees

go-radix Provides the radix package that implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

Armon Dadgar 768 Dec 30, 2022
A go implementation of Verkle trees

go-verkle A very experimental implementation of Verkle trees. When production-ready, the code is to be split between go-kzg and go-ethereum. Notes Nod

Guillaume Ballet 106 Jan 8, 2023
Adaptive Radix Trees implemented in Go

An Adaptive Radix Tree Implementation in Go This library provides a Go implementation of the Adaptive Radix Tree (ART). Features: Lookup performance s

Pavel Larkin 252 Dec 30, 2022
Generic types that are missing from Go, including sets, trees, sorted lists, etc.

go-typ Generic types that are missing from Go, including sets, trees, sorted lists, etc. All code is implemented with 0 dependencies and in pure Go co

null 16 Dec 4, 2022
A generic Go library for implementations of tries (radix trees), state commitments and proofs of inclusion

trie.go Go library for implementations of tries (radix trees), state commitments and proof of inclusion for large data sets. It implements a generic 2

IOTA 5 Aug 3, 2022
Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

sarp dağ demirel 52 Oct 7, 2022
An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

A.Samet İleri 15 Jul 1, 2022
A binary stream packer and unpacker

binpacker A binary packer and unpacker. Install go get github.com/zhuangsirui/binpacker Examples Packer buffer := new(bytes.Buffer) packer := binpacke

Zhuang Sirui 200 Dec 1, 2022
Simple dense bitmap index in Go with binary operators

This package contains a bitmap index which is backed by uint64 slice, easily encodable to/from a []byte without copying memory around so it can be present in both disk and memory. As opposed to something as roaring bitmaps, this is a simple implementation designed to be used for small to medium dense collections.

Roman Atachiants 188 Jan 3, 2023
Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Arthur Abeilice 0 May 17, 2022
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

web_developer 1 Oct 9, 2021
A project that deals with implementations of a binary tree

Binary Search Tree This is a project that deals with implementations of a binary tree and the following functions. Print Prints the entire tree. Argum

Victor Zeddys 1 Nov 1, 2021
A slice backed binary heap with support for generic type parameters.

go-binaryheap A slice backed binary heap where the order can be customized by a comparison function. The main branch now requires go 1.18 because the

null 3 Jun 13, 2022
LeetCode in Go with the code style strictly follows the Google Golang Style Guide

LeetCode in Go LeetCode Online Judge is a website containing many algorithm questions. Most of them are real interview questions of Google, Facebook,

null 0 Nov 13, 2021
Go implementation of Count-Min-Log

Count-Min-Log Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier TL;DR: Count-Min-Log Sketch

Seif Lotfy 59 Jan 4, 2023
A Go implementation of the Elias-Fano encoding

go-ef A Go implementation of the Elias-Fano encoding Example package main import ( "fmt" "github.com/amallia/go-ef" "os" ) func main() {

Antonio Mallia 27 Nov 23, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 50 Sep 26, 2022