llrb

Documentation

Index

• type Key
• type Node
  • func NewNode(key Key, value Value, isRed bool) *Node
• type Tree
  • func NewTree() *Tree
  • func (t *Tree) Floor(key Key) (Key, Value)
  • func (t *Tree) Put(k Key, v Value) Value
  • func (t *Tree) Remove(key Key)
  • func (t *Tree) String() string
• type Value

Types

type Key

type Key interface {
	// Compare gives the result of a 3-way comparison
	// a.Compare(b) = 1 => a > b
	// a.Compare(b) = 0 => a == b
	// a.Compare(b) = -1 => a < b
	Compare(k Key) int
}

Key represents key of Tree.

type Node

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

Node is a node of Tree.

func NewNode

func NewNode(key Key, value Value, isRed bool) *Node

NewNode creates a new instance of Node.

type Tree

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

Tree is an implementation of Left-learning Red-Black Tree. Original paper on Left-leaning Red-Black Trees:

• http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

Invariant 1: No red node has a red child Invariant 2: Every leaf path has the same number of black nodes Invariant 3: Only the left child can be red (left leaning)

func NewTree

func NewTree() *Tree

NewTree creates a new instance of Tree.

func (*Tree) Floor

func (t *Tree) Floor(key Key) (Key, Value)

Floor returns the greatest key less than or equal to the given key.

func (*Tree) Put

func (t *Tree) Put(k Key, v Value) Value

Put puts the value of the given key.

func (*Tree) Remove

func (t *Tree) Remove(key Key)

Remove removes the value of the given key.

func (*Tree) String

func (t *Tree) String() string

type Value

type Value interface {
	String() string
}

Value represents the data stored in the nodes of Tree.