Documentation
¶
Index ¶
- func ApplyNodeInorder[T any](node *BinarySearchTreeNode[T], f func(item T))
- func ApplyNodePostorder[T any](node *BinarySearchTreeNode[T], f func(item T))
- func ApplyNodePreorder[T any](node *BinarySearchTreeNode[T], f func(item T))
- func ApplyTreeInorder[T any](tree *BinarySearchTree[T], f func(item T))
- func ApplyTreePostorder[T any](tree *BinarySearchTree[T], f func(item T))
- func ApplyTreePreorder[T any](tree *BinarySearchTree[T], f func(item T))
- func FoldNodeInorder[T, G any](node *BinarySearchTreeNode[T], initialAccumulator G, ...) G
- func FoldNodePostorder[T, G any](node *BinarySearchTreeNode[T], initialAccumulator G, ...) G
- func FoldNodePreorder[T, G any](node *BinarySearchTreeNode[T], initialAccumulator G, ...) G
- func FoldTreeInorder[T, G any](tree *BinarySearchTree[T], initialAccumulator G, ...) G
- func FoldTreePostorder[T, G any](tree *BinarySearchTree[T], initialAccumulator G, ...) G
- func FoldTreePreorder[T, G any](tree *BinarySearchTree[T], initialAccumulator G, ...) G
- type BinarySearchTree
- type BinarySearchTreeNode
- func (node *BinarySearchTreeNode[T]) Height() int
- func (node *BinarySearchTreeNode[T]) Item() T
- func (node *BinarySearchTreeNode[T]) Left() *BinarySearchTreeNode[T]
- func (node *BinarySearchTreeNode[T]) Parent() *BinarySearchTreeNode[T]
- func (node *BinarySearchTreeNode[T]) Predecessor() *BinarySearchTreeNode[T]
- func (node *BinarySearchTreeNode[T]) Right() *BinarySearchTreeNode[T]
- func (node *BinarySearchTreeNode[T]) Size() int
- func (node *BinarySearchTreeNode[T]) Successor() *BinarySearchTreeNode[T]
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ApplyNodeInorder ¶
func ApplyNodeInorder[T any](node *BinarySearchTreeNode[T], f func(item T))
Apply a function f to each node in a tree Inorder.
Apply should not change the item in a Node, as this could affect the binary tree structure.
func ApplyNodePostorder ¶
func ApplyNodePostorder[T any](node *BinarySearchTreeNode[T], f func(item T))
Apply a function f to each node in a tree Postorder.
Apply should not change the item in a Node, as this could affect the binary tree structure.
func ApplyNodePreorder ¶
func ApplyNodePreorder[T any](node *BinarySearchTreeNode[T], f func(item T))
Apply a function f to each node in a tree Preorder.
Apply should not change the item in a Node, as this could affect the binary tree structure.
func ApplyTreeInorder ¶
func ApplyTreeInorder[T any](tree *BinarySearchTree[T], f func(item T))
Apply a function f to each node in a tree Inorder.
Apply should not change the item in a Node, as this could affect the binary tree structure.
This method is a wrapper for InorderTraversalFold(tree.root, initialAccumulator, f)
func ApplyTreePostorder ¶
func ApplyTreePostorder[T any](tree *BinarySearchTree[T], f func(item T))
Apply a function f to each node in a tree Postorder.
Apply should not change the item in a Node, as this could affect the binary tree structure.
This method is a wrapper for PostorderTraversalFold(tree.root, initialAccumulator, f)
func ApplyTreePreorder ¶
func ApplyTreePreorder[T any](tree *BinarySearchTree[T], f func(item T))
Apply a function f to each node in a tree Preorder.
Apply should not change the item in a Node, as this could affect the binary tree structure.
This method is a wrapper for PreorderTraversalFold(tree.root, initialAccumulator, f)
func FoldNodeInorder ¶
func FoldNodeInorder[T, G any](node *BinarySearchTreeNode[T], initialAccumulator G, f func(item T, accumulator G) G) G
Fold a function f (taking the current node item and the accumulator value) across the tree Inorder. f must return the next value of the accumulator.
Returns the final accumulator value
func FoldNodePostorder ¶
func FoldNodePostorder[T, G any](node *BinarySearchTreeNode[T], initialAccumulator G, f func(item T, accumulator G) G) G
Fold a function f (taking the current node item and the accumulator value) across the tree Postorder. f must return the next value of the accumulator.
Returns the final accumulator value
func FoldNodePreorder ¶
func FoldNodePreorder[T, G any](node *BinarySearchTreeNode[T], initialAccumulator G, f func(item T, accumulator G) G) G
Fold a function f (taking the current node item and the accumulator value) across the tree Preorder. f must return the next value of the accumulator.
Returns the final accumulator value
func FoldTreeInorder ¶
func FoldTreeInorder[T, G any](tree *BinarySearchTree[T], initialAccumulator G, f func(item T, accumulator G) G) G
Fold a function f over the tree Inorder.
This method is a wrapper for FoldInorder(tree.root, initialAccumulator, f)
func FoldTreePostorder ¶
func FoldTreePostorder[T, G any](tree *BinarySearchTree[T], initialAccumulator G, f func(item T, accumulator G) G) G
Fold a function f over the tree Postorder.
This method is a wrapper for FoldPostorder(tree.root, initialAccumulator, f)
func FoldTreePreorder ¶
func FoldTreePreorder[T, G any](tree *BinarySearchTree[T], initialAccumulator G, f func(item T, accumulator G) G) G
Fold a function f over the tree preorder.
This method is a wrapper for FoldPreorder(tree.root, initialAccumulator, f)
Types ¶
type BinarySearchTree ¶
type BinarySearchTree[T any] struct { // contains filtered or unexported fields }
Implement a binary search tree.
A BST has items stored in nodes, such that all left/right children are respectively smaller/larger than the parent node.
func New ¶
func New[T any](comparatorFunction comparator.ComparatorFunction[T]) *BinarySearchTree[T]
Create a new binary tree of generic type.
The comparator function (see github.com/hmcalister/Go-DSA/Comparator) defines how the items are ordered when creating the tree. This allows for trees that have any type, rather than just comparable types.
func (*BinarySearchTree[T]) Add ¶
func (tree *BinarySearchTree[T]) Add(item T) error
Insert a new item into the tree.
Returns a dsa_error.ItemAlreadyPresent error if the item already exists in the tree.
func (*BinarySearchTree[T]) Find ¶
func (tree *BinarySearchTree[T]) Find(item T) (*BinarySearchTreeNode[T], error)
Determines if a given item is present in the tree. If the item is present in the tree, the Node containing that item is returned with nil error. If the item is not present, nil is returned along with a dsa_error.ErrorItemNotFound.
func (*BinarySearchTree[T]) Remove ¶
func (tree *BinarySearchTree[T]) Remove(item T) error
Remove an item from the tree.
Returns a dsa_error.ErrorItemNotFound if item is not present in the tree.
func (*BinarySearchTree[T]) Root ¶
func (tree *BinarySearchTree[T]) Root() *BinarySearchTreeNode[T]
Get the root the binary search tree
type BinarySearchTreeNode ¶
type BinarySearchTreeNode[T any] struct { // contains filtered or unexported fields }
func (*BinarySearchTreeNode[T]) Height ¶
func (node *BinarySearchTreeNode[T]) Height() int
Get the height of this node, the number of steps from this node to the furthest leaf node.
A leaf node has height 0.
func (*BinarySearchTreeNode[T]) Item ¶
func (node *BinarySearchTreeNode[T]) Item() T
Get the item of this tree node
BEWARE: Mutating this item (e.g. if this item is a struct, array, etc...) may break the tree structure! Only mutate the result of node.Item() if: i) The type of T is a primitive, such as int, float... in which case the result is copied anyway ii) You can ensure your mutation will not change the ordering based on the tree's ComparatorFunction
func (*BinarySearchTreeNode[T]) Left ¶
func (node *BinarySearchTreeNode[T]) Left() *BinarySearchTreeNode[T]
Get the left child of this node. May be nil.
func (*BinarySearchTreeNode[T]) Parent ¶
func (node *BinarySearchTreeNode[T]) Parent() *BinarySearchTreeNode[T]
Get the parent of this node. May be nil
The root node has a nil parent.
func (*BinarySearchTreeNode[T]) Predecessor ¶
func (node *BinarySearchTreeNode[T]) Predecessor() *BinarySearchTreeNode[T]
Return the predecessor of this node, or nil if there is no successor
func (*BinarySearchTreeNode[T]) Right ¶
func (node *BinarySearchTreeNode[T]) Right() *BinarySearchTreeNode[T]
Get the right child of this node. May be nil.
func (*BinarySearchTreeNode[T]) Size ¶
func (node *BinarySearchTreeNode[T]) Size() int
Get the size of this Node, the number of items in the subtree rooted at this node
A leaf node has size 1.
func (*BinarySearchTreeNode[T]) Successor ¶
func (node *BinarySearchTreeNode[T]) Successor() *BinarySearchTreeNode[T]
Return the successor of this node, or nil if there is no successor
Source Files