Documentation
¶
Index ¶
- type BinarySearchTree
- func (bst *BinarySearchTree) Contains(value int) bool
- func (bst *BinarySearchTree) Height() int
- func (bst *BinarySearchTree) Insert(value int) error
- func (bst *BinarySearchTree) IsEmpty() bool
- func (bst *BinarySearchTree) Remove(value int)
- func (bst *BinarySearchTree) Size() int
- func (bst *BinarySearchTree) TotalDegree() int
- func (bst *BinarySearchTree) TraverseInOrder() []int
- func (bst *BinarySearchTree) TraverseLevelOrder() []int
- func (bst *BinarySearchTree) TraversePostOrder() []int
- func (bst *BinarySearchTree) TraversePreOrder() []int
- type Node
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BinarySearchTree ¶
type BinarySearchTree struct {
// contains filtered or unexported fields
}
BinarySearchTree is a binary tree data structure that satisfies the BST invariant: the left substree of every node has element with smaller value and the right subtree of every node has element with bigger value.
func (*BinarySearchTree) Contains ¶
func (bst *BinarySearchTree) Contains(value int) bool
Contains returns whether the tree contains a node with the specified `value` or not.
Complexity: O(log(n)) on average, O(n) in the worst case
func (*BinarySearchTree) Height ¶
func (bst *BinarySearchTree) Height() int
Height returns the height of the tree.
Complexity: O(n)
func (*BinarySearchTree) Insert ¶
func (bst *BinarySearchTree) Insert(value int) error
Insert adds an node with the specified `value` into the tree, if it does not already exists, otherwise returns an error.
Complexity: O(log(n)) on average, O(n) in the worst case
func (*BinarySearchTree) IsEmpty ¶
func (bst *BinarySearchTree) IsEmpty() bool
IsEmpty returns whether the tree is empty or not.
Complexity: O(1)
func (*BinarySearchTree) Remove ¶
func (bst *BinarySearchTree) Remove(value int)
Remove removes the node that contains the specified `value`, if exists, and restore the BST invariant.
Complexity: O(log(n)) on average, O(n) in the worst case
func (*BinarySearchTree) Size ¶
func (bst *BinarySearchTree) Size() int
Size returns the number of elements contained into the tree.
Complexity: O(1)
func (*BinarySearchTree) TotalDegree ¶
func (bst *BinarySearchTree) TotalDegree() int
TotalDegree returns the sum of the degree of every node of the tree.
Complexity: O(1)
func (*BinarySearchTree) TraverseInOrder ¶
func (bst *BinarySearchTree) TraverseInOrder() []int
TraverseInOrder traverses the tree nodes in an in-order fashion, putting the values into a slice and returning it.
func (*BinarySearchTree) TraverseLevelOrder ¶
func (bst *BinarySearchTree) TraverseLevelOrder() []int
TraverseLevelOrder traverses the tree nodes in a level-order fashion (basically doing a breadth first search), putting the values into a slice and returning it.
func (*BinarySearchTree) TraversePostOrder ¶
func (bst *BinarySearchTree) TraversePostOrder() []int
TraversePostOrder traverses the tree nodes in a post-order fashion, putting the values into a slice and returning it.
func (*BinarySearchTree) TraversePreOrder ¶
func (bst *BinarySearchTree) TraversePreOrder() []int
TraversePreOrder traverses the tree nodes in a pre-order fashion, putting the values into a slice and returning it.
Source Files