rbt

Documentation

Index

• Constants
• type DuplicateError
  • func NewDuplicateError(k interface{}) *DuplicateError
  • func (e *DuplicateError) Error() string
• type NilNodeError
  • func NewNilNodeError(k interface{}) *NilNodeError
  • func (e *NilNodeError) Error() string
• type Node
  • func NewNode(k, v interface{}, color int) *Node
• type NodeData
• type RBT
  • func NewWith(comparator utils.Comparator) *RBT
  • func NewWithIntComparator() *RBT
  • func NewWithStringComparator() *RBT
  • func (tree *RBT) BlackHeight() int
  • func (tree *RBT) Clear()
  • func (tree *RBT) Delete(key interface{}) (interface{}, error)
  • func (tree *RBT) DepthFirstTraversal()
  • func (tree *RBT) InOrderTraversal()
  • func (tree *RBT) Insert(key, value interface{}) (interface{}, error)
  • func (tree *RBT) IsBalanced() bool
  • func (tree *RBT) IsEmpty() bool
  • func (tree *RBT) ReturnNodeValue(key interface{}) (interface{}, error)
  • func (tree *RBT) Root() *Node
  • func (tree *RBT) Search(key interface{}) bool
  • func (tree *RBT) Size() int
  • func (tree *RBT) Update(key interface{}, value interface{}) (interface{}, error)

Constants

const BLACK = 0

const LEFT = 2

const RED = 1

const RIGHT = 3

Types

type DuplicateError

type DuplicateError struct {
	Key     interface{}
	Message string
}

func NewDuplicateError

func NewDuplicateError(k interface{}) *DuplicateError

func (*DuplicateError) Error

func (e *DuplicateError) Error() string

type NilNodeError

type NilNodeError struct {
	Key     interface{}
	Message string
}

func NewNilNodeError

func NewNilNodeError(k interface{}) *NilNodeError

func (*NilNodeError) Error

func (e *NilNodeError) Error() string

type Node

type Node struct {
	Data *NodeData
	// contains filtered or unexported fields
}

Node stores left, right, and parent Node pointers; the node's color, and NodeData, containing the key and the value the caller wishes to store.

func NewNode

func NewNode(k, v interface{}, color int) *Node

NewNode takes in a key and a value and returns a pointer to type Node. When creating a new node, the left and right children, as well as the parent node, are set to nil.

type NodeData

type NodeData struct {
	Key   interface{}
	Value interface{}
}

NodeData stores the key and the value of the Node.

type RBT

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

RBT stores the root Node of the tree, a key comparator, and the size of the tree. Duplicates are not allowed. Comparator format is taken from https://github.com/emirpasic/gods#comparator. Either import the package https://github.com/emirpasic/gods/utils and pass a comparator from the library, or write a custom comparator using guidelines from the gods README.

func NewWith

func NewWith(comparator utils.Comparator) *RBT

NewWith returns a pointer to a RBT where root is nil, size is 0, and the key comparator is set to the parameter passed in. The comparator format is taken from https://github.com/emirpasic/gods#comparator. Either import the package https://github.com/emirpasic/gods/utils and pass a comparator from the library, or write a custom comparator using guidelines from the gods README.

func NewWithIntComparator

func NewWithIntComparator() *RBT

NewWithIntComparator returns a pointer to a RBT where root is nil, size is 0, and the key comparator is set to the IntComparator from package https://github.com/emirpasic/gods/utils. the comparator format is taken from https://github.com/emirpasic/gods#comparator.

func NewWithStringComparator

func NewWithStringComparator() *RBT

NewWithStringComparator returns a pointer to a RBT where root is nil, size is 0, and the key comparator is set to the StringComparator from package https://github.com/emirpasic/gods/utils. the comparator format is taken from https://github.com/emirpasic/gods#comparator.

func (*RBT) BlackHeight

func (tree *RBT) BlackHeight() int

BlackHeight returns an int representing the black height of the tree.

func (*RBT) Clear

func (tree *RBT) Clear()

Clear sets the root node to nil and sets the size of the tree to 0.

func (*RBT) Delete

func (tree *RBT) Delete(key interface{}) (interface{}, error)

Delete takes a key, removes the node from the tree, and decrements the size of the tree. The function returns the key of the deleted node and an error, if there was one.

func (*RBT) DepthFirstTraversal

func (tree *RBT) DepthFirstTraversal()

DepthFirstTraversal (pre-order traversal) traverses the binary search tree by printing the root node, then recursively visiting the left and the right nodes of the current node.

func (*RBT) InOrderTraversal

func (tree *RBT) InOrderTraversal()

InOrderTraversal prints every node's value in order from smallest to greatest.

func (*RBT) Insert

func (tree *RBT) Insert(key, value interface{}) (interface{}, error)

Insert takes a key and a value of type interface, and inserts a new Node with that key and value. The function inserts by key; that is, the key of the new node is compared against current nodes to find the correct insertion point. The function returns the newly inserted node's key or an error, if there was one.

func (*RBT) IsBalanced

func (tree *RBT) IsBalanced() bool

IsBalanced returns a bool representing whether all paths from a node to its nil descendants contain the same number of black nodes.

func (*RBT) IsEmpty

func (tree *RBT) IsEmpty() bool

IsEmpty returns a boolean stating whether the tree is empty or not.

func (*RBT) ReturnNodeValue

func (tree *RBT) ReturnNodeValue(key interface{}) (interface{}, error)

ReturnNodeValue takes a key and returns the value associated with the key or an error, if there was one.

func (*RBT) Root

func (tree *RBT) Root() *Node

Root returns the root of the tree, a pointer to type Node.

func (*RBT) Search

func (tree *RBT) Search(key interface{}) bool

Search takes a key and searches for the key in the tree. The function returns a boolean, stating whether the key was found or not.

func (*RBT) Size

func (tree *RBT) Size() int

Size returns the size, or number of nodes in the tree, of the tree.

func (*RBT) Update

func (tree *RBT) Update(key interface{}, value interface{}) (interface{}, error)

Update takes a key and a value and updates a node with the existing key with the new value. Returns the new value of the node or an error, if there was one.