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
- func IteratorNodeInorder[T any](node *BinarySearchTreeNode[T]) iter.Seq[T]
- func IteratorNodePostorder[T any](node *BinarySearchTreeNode[T]) iter.Seq[T]
- func IteratorNodePreorder[T any](node *BinarySearchTreeNode[T]) iter.Seq[T]
- func IteratorTreeInorder[T any](tree *BinarySearchTree[T]) iter.Seq[T]
- func IteratorTreePostorder[T any](tree *BinarySearchTree[T]) iter.Seq[T]
- func IteratorTreePreorder[T any](tree *BinarySearchTree[T]) iter.Seq[T]
- 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.
Idiomatic Go should likely use IteratorNodeInorder() rather than functional methods.
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.
Idiomatic Go should likely use IteratorNodePostorder() rather than functional methods.
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.
Idiomatic Go should likely use IteratorNodePreorder() rather than functional methods.
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.
Idiomatic Go should likely use IteratorTreeInorder() rather than functional methods.
Apply should not change the item in a Node, as this could affect the binary tree structure.
This method is a wrapper for ApplyNodeInorder(tree.root, 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.
Idiomatic Go should likely use IteratorTreePostorder() rather than functional methods.
Apply should not change the item in a Node, as this could affect the binary tree structure.
This method is a wrapper for ApplyNodePostorder(tree.root, 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.
Idiomatic Go should likely use IteratorTreePreorder() rather than functional methods.
Apply should not change the item in a Node, as this could affect the binary tree structure.
This method is a wrapper for ApplyNodePreorder(tree.root, 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.
Idiomatic Go should likely use IteratorNodeInorder() rather than functional methods.
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.
Idiomatic Go should likely use IteratorNodePostorder() rather than functional methods.
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.
Idiomatic Go should likely use IteratorNodePreorder() rather than functional methods.
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.
Idiomatic Go should likely use IteratorTreeInorder() rather than functional methods.
This method is a wrapper for FoldNodeInorder(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.
Idiomatic Go should likely use IteratorTreePostorder() rather than functional methods.
This method is a wrapper for FoldNodePostorder(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.
Idiomatic Go should likely use IteratorTreePreorder() rather than functional methods.
This method is a wrapper for FoldNodePreorder(tree.root, initialAccumulator, f)
func IteratorNodeInorder ¶ added in v1.2.0
func IteratorNodeInorder[T any](node *BinarySearchTreeNode[T]) iter.Seq[T]
Iterate over each node in a tree Inorder.
func IteratorNodePostorder ¶ added in v1.2.0
func IteratorNodePostorder[T any](node *BinarySearchTreeNode[T]) iter.Seq[T]
Iterate over each node in a tree Postorder.
func IteratorNodePreorder ¶ added in v1.2.0
func IteratorNodePreorder[T any](node *BinarySearchTreeNode[T]) iter.Seq[T]
Iterate over each node in a tree Preorder.
func IteratorTreeInorder ¶ added in v1.2.0
func IteratorTreeInorder[T any](tree *BinarySearchTree[T]) iter.Seq[T]
Iterate over the tree Inorder.
This method is a wrapper for IteratorNodeInorder(tree.root)
func IteratorTreePostorder ¶ added in v1.2.0
func IteratorTreePostorder[T any](tree *BinarySearchTree[T]) iter.Seq[T]
Iterate over the tree Postorder.
This method is a wrapper for IteratorNodePostorder(tree.root)
func IteratorTreePreorder ¶ added in v1.2.0
func IteratorTreePreorder[T any](tree *BinarySearchTree[T]) iter.Seq[T]
Iterate over the tree Preorder.
This method is a wrapper for IteratorNodePreorder(tree.root)
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]) Items ¶ added in v1.1.0
func (tree *BinarySearchTree[T]) Items() []T
Get all items from the tree. This method allocates an array of length equal to the number of items. Items may not be present in the order they were inserted.
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