Documentation ¶
Overview ¶
Package tree provides generic structures for tree-based data structures and algorithms.
Index ¶
- type BinarySearchTree
- func (self *BinarySearchTree[T]) Contains(value T) bool
- func (self *BinarySearchTree[T]) Count() int
- func (self *BinarySearchTree[T]) Height() int
- func (self *BinarySearchTree[T]) InsertNode(node *BinarySearchTreeNode[T])
- func (self *BinarySearchTree[T]) InsertTree(tree *BinarySearchTree[T])
- func (self *BinarySearchTree[T]) InsertValue(value T)
- func (self *BinarySearchTree[T]) IsBST() bool
- func (self *BinarySearchTree[T]) IsEmpty() bool
- func (self *BinarySearchTree[T]) Map(formula func(T) T) []T
- func (self *BinarySearchTree[T]) Maximum() *BinarySearchTreeNode[T]
- func (self *BinarySearchTree[T]) Minimum() *BinarySearchTreeNode[T]
- func (self *BinarySearchTree[T]) RemoveNode(value T)
- func (self *BinarySearchTree[T]) Search(value T) *BinarySearchTreeNode[T]
- func (self *BinarySearchTree[T]) String() string
- func (self *BinarySearchTree[T]) ToSlice() []T
- func (self *BinarySearchTree[T]) TraverseInOrder(process func(T))
- func (self *BinarySearchTree[T]) TraverseLevelOrder(process func(T))
- func (self *BinarySearchTree[T]) TraversePostOrder(process func(T))
- func (self *BinarySearchTree[T]) TraversePreOrder(process func(T))
- type BinarySearchTreeNode
- func (self *BinarySearchTreeNode[T]) Contains(value T) bool
- func (self *BinarySearchTreeNode[T]) Count() int
- func (self *BinarySearchTreeNode[T]) Depth() int
- func (self *BinarySearchTreeNode[T]) HasAnyChildren() bool
- func (self *BinarySearchTreeNode[T]) HasBothChildren() bool
- func (self *BinarySearchTreeNode[T]) HasLeftChild() bool
- func (self *BinarySearchTreeNode[T]) HasRightChild() bool
- func (self *BinarySearchTreeNode[T]) Height() int
- func (self *BinarySearchTreeNode[T]) Insert(node *BinarySearchTreeNode[T])
- func (self *BinarySearchTreeNode[T]) IsBST(minValue, maxValue T) bool
- func (self *BinarySearchTreeNode[T]) IsLeaf() bool
- func (self *BinarySearchTreeNode[T]) IsLeftChild() bool
- func (self *BinarySearchTreeNode[T]) IsRightChild() bool
- func (self *BinarySearchTreeNode[T]) IsRoot() bool
- func (self *BinarySearchTreeNode[T]) IterInOrder(process func(T))
- func (self *BinarySearchTreeNode[T]) IterPostOrder(process func(T))
- func (self *BinarySearchTreeNode[T]) IterPreOrder(process func(T))
- func (self *BinarySearchTreeNode[T]) Map(formula func(T) T) (nodes []T)
- func (self *BinarySearchTreeNode[T]) Maximum() *BinarySearchTreeNode[T]
- func (self *BinarySearchTreeNode[T]) Minimum() *BinarySearchTreeNode[T]
- func (self *BinarySearchTreeNode[T]) Predecessor() *BinarySearchTreeNode[T]
- func (self *BinarySearchTreeNode[T]) Remove() *BinarySearchTreeNode[T]
- func (self *BinarySearchTreeNode[T]) Search(value T) *BinarySearchTreeNode[T]
- func (self *BinarySearchTreeNode[T]) String() string
- func (self *BinarySearchTreeNode[T]) ToSlice() []T
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BinarySearchTree ¶
type BinarySearchTree[T constraints.Ordered] struct { // contains filtered or unexported fields }
Binary Search Tree Struct
func BinarySearchTreeInit ¶
func BinarySearchTreeInit[T constraints.Ordered](values ...T) *BinarySearchTree[T]
Constructor Function to return a new Binary Search Tree.
func (*BinarySearchTree[T]) Contains ¶
func (self *BinarySearchTree[T]) Contains(value T) bool
Method to return if a tree Contains a value.
func (*BinarySearchTree[T]) Count ¶
func (self *BinarySearchTree[T]) Count() int
Method to return the distance of node to it's lowest leaf. Runs in O(h) time.
func (*BinarySearchTree[T]) Height ¶
func (self *BinarySearchTree[T]) Height() int
Method to return the distance of node to it's lowest leaf. Runs in O(h) time.
func (*BinarySearchTree[T]) InsertNode ¶
func (self *BinarySearchTree[T]) InsertNode(node *BinarySearchTreeNode[T])
Method to Insert a node into the tree.
func (*BinarySearchTree[T]) InsertTree ¶
func (self *BinarySearchTree[T]) InsertTree(tree *BinarySearchTree[T])
Method to Insert a tree into the tree.
func (*BinarySearchTree[T]) InsertValue ¶
func (self *BinarySearchTree[T]) InsertValue(value T)
Mehtod to Insert a value into the tree.
func (*BinarySearchTree[T]) IsBST ¶
func (self *BinarySearchTree[T]) IsBST() bool
Method to return True if tree is a valid Binary Tree. False otherwise.
func (*BinarySearchTree[T]) IsEmpty ¶
func (self *BinarySearchTree[T]) IsEmpty() bool
Method to return True if tree is currently empty (rootless). False otherwise.
func (*BinarySearchTree[T]) Map ¶
func (self *BinarySearchTree[T]) Map(formula func(T) T) []T
Method to return a slice of the tree in-order (via tranversal) with the ability to transform the contents via a function.
func (*BinarySearchTree[T]) Maximum ¶
func (self *BinarySearchTree[T]) Maximum() *BinarySearchTreeNode[T]
Method to return the rightmost descendent of a tree. O(h) time.
func (*BinarySearchTree[T]) Minimum ¶
func (self *BinarySearchTree[T]) Minimum() *BinarySearchTreeNode[T]
Method to return the leftmost descendent of a tree. O(h) time.
func (*BinarySearchTree[T]) RemoveNode ¶
func (self *BinarySearchTree[T]) RemoveNode(value T)
Method to Remove a node from the tree.
func (*BinarySearchTree[T]) Search ¶
func (self *BinarySearchTree[T]) Search(value T) *BinarySearchTreeNode[T]
Method to iterate node in postorder order (left, right, node).
func (*BinarySearchTree[T]) String ¶
func (self *BinarySearchTree[T]) String() string
Method that return a string description of the tree.
func (*BinarySearchTree[T]) ToSlice ¶
func (self *BinarySearchTree[T]) ToSlice() []T
Method to return a slice of the tree in-order (via tranversal).
func (*BinarySearchTree[T]) TraverseInOrder ¶
func (self *BinarySearchTree[T]) TraverseInOrder(process func(T))
Method to iterate node in inorder order (left, node, right).
func (*BinarySearchTree[T]) TraverseLevelOrder ¶
func (self *BinarySearchTree[T]) TraverseLevelOrder(process func(T))
Method to iterate node in postorder order (left, right, node).
func (*BinarySearchTree[T]) TraversePostOrder ¶
func (self *BinarySearchTree[T]) TraversePostOrder(process func(T))
Method to iterate node in postorder order (left, right, node).
func (*BinarySearchTree[T]) TraversePreOrder ¶
func (self *BinarySearchTree[T]) TraversePreOrder(process func(T))
Method to iterate tree in preorder order (node, left, right).
type BinarySearchTreeNode ¶
type BinarySearchTreeNode[T constraints.Ordered] struct { // contains filtered or unexported fields }
Binary Search Tree's Node
func BinarySearchTreeNodeInit ¶
func BinarySearchTreeNodeInit[T constraints.Ordered](value T) *BinarySearchTreeNode[T]
Constructor Function to return a new BinarySearchTreeNode
func (*BinarySearchTreeNode[T]) Contains ¶
func (self *BinarySearchTreeNode[T]) Contains(value T) bool
Method to return if a node's subnode Contains a value.
func (*BinarySearchTreeNode[T]) Count ¶
func (self *BinarySearchTreeNode[T]) Count() int
Method to return number of subnodes. Runs in O(n) time.
func (*BinarySearchTreeNode[T]) Depth ¶
func (self *BinarySearchTreeNode[T]) Depth() int
Method to return the distance of node from the root. Runs in O(h) time.
func (*BinarySearchTreeNode[T]) HasAnyChildren ¶
func (self *BinarySearchTreeNode[T]) HasAnyChildren() bool
Method to return True if node has a left or right child (if HasLeftChild || HasRightChild). False if otherwise.
func (*BinarySearchTreeNode[T]) HasBothChildren ¶
func (self *BinarySearchTreeNode[T]) HasBothChildren() bool
Method to return True if node has both children (if HasLeftChild && HasRightChild). False if otherwise.
func (*BinarySearchTreeNode[T]) HasLeftChild ¶
func (self *BinarySearchTreeNode[T]) HasLeftChild() bool
Method to return True if node has a left child (if node.left != nil). False if otherwise.
func (*BinarySearchTreeNode[T]) HasRightChild ¶
func (self *BinarySearchTreeNode[T]) HasRightChild() bool
Method to return True if node has a right child (if node.right != nil). False if otherwise.
func (*BinarySearchTreeNode[T]) Height ¶
func (self *BinarySearchTreeNode[T]) Height() int
Method to return the distance of node to it's lowest leaf. Runs in O(h) time.
func (*BinarySearchTreeNode[T]) Insert ¶
func (self *BinarySearchTreeNode[T]) Insert(node *BinarySearchTreeNode[T])
Method to Insert a new node into a node's subtree. Runs in O(h) time. Where h is the Height of the node to a leaf.
func (*BinarySearchTreeNode[T]) IsBST ¶
func (self *BinarySearchTreeNode[T]) IsBST(minValue, maxValue T) bool
Methood to return true if a node and it's subtree is a valid Binary Search Tree. False otherwise.
func (*BinarySearchTreeNode[T]) IsLeaf ¶
func (self *BinarySearchTreeNode[T]) IsLeaf() bool
Method to return True if node is a leaf node (has no left or right). False if otherwise.
func (*BinarySearchTreeNode[T]) IsLeftChild ¶
func (self *BinarySearchTreeNode[T]) IsLeftChild() bool
Method to return True if node is a left child (if parent.left == node). False if otherwise.
func (*BinarySearchTreeNode[T]) IsRightChild ¶
func (self *BinarySearchTreeNode[T]) IsRightChild() bool
Method to return True if node is a right child (if parent.right == node). False if otherwise.
func (*BinarySearchTreeNode[T]) IsRoot ¶
func (self *BinarySearchTreeNode[T]) IsRoot() bool
Method to return True if node is root (has no parent node). False otherwise.
func (*BinarySearchTreeNode[T]) IterInOrder ¶
func (self *BinarySearchTreeNode[T]) IterInOrder(process func(T))
Method to iterate node in inorder order (left, node, right).
func (*BinarySearchTreeNode[T]) IterPostOrder ¶
func (self *BinarySearchTreeNode[T]) IterPostOrder(process func(T))
Method to iterate node in postorder order (left, right, node).
func (*BinarySearchTreeNode[T]) IterPreOrder ¶
func (self *BinarySearchTreeNode[T]) IterPreOrder(process func(T))
Method to iterate node in preorder order (node, left, right).
func (*BinarySearchTreeNode[T]) Map ¶
func (self *BinarySearchTreeNode[T]) Map(formula func(T) T) (nodes []T)
Method to return a slice of the node and it's subnodes in-order (via tranversal) with the ability to transform the contents via a function.
func (*BinarySearchTreeNode[T]) Maximum ¶
func (self *BinarySearchTreeNode[T]) Maximum() *BinarySearchTreeNode[T]
Method to return the rightmost descendent of a node. O(h) time.
func (*BinarySearchTreeNode[T]) Minimum ¶
func (self *BinarySearchTreeNode[T]) Minimum() *BinarySearchTreeNode[T]
Method to return the leftmost descendent of a node. O(h) time.
func (*BinarySearchTreeNode[T]) Predecessor ¶
func (self *BinarySearchTreeNode[T]) Predecessor() *BinarySearchTreeNode[T]
Method to return the node whose value precedes our value in sorted order.
func (*BinarySearchTreeNode[T]) Remove ¶
func (self *BinarySearchTreeNode[T]) Remove() *BinarySearchTreeNode[T]
Method to Remove a node with a target value form a subtree. O(h) time.
func (*BinarySearchTreeNode[T]) Search ¶
func (self *BinarySearchTreeNode[T]) Search(value T) *BinarySearchTreeNode[T]
Method to find the "highest" node with the specified value. Runs in O(h) time, where h is the Height of the node to a leaf.
func (*BinarySearchTreeNode[T]) String ¶
func (self *BinarySearchTreeNode[T]) String() string
Method that return a string description of the node and it's subnodes.
func (*BinarySearchTreeNode[T]) ToSlice ¶
func (self *BinarySearchTreeNode[T]) ToSlice() []T
Method to return a slice of the tree in-order (via tranversal).