treap: Index | Files

package treap

import ""

The treap package provides a balanced binary tree datastructure, expected to have logarithmic height.


Package Files


type Item Uses

type Item interface{}

Item can be anything.

type Key Uses

type Key interface{}

Key can be anything. It will use LessFunc to compare keys.

type LessFunc Uses

type LessFunc func(a, b interface{}) bool

LessFunc returns true if a < b

type Node Uses

type Node struct {
    // contains filtered or unexported fields

A Node in the Tree.

type OverlapFunc Uses

type OverlapFunc func(a, b interface{}) bool

OverlapFunc return true if a overlaps b. Optional. Only used by overlap trees.

type Tree Uses

type Tree struct {
    // contains filtered or unexported fields

A Tree is the data structure that stores everything

func NewOverlapTree Uses

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 Uses

func NewTree(lessfn LessFunc) *Tree

To create a Tree, you need to supply a LessFunc that can compare the keys in the Node.

func (*Tree) Delete Uses

func (t *Tree) Delete(key Key)

Delete the item from the tree that has this key.

func (*Tree) Exists Uses

func (t *Tree) Exists(key Key) bool

Returns true if there is an item in the tree with this key.

func (*Tree) Get Uses

func (t *Tree) Get(key Key) Item

Get an Item in the tree.

func (*Tree) Height Uses

func (t *Tree) Height(key Key) int

Returns the height (depth) of the tree.

func (*Tree) Insert Uses

func (t *Tree) Insert(key Key, item Item)

Insert an item into the tree.

func (*Tree) IterAscend Uses

func (t *Tree) IterAscend() <-chan Item

Returns a channel of Items whose keys are in ascending order.

func (*Tree) IterKeysAscend Uses

func (t *Tree) IterKeysAscend() <-chan Key

Returns a channel of keys in ascending order.

func (*Tree) IterateOverlap Uses

func (t *Tree) IterateOverlap(key Key) <-chan Item

Returns a channel of items that overlap key.

func (*Tree) Len Uses

func (t *Tree) Len() int

The length of the tree (number of nodes).

func (*Tree) Max Uses

func (t *Tree) Max() Item

Returns the maximum item in the tree.

func (*Tree) Merge Uses

func (t *Tree) Merge(left, right *Node) *Node

Merge two trees together by supplying the root node of each tree.

func (*Tree) Min Uses

func (t *Tree) Min() Item

Returns the minimum item in the tree.

func (*Tree) Reset Uses

func (t *Tree) Reset()

Remove everything from the tree.

func (*Tree) Split Uses

func (t *Tree) Split(key Key) (*Node, *Node)

Split the tree by creating a tree with a node of priority -1 so it will be the root

Package treap imports 2 packages (graph). Updated 2018-02-12. Refresh now. Tools for package owners.