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.
Owner
Yasushi Saito
Similar Resources
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
Related tags
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