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
}

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

func (*Tree) Floor

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

func (*Tree) Put

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

func (*Tree) Remove

func (t *Tree) Remove(key Key)

func (*Tree) String

func (t *Tree) String() string

type Value

type Value interface {
	String() string
}