rbtree

README

Rbtree

This is an implementation of Red-Black tree written by Golang and 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
}

Documentation

Overview

Package rbtree implements operations on Red-Black tree.

Index

• Constants
• type Int
  • func (x Int) Less(than Item) bool
• type Item
• type Iterator
• type Node
• type Rbtree
  • func New() *Rbtree
  • func (t *Rbtree) Ascend(pivot Item, iterator Iterator)
  • func (t *Rbtree) AscendRange(ge, lt Item, iterator Iterator)
  • func (t *Rbtree) Delete(item Item) Item
  • func (t *Rbtree) Descend(pivot Item, iterator Iterator)
  • func (t *Rbtree) Get(item Item) Item
  • func (t *Rbtree) Init() *Rbtree
  • func (t *Rbtree) Insert(item Item)
  • func (t *Rbtree) InsertOrGet(item Item) Item
  • func (t *Rbtree) Len() uint
  • func (t *Rbtree) Max() Item
  • func (t *Rbtree) Min() Item
  • func (t *Rbtree) Search(item Item) *Node
• type String
  • func (x String) Less(than Item) bool

Constants

const (
	// RED represents the color of the node is red
	RED = 0
	// BLACK represents the color of the node is black
	BLACK = 1
)

Types

type Int

type Int int

Int is type of int

func (Int) Less

func (x Int) Less(than Item) bool

Less returns whether x(Int) is smaller than specified item

type Item

type Item interface {
	Less(than Item) bool
}

Item has a method to compare items which is less

type Iterator

type Iterator func(i Item) bool

Iterator is the function of iteration entity which would be used by those functions like `Ascend`, `Dscend`, etc.

A typical Iterator with Print :

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

type Node

type Node struct {
	Left   *Node
	Right  *Node
	Parent *Node
	Color  uint

	// for use by client.
	Item
}

Node of the rbtree has a pointer of the node of parent, left, right, also has own color and Item which client uses

type Rbtree

type Rbtree struct {
	NIL *Node
	// contains filtered or unexported fields
}

Rbtree represents a Red-Black tree.

func New

func New() *Rbtree

New returns an initialized Red-Black tree

func (*Rbtree) Ascend

func (t *Rbtree) Ascend(pivot Item, iterator Iterator)

Ascend will call iterator once for each element greater or equal than pivot in ascending order. It will stop whenever the iterator returns false.

func (*Rbtree) AscendRange

func (t *Rbtree) AscendRange(ge, lt Item, iterator Iterator)

AscendRange will call iterator once for elements greater or equal than @ge and less than @lt, which means the range would be [ge, lt). It will stop whenever the iterator returns false.

func (*Rbtree) Delete

func (t *Rbtree) Delete(item Item) Item

Delete delete the item in the tree

func (*Rbtree) Descend

func (t *Rbtree) Descend(pivot Item, iterator Iterator)

Descend will call iterator once for each element less or equal than pivot in descending order. It will stop whenever the iterator returns false.

func (*Rbtree) Get

func (t *Rbtree) Get(item Item) Item

Get search for the specified items which is carried by a Node

func (*Rbtree) Init

func (t *Rbtree) Init() *Rbtree

Init returns the initial of rbtree

func (*Rbtree) Insert

func (t *Rbtree) Insert(item Item)

Insert func inserts a item as a new RED node

func (*Rbtree) InsertOrGet

func (t *Rbtree) InsertOrGet(item Item) Item

InsertOrGet inserts or retrieves the item in the tree. If the item is already in the tree then the return value will be that. If the item is not in the tree the return value will be the item you put in.

func (*Rbtree) Len

func (t *Rbtree) Len() uint

Len returns number of nodes in the tree.

func (*Rbtree) Max

func (t *Rbtree) Max() Item

Max return the item maxmum one

func (*Rbtree) Min

func (t *Rbtree) Min() Item

Min return the item minimum one

func (*Rbtree) Search

func (t *Rbtree) Search(item Item) *Node

Search does only search the node which includes it node TODO: This is for debug, delete it in the future

type String

type String string

String is type of string

func (String) Less

func (x String) Less(than Item) bool

Less returns whether x(String) is smaller than specified item