Code Monkey home page Code Monkey logo

gollrb's Introduction

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!

gollrb's People

Contributors

anschelsc avatar codelingobot avatar magicaltux avatar petar avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

gollrb's Issues

top down 2-3-4 mode does not correctly delete

Hi,

I noticed this because I've been writing an llrb, and on my own project I can't get deletion to test as correct when using top down 2-3-4 insertion (see post on golang-nuts).

I wanted to check my sanity (I've pored over the code so many times to see if I'm doing something stupid), so I inserted one of my failing deletion tests into GoLLRB and it gives equivalent behaviour (passes on bottom up 2-3 and fails catastrophically on top down 2-3-4).

func TestRandomInsertionDeletion(t *testing.T) {
    count, max := 100000, 1000
    tree := New(IntLess)
    for i := 0; i < count; i++ {
        if rand.Float64() < 0.5 {
            tree.ReplaceOrInsert(rand.Intn(max))
        }
        if rand.Float64() < 0.5 {
            tree.Delete(rand.Intn(max))
        }
    }
}

The test is obviously very vicious, but is fine with the standard 2-3 GoLLRB insertion mode.

Any ideas?

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.

Particular data sequence causes inconsistency & panic in llrb

I encountered a crash in a data processing app that makes use of GoLLRB.

panic: runtime error: invalid memory address or nil pointer dereference
at llrb/llrb.go:423 (moveRedLeft)

I found a particular sequence of data that causes the tree to become inconsistent and crash. I've attached a simple test program that reproduces the error.

Download the code file llrbcrash.go and run with:

go get github.com/petar/GoLLRB
go run llrbcrash.go

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?

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))
    }
}

please tag formal releases

Please consider assigning version numbers and tagging releases. Tags/releases
are useful for downstream package maintainers (in Debian and other distributions) to export source tarballs, automatically track new releases and to declare dependencies between packages. Read more in the Debian Upstream Guide.

Versioning provides additional benefits to encourage vendoring of a particular (e.g. latest stable) release contrary to random unreleased snapshots.

Versioning provides safety margin for situations like "ops, we've made a mistake but reverted problematic commit in master". Presumably tagged version/release is better tested/reviewed than random snapshot of "master" branch.

Thank you.

See also

Still active?

Hi, I'm looking to use this library for a production tool, and was wondering if it's still being actively maintained?

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))
}

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.

IterRange can never include the last (Max) element

I want to iterate from a given key to the end of the tree inclusively. But there seems to be no way to get the last (tree.Max()) value as part of that iteration. I don't know what the most elegant solution would be...

  • a bool param to IterRange that would change < @upper to <= @upper?
  • a new IterRangeInclusive that goes @lower <= E <= @upper?
  • telling me I should simply tack on tree.Max() when my IterRange chan returns a nil and I expect another element?

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.