rbtree

Golang red-black tree.

Nice visualization

Types

It uses a comparable type as a key and any type as a value.

Methods

Method name	Time
Set	O(log2n)
SetNx	O(log2n)
Del	O(log2n)
Get	O(log2n)
GetEx	O(log2n)
IsExist	O(log2n)
Len	O(1)
Move	O(2log2n)
Max	O(log2n)
Min	O(log2n)
Empty	O(1)
Walk	O(log2n + m)
Slice	O(log2n + m)

Memory usage

O(n×node),

where

node = 3*sizeof(uintptr) +
          sizeof(Key) +
          sizeof(bool) +
          sizeof(Value) // data

Install

Get or update

go get -u github.com/logrusorgru/rbtree

Test

go test -cover -race github.com/logrusorgru/rbtree

Run benchmark

expensive

go test -timeout=30m -test.bench . github.com/logrusorgru/rbtree

limited

go test -test.benchtime=0.1s -test.bench . github.com/logrusorgru/rbtree

Usage

package main

import (
	"fmt"

	"github.com/logrusorgru/rbtree"
)

func main() {
	// create new red-black tree
	var tr = rbtree.New[int, string]()

	// append value to tree
	tr.Set(0, "zero")
	tr.Set(12, "some value")
	var t int = 98
	tr.Set(t, "don't forget about int indexing")
	tr.Set(199, "rbtree distributed under Unlicense, feel free to fork it")
	tr.Set(2, "trash")

	// delete value from tree
	tr.Del(2)

	// get it
	fmt.Println(tr.Get(2))
	fmt.Println(tr.Get(t))

	// check existence only
	fmt.Println(tr.IsExist(12))
	fmt.Println(tr.IsExist(590))

	// get count
	fmt.Println(tr.Len())

	// change index of value
	tr.Move(12, 13)
	fmt.Println(tr.Get(13))
	fmt.Println(tr.IsExist(12))

	// take min index and value
	fmt.Println(tr.Min())

	// max
	fmt.Println(tr.Max())

	// empty
	tr.Empty()
	fmt.Println(tr.Len())
	fmt.Println(tr.Min())
	fmt.Println(tr.Max())
	fmt.Println(tr.Get(0))
}

See also

If you want to lookup the tree much more than change it, take a look at LLRB (if memory usage are critical) (read | source)

Licensing

Copyright © 2016-2022 Konstantin Ivanov. This work is free. It comes without any warranty, to the extent permitted by applicable law. You can redistribute it and/or modify it under the terms of the the Unlicense. See the LICENSE file for more details.