pkg

Documentation

Overview

Package redblacktree implements a red-black tree.

Used by TreeSet and TreeMap.

Structure is not thread safe.

References: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

Index

• type Node
  • func (node *Node) String() string
• type Tree
  • func NewWith(comparator utils.Comparator) *Tree
  • func (tree *Tree) Clear()
  • func (tree *Tree) Empty() bool
  • func (tree *Tree) Get(key interface{}) (values []Value, found bool)
  • func (tree *Tree) Left() (key interface{}, values []Value)
  • func (tree *Tree) PopLeft() (key interface{}, values []Value)
  • func (tree *Tree) PopRight() (key interface{}, values []Value)
  • func (tree *Tree) Put(key interface{}, value Value)
  • func (tree *Tree) Remove(key interface{})
  • func (tree *Tree) Right() (key interface{}, values []Value)
  • func (tree *Tree) Size() int
  • func (tree *Tree) String() string
• type Value

Types

type Node

type Node struct {
	Key    interface{}
	Values []Value

	Left   *Node
	Right  *Node
	Parent *Node
	// contains filtered or unexported fields
}

Node is a single element within the tree

func (*Node) String

func (node *Node) String() string

type Tree

type Tree struct {
	Root *Node

	Comparator utils.Comparator
	// contains filtered or unexported fields
}

Tree holds elements of the red-black tree

func NewWith

func NewWith(comparator utils.Comparator) *Tree

NewWith instantiates a red-black tree with the custom comparator.

func (*Tree) Clear

func (tree *Tree) Clear()

Clear removes all nodes from the tree.

func (*Tree) Empty

func (tree *Tree) Empty() bool

Empty returns true if tree does not contain any nodes

func (*Tree) Get

func (tree *Tree) Get(key interface{}) (values []Value, found bool)

Get searches the node in the tree by key and returns its value or nil if key is not found in tree. Second return parameter is true if key was found, otherwise false. Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Left

func (tree *Tree) Left() (key interface{}, values []Value)

Left returns the left-most (min) node or nil if tree is empty.

func (*Tree) PopLeft

func (tree *Tree) PopLeft() (key interface{}, values []Value)

func (*Tree) PopRight

func (tree *Tree) PopRight() (key interface{}, values []Value)

func (*Tree) Put

func (tree *Tree) Put(key interface{}, value Value)

Put inserts node into the tree. Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Remove

func (tree *Tree) Remove(key interface{})

Remove remove the node from the tree by key. Key should adhere to the comparator's type assertion, otherwise method panics.

func (*Tree) Right

func (tree *Tree) Right() (key interface{}, values []Value)

Right returns the right-most (max) node or nil if tree is empty.

func (*Tree) Size

func (tree *Tree) Size() int

Size returns number of nodes in the tree.

func (*Tree) String

func (tree *Tree) String() string

String returns a string representation of container

type Value

type Value interface {
	ID() string
}