zhoubowen-sky/rbtree

Rbtree

This is an implementation of Red-Black tree written by Golang which does not support duplicate keys.

Installation

With a healthy Go language installed, simply run go get github.com/HuKeping/rbtree

Example

All you have to do is to implement a comparison function Less() bool for your Item which will be store in the Red-Black tree, here are some examples.

A simple case for int items.

package main

import (
	"fmt"
	"github.com/HuKeping/rbtree"
)

func main() {
	rbt := rbtree.New()

	m := 0
	n := 10

	for m < n {
		rbt.Insert(rbtree.Int(m))
		m++
	}

	m = 0
	for m < n {
		if m%2 == 0 {
			rbt.Delete(rbtree.Int(m))
		}
		m++
	}

	// 1, 3, 5, 7, 9 were expected.
	rbt.Ascend(rbt.Min(), Print)
}

func Print(item rbtree.Item) bool {
	i, ok := item.(rbtree.Int)
	if !ok {
		return false
	}
	fmt.Println(i)
	return true
}

A simple case for string items.

package main

import (
	"fmt"
	"github.com/HuKeping/rbtree"
)

func main() {
	rbt := rbtree.New()

	rbt.Insert(rbtree.String("Hello"))
	rbt.Insert(rbtree.String("World"))

	rbt.Ascend(rbt.Min(), Print)
}

func Print(item rbtree.Item) bool {
	i, ok := item.(rbtree.String)
	if !ok {
		return false
	}
	fmt.Println(i)
	return true
}

A quite interesting case for struct items.

package main

import (
	"fmt"
	"github.com/HuKeping/rbtree"
	"time"
)

type Var struct {
	Expiry time.Time `json:"expiry,omitempty"`
	ID     string    `json:"id",omitempty`
}

// We will order the node by `Time`
func (x Var) Less(than rbtree.Item) bool {
	return x.Expiry.Before(than.(Var).Expiry)
}

func main() {
	rbt := rbtree.New()

	var1 := Var{
		Expiry: time.Now().Add(time.Second * 10),
		ID:     "var1",
	}
	var2 := Var{
		Expiry: time.Now().Add(time.Second * 20),
		ID:     "var2",
	}
	var3 := Var{
		Expiry: var2.Expiry,
		ID:     "var2-dup",
	}
	var4 := Var{
		Expiry: time.Now().Add(time.Second * 40),
		ID:     "var4",
	}
	var5 := Var{
		Expiry: time.Now().Add(time.Second * 50),
		ID:     "var5",
	}

	rbt.Insert(var1)
	rbt.Insert(var2)
	rbt.Insert(var3)
	rbt.Insert(var4)
	rbt.Insert(var5)

	tmp := Var{
		Expiry: var4.Expiry,
		ID:     "This field is not the key factor",
	}

	// var4 and var5 were expected
	rbt.Ascend(rbt.Get(tmp), Print)
}

func Print(item rbtree.Item) bool {
	i, ok := item.(Var)
	if !ok {
		return false
	}
	fmt.Printf("%+v\n", i)
	return true
}