llrb

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[K Key, V Value] struct {
	// contains filtered or unexported fields
}

Node is a node of Tree.

func NewNode[K Key, V Value](key K, value V, isRed bool) *Node[K, V]

type Tree ¶

type Tree[K Key, V Value] 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[K Key, V Value]() *Tree[K, V]

func (t *Tree[K, V]) Floor(key K) (K, V)

func (t *Tree[K, V]) Put(k K, v V) V

func (t *Tree[K, V]) Remove(key K)

func (t *Tree[K, V]) String() string

type Value ¶

type Value interface {
	String() string
}

Value represents the data stored in the nodes of Tree.