llrb

Documentation

Overview

Package llrb provides a Left-leaning Red-Black tree implementation.

Index

• type Key
• type Node
  • func NewNode[K Key, V Value](key K, value V, isRed bool) *Node[K, V]
• type Tree
  • func NewTree[K Key, V Value]() *Tree[K, V]
  • func (t *Tree[K, V]) Floor(key K) (K, V)
  • func (t *Tree[K, V]) Len() int
  • 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

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

Node is a node of Tree.

func NewNode

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

NewNode creates a new instance of Node.

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

func NewTree[K Key, V Value]() *Tree[K, V]

NewTree creates a new instance of Tree.

func (*Tree[K, V]) Floor

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

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

func (*Tree[K, V]) Len

func (t *Tree[K, V]) Len() int

Len returns the length of the tree.

func (*Tree[K, V]) Put

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

Put puts the value of the given key.

func (*Tree[K, V]) Remove

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

Remove removes the value of the given key.

func (*Tree[K, V]) String

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

type Value

type Value interface {
	String() string
}

Value represents the data stored in the nodes of Tree.