An yet-another red-black tree implementation, with a C++ STL-like API.

Overview
A red-black tree with an API similar to C++ STL's.

INSTALLATION
    go get github.com/yasushi-saito/rbtree

EXAMPLE

        More examples can be found in rbtree_test.go

        import "github.com/yasushi-saito/rbtree"

	type MyItem struct {
		key   int
		value string
	}

	tree := rbtree.NewTree(func(a, b Item) int { return a.(MyItem).key - b.(MyItem).key })
	tree.Insert(MyItem{10, "value10"})
	tree.Insert(MyItem{12, "value12"})

	fmt.Println("Get(10) ->", tree.Get(MyItem{10, ""}))
	fmt.Println("Get(11) ->", tree.Get(MyItem{11, ""}))

	// Find an element >= 11
	iter := tree.FindGE(MyItem{11, ""})
	fmt.Println("FindGE(11) ->", iter.Item())

	// Find an element >= 13
	iter = tree.FindGE(MyItem{13, ""})
	if !iter.End() { panic("There should be no element >= 13") }

	// Output:
	// Get(10) -> {10 value10}
	// Get(11) -> <nil>
	// FindGE(11) -> {12 value12}

TYPES

type CompareFunc func(a, b Item) int
    CompareFunc returns 0 if a==b, <0 if a<b, >0 if a>b.

type Item interface{}
    Item is the object stored in each tree node.

type Iterator struct {
    // contains filtered or unexported fields
}
    Iterator allows scanning tree elements in sort order.

    Iterator invalidation rule is the same as C++ std::map<>'s. That is, if
    you delete the element that an iterator points to, the iterator becomes
    invalid. For other operation types, the iterator remains valid.

func (iter Iterator) Equal(iter2 Iterator) bool

func (iter Iterator) Item() interface{}
    Return the current element.

    REQUIRES: !iter.Limit() && !iter.NegativeLimit()

func (iter Iterator) Limit() bool
    Check if the iterator points beyond the max element in the tree

func (iter Iterator) Max() bool
    Check if the iterator points to the maximum element in the tree

func (iter Iterator) Min() bool
    Check if the iterator points to the minimum element in the tree

func (iter Iterator) NegativeLimit() bool
    Check if the iterator points before the minumum element in the tree

func (iter Iterator) Next() Iterator
    Create a new iterator that points to the successor of the current
    element.

    REQUIRES: !iter.Limit()

func (iter Iterator) Prev() Iterator
    Create a new iterator that points to the predecessor of the current
    node.

    REQUIRES: !iter.NegativeLimit()

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

func NewTree(compare CompareFunc) *Tree
    Create a new empty tree.

func (root *Tree) DeleteWithIterator(iter Iterator)
    Delete the current item.

    REQUIRES: !iter.Limit() && !iter.NegativeLimit()

func (root *Tree) DeleteWithKey(key Item) bool
    Delete an item with the given key. Return true iff the item was found.

func (root *Tree) FindGE(key Item) Iterator
    Find the smallest element N such that N >= key, and return the iterator
    pointing to the element. If no such element is found, return
    root.Limit().

func (root *Tree) FindLE(key Item) Iterator
    Find the largest element N such that N <= key, and return the iterator
    pointing to the element. If no such element is found, return
    iter.NegativeLimit().

func (root *Tree) Get(key Item) Item
    A convenience function for finding an element equal to key. Return nil
    if not found.

func (root *Tree) Insert(item Item) bool
    Insert an item. If the item is already in the tree, do nothing and
    return false. Else return true.

func (root *Tree) Len() int
    Return the number of elements in the tree.

func (root *Tree) Limit() Iterator
    Create an iterator that points beyond the maximum item in the tree

func (root *Tree) Max() Iterator
    Create an iterator that points at the maximum item in the tree

    If the tree is empty, return NegativeLimit()

func (root *Tree) Min() Iterator
    Create an iterator that points to the minimum item in the tree If the
    tree is empty, return Limit()

func (root *Tree) NegativeLimit() Iterator
    Create an iterator that points before the minimum item in the tree


You might also like...
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

Go-merkle - Merkle tree implementation in Golang

go-merkle go-merkle implements a simple merkle tree in Golang. It allows to obta

A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees

radixs A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees. This implemen

An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

an R-Tree library for Go

rtreego A library for efficiently storing and querying spatial data in the Go programming language. About The R-tree is a popular data structure for e

Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Owner
Yasushi Saito
@luminarycloud
Yasushi Saito
Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

disksing 172 Nov 16, 2022
Data structure and algorithm library for go, designed to provide functions similar to C++ STL

GoSTL English | 简体中文 Introduction GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more p

stirlingx 747 Nov 24, 2022
Exp-tree: go library for parsing expression tree

Vinshop expression tree Exp-tree is go library for parsing expression tree Installation go get -u github.com/vinshop/exp-tree Quick start Format Expre

VinShop 6 May 11, 2022
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 19 Mar 17, 2022
publish a tree-like data structure from a backend to a front-end

tree-publish publish a tree-like data structure from a backend to a front-end. It needs to be a tree in order to publish the data as JSON document. If

Lutz Behnke 0 Dec 20, 2021
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Cameron Bergoon 399 Nov 26, 2022
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 31 Nov 3, 2022
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Josh Baker 235 Nov 27, 2022
An immutable radix tree implementation in Golang

go-immutable-radix Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimi

HashiCorp 850 Nov 24, 2022
B-tree implementation for Go

btree btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly do

Amit Davidson 211 Nov 13, 2022