avl

Documentation

Index

• type AVL
  • func NewWith(comparator utils.Comparator) *AVL
  • func NewWithIntComparator() *AVL
  • func NewWithStringComparator() *AVL
  • func (tree *AVL) Clear()
  • func (tree *AVL) Delete(key interface{}) (interface{}, error)
  • func (tree *AVL) DepthFirstTraversal()
  • func (tree *AVL) InOrderTraversal()
  • func (tree *AVL) Insert(key, value interface{}) (interface{}, error)
  • func (tree *AVL) IsBalanced() bool
  • func (tree *AVL) IsEmpty() bool
  • func (tree *AVL) ReturnNodeValue(key interface{}) (interface{}, error)
  • func (tree *AVL) Root() *Node
  • func (tree *AVL) Search(key interface{}) bool
  • func (tree *AVL) Size() int
  • func (tree *AVL) Update(key interface{}, value interface{}) (interface{}, error)
• 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{}) *Node
  • func (node *Node) BalanceFactor() int
• type NodeData

Types

type AVL

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

AVL 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) *AVL

NewWith returns a pointer to a BST 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() *AVL

NewWithIntComparator returns a pointer to a BST 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() *AVL

NewWithStringComparator returns a pointer to a BST 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 (*AVL) Clear

func (tree *AVL) Clear()

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

func (*AVL) Delete

func (tree *AVL) 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 (*AVL) DepthFirstTraversal

func (tree *AVL) 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 (*AVL) InOrderTraversal

func (tree *AVL) InOrderTraversal()

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

func (*AVL) Insert

func (tree *AVL) 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 (*AVL) IsBalanced

func (tree *AVL) IsBalanced() bool

IsBalanced returns a bool representing whether the AVL tree maintains the invariant: -1 <= getHeight(leftSubtree) - getHeight(rightSubtree) <= 1

func (*AVL) IsEmpty

func (tree *AVL) IsEmpty() bool

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

func (*AVL) ReturnNodeValue

func (tree *AVL) 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 (*AVL) Root

func (tree *AVL) Root() *Node

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

func (*AVL) Search

func (tree *AVL) 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 (*AVL) Size

func (tree *AVL) Size() int

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

func (*AVL) Update

func (tree *AVL) 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.

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; and NodeData, containing the key and the value the caller wishes to store.

func NewNode

func NewNode(k, v interface{}) *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.

func (*Node) BalanceFactor

func (node *Node) BalanceFactor() int

BalanceFactor returns the difference in a node's left subtree's height and its right subtree's height. Function returns 0 if node is nil.

type NodeData

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

NodeData stores the key and the value of the Node.