README
¶
treap
This Go package provides a balanced binary search tree data structure, expected to have logarithmic height.
This is for go version 1.0.
For more on treaps, check out the following links:
This implementation borrows a lot of ideas from GoLLRB by Petar Maymounkov.
Status
This package was extracted from production code powering StatHat, so clearly we feel that it is production-ready, but it should still be considered experimental as other uses of it could reveal issues we aren't experiencing.
Contact us
We'd love to hear from you if you are using this in your projects! Please drop us a line: @stathat or contact us here.
About
Documentation
¶
Overview ¶
The treap package provides a balanced binary tree datastructure, expected to have logarithmic height.
Index ¶
- type Item
- type Key
- type LessFunc
- type Node
- type OverlapFunc
- type Tree
- func (t *Tree) Delete(key Key)
- func (t *Tree) Exists(key Key) bool
- func (t *Tree) Get(key Key) Item
- func (t *Tree) Height(key Key) int
- func (t *Tree) Insert(key Key, item Item)
- func (t *Tree) IterAscend() <-chan Item
- func (t *Tree) IterKeysAscend() <-chan Key
- func (t *Tree) IterateOverlap(key Key) <-chan Item
- func (t *Tree) Len() int
- func (t *Tree) Max() Item
- func (t *Tree) Merge(left, right *Node) *Node
- func (t *Tree) Min() Item
- func (t *Tree) Reset()
- func (t *Tree) Split(key Key) (*Node, *Node)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type OverlapFunc ¶
type OverlapFunc func(a, b interface{}) bool
OverlapFunc return true if a overlaps b. Optional. Only used by overlap trees.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
A Tree is the data structure that stores everything
func NewOverlapTree ¶
func NewOverlapTree(lessfn LessFunc, overfn OverlapFunc) *Tree
To create a tree that also lets you iterate by key overlap, supply a LessFunc and an OverlapFunc
func NewTree ¶
To create a Tree, you need to supply a LessFunc that can compare the keys in the Node.
func (*Tree) IterAscend ¶
Returns a channel of Items whose keys are in ascending order.
func (*Tree) IterKeysAscend ¶
Returns a channel of keys in ascending order.
func (*Tree) IterateOverlap ¶
Returns a channel of items that overlap key.
Source Files