rbtree

README

rbtree

Red-Black Tree Golang Implementation

Installation

go get -u -v github.com/monitor1379/rbtree

Example

package main

import (
	"fmt"

	"github.com/monitor1379/rbtree"
)

func main() {
	tree := rbtree.NewStringRBTree()

	tree.Put("name", "monitor1379")
	tree.Put("age", 25)

	name, ok := tree.Get("name")
	fmt.Println(name, ok)
	// print: monitor1379 true

	tree.Remove("age")

	age, ok := tree.Get("age")
	fmt.Println(age, ok)
	// print: <nil> false

}

You can create a rbtree object by:

rbtree.NewIntRBTree()
rbtree.NewStringRBTree()
rbtree.NewRBTree(rbtree.Comparator)

Note that rbtree.Comparator is a type of interface{}:

// Comparetor.Compare returns an integer comparing two object lexicographically.
// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
//
type Comparator interface {
	Compare(interface{}, interface{}) int
}

Such as:

type IntComparator struct{}

func (c *IntComparator) Compare(i, j interface{}) int {
	ii, ok := i.(int)
	if !ok {
		panic(ErrInvalidInputTypeOfComparator)
	}

	jj, ok := j.(int)
	if !ok {
		panic(ErrInvalidInputTypeOfComparator)
	}

	if ii < jj {
		return -1
	} else if ii == jj {
		return 0
	}
	return 1
}

Benchmark

Platform:

goos: linux
goarch: amd64
pkg: github.com/monitor1379/rbtree

Run benchmark testing:

cd $GOPATH/src/github.com/monitor1379/rbtree
go test -v -bench=. -run=none .

RBTree:

BenchmarkRBTreeRandomInsert-8                    1000000              1280 ns/op
BenchmarkRBTreeRandomInsertAndSearch-8           1000000              1092 ns/op
BenchmarkRBTreeRandomDelete-8                    1000000              1189 ns/op

Binary-Search Tree:

BenchmarkBSTreeRandomInsert-8                    1000000              1491 ns/op
BenchmarkBSTreeWorstInsert-8                       50000            126385 ns/op

GODS library:

BenchmarkGodsRBTreeRandomInsert-8                1000000              1260 ns/op
BenchmarkGodsRBTreeRandomInsertAndSearch-8       1000000              1118 ns/op

Golang builtin map:

BenchmarkMapInsert-8                             3000000               500 ns/op
BenchmarkMapRandomInsertAndSearch-8             10000000               168 ns/op

Documentation

Index

• Variables
• type BSTree
  • func NewBSTree(comparator Comparator) *BSTree
  • func NewIntBSTree() *BSTree
  • func NewStringBSTree() *BSTree
  • func (t *BSTree) InsertOrReplace(key interface{}, value interface{})
  • func (t *BSTree) PrettyString() string
  • func (t *BSTree) Search(key interface{}) (interface{}, bool)
  • func (t *BSTree) SearchInsertPosition(key interface{}) (*Node, *Node, int)
  • func (t *BSTree) Size() int
• type Color
• type Comparator
• type IntComparator
  • func (c *IntComparator) Compare(i, j interface{}) int
• type Node
  • func (c *Node) GetGrandparent() *Node
  • func (c *Node) GetSibling() *Node
  • func (c *Node) GetUncle() *Node
• type RBTree
  • func NewIntRBTree() *RBTree
  • func NewRBTree(comparator Comparator) *RBTree
  • func NewStringRBTree() *RBTree
  • func (t *RBTree) Delete(key interface{})
  • func (t *RBTree) Get(key interface{}) (interface{}, bool)
  • func (t *RBTree) InsertOrReplace(key interface{}, value interface{})
  • func (t *RBTree) Put(key interface{}, value interface{})
  • func (t *RBTree) Remove(key interface{})
• type StringComparator
  • func (c *StringComparator) Compare(i, j interface{}) int

Variables

var (
	ErrInvalidInputTypeOfComparator = errors.New("invalid input type of comparator")
)

Types

type BSTree

type BSTree struct {
	// contains filtered or unexported fields
}

BSTree is Binary Search Tree

func NewBSTree

func NewBSTree(comparator Comparator) *BSTree

func NewIntBSTree

func NewIntBSTree() *BSTree

func NewStringBSTree

func NewStringBSTree() *BSTree

func (*BSTree) InsertOrReplace

func (t *BSTree) InsertOrReplace(key interface{}, value interface{})

func (*BSTree) PrettyString

func (t *BSTree) PrettyString() string

func (*BSTree) Search

func (t *BSTree) Search(key interface{}) (interface{}, bool)

func (*BSTree) SearchInsertPosition

func (t *BSTree) SearchInsertPosition(key interface{}) (*Node, *Node, int)

func (*BSTree) Size

func (t *BSTree) Size() int

type Color

type Color int

var (
	ColorRed   Color = 0
	ColorBlack Color = 1
)

type Comparator

type Comparator interface {
	Compare(interface{}, interface{}) int
}

Comparetor.Compare returns an integer comparing two object lexicographically. The result will be 0 if a==b, -1 if a < b, and +1 if a > b.

type IntComparator

type IntComparator struct{}

func (*IntComparator) Compare

func (c *IntComparator) Compare(i, j interface{}) int

type Node

type Node struct {
	Key    interface{}
	Value  interface{}
	Color  Color
	Parent *Node
	Left   *Node
	Right  *Node
}

func (*Node) GetGrandparent

func (c *Node) GetGrandparent() *Node

func (*Node) GetSibling

func (c *Node) GetSibling() *Node

func (*Node) GetUncle

func (c *Node) GetUncle() *Node

type RBTree

type RBTree struct {
	*BSTree
}

func NewIntRBTree

func NewIntRBTree() *RBTree

func NewRBTree

func NewRBTree(comparator Comparator) *RBTree

func NewStringRBTree

func NewStringRBTree() *RBTree

func (*RBTree) Delete

func (t *RBTree) Delete(key interface{})

func (*RBTree) Get

func (t *RBTree) Get(key interface{}) (interface{}, bool)

func (*RBTree) InsertOrReplace

func (t *RBTree) InsertOrReplace(key interface{}, value interface{})

func (*RBTree) Put

func (t *RBTree) Put(key interface{}, value interface{})

func (*RBTree) Remove

func (t *RBTree) Remove(key interface{})

type StringComparator

type StringComparator struct{}

func (*StringComparator) Compare

func (c *StringComparator) Compare(i, j interface{}) int