rbtree

Documentation

Index

• type NodeType
  • func (n NodeType) IsBlack() bool
  • func (n NodeType) IsRed() bool
  • func (n NodeType) String() string
• type RBNode
• type RBTree
  • func NewRBTree() *RBTree
  • func (t *RBTree) Delete(key int) bool
  • func (t *RBTree) Insert(key int, value string) bool
  • func (t *RBTree) LookupNUniqueAt(n int, key int) []string
  • func (t *RBTree) Root() *RBNode
  • func (t *RBTree) Search(key int) (string, bool)
  • func (t *RBTree) Size() int
  • func (t *RBTree) String() string

Types

type NodeType

type NodeType int

NodeType describes which type the node represents

const (
	// Red represents a red type of the RBTree
	Red NodeType = iota

	// Black represents a black type of the RBTree
	Black
)

func (NodeType) IsBlack

func (n NodeType) IsBlack() bool

IsBlack returns if the NodeType is Black

func (NodeType) IsRed

func (n NodeType) IsRed() bool

IsRed returns if the NodeType is Red

func (NodeType) String

func (n NodeType) String() string

type RBNode

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

RBNode is a RBTree node

type RBTree

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

RBTree implements a non-thread safe fixed size Red, Black tree

func NewRBTree

func NewRBTree() *RBTree

NewRBTree creates a new RBTree

func (*RBTree) Delete

func (t *RBTree) Delete(key int) bool

Delete removes the entry for key from the redBlackTree. Returns true on successful deletion, false if the key is not in tree

func (*RBTree) Insert

func (t *RBTree) Insert(key int, value string) bool

Insert inserts a value and string into the tree Returns true on insertion and false if a duplicate exists

func (*RBTree) LookupNUniqueAt

func (t *RBTree) LookupNUniqueAt(n int, key int) []string

LookupNUniqueAt iterates through the tree from the last node that is smaller than key or equal, and returns the next n unique values.

func (*RBTree) Root

func (t *RBTree) Root() *RBNode

Root returns the root node within the tree

func (*RBTree) Search

func (t *RBTree) Search(key int) (string, bool)

Search searches for a value in the redBlackTree, returns the string and true if found or the empty string and false if val is not in the tree.

func (*RBTree) Size

func (t *RBTree) Size() int

Size returns the number of nodes

func (*RBTree) String

func (t *RBTree) String() string