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

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

##### Overview

##### 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

###### 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

###### 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

###### 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

###### 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

###### 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

###### 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

###### 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

###### 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

###### 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

###### 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