binarysearchtree

Documentation

Overview

Package binarysearchtree creates a BinarySearchTree data structure for the Key and Value types specified in in the constraints of the generic structs and interfaces.

Specifically, the key type must be ordered and the value type may be any valid type.

References: https://hackthedeveloper.com/golang-binary-search-tree/ https://www.golangprograms.com/golang-program-to-implement-binary-tree.html

Index

• func InOrder[K constraints.Ordered, V any](root *Node[K, V])
• type BSTer
  • func New[K constraints.Ordered, V any]() BSTer[K, V]
• type Bst
  • func (bst *Bst[K, V]) InOrderTraverse(f func(V))
  • func (bst *Bst[K, V]) Insert(key K, value V)
  • func (bst *Bst[K, V]) Max() *V
  • func (bst *Bst[K, V]) Min() *V
  • func (bst *Bst[K, V]) PostOrderTraverse(f func(V))
  • func (bst *Bst[K, V]) PreOrderTraverse(f func(V))
  • func (bst *Bst[K, V]) Remove(key K) *Node[K, V]
  • func (bst *Bst[K, V]) Root() *Node[K, V]
  • func (bst *Bst[K, V]) Search(key K) bool
  • func (bst *Bst[K, V]) String() string
• type Node

Functions

func InOrder

func InOrder[K constraints.Ordered, V any](root *Node[K, V])

InOrder Traversal

Types

type BSTer

type BSTer[K constraints.Ordered, V any] interface {
	Insert(key K, value V)       // inserts the Item t in the tree
	Search(key K) bool           // returns true if the Item t exists in the tree
	Remove(key K) *Node[K, V]    // removes the Item t from the tree
	InOrderTraverse(f func(V))   //visits all nodes with in-order traversing
	PreOrderTraverse(f func(V))  //visits all nodes with pre-order traversing
	PostOrderTraverse(f func(V)) //visits all nodes with post-order traversing
	Min() *V                     //returns the Item with min value stored in the tree
	Max() *V                     //returns the Item with max value stored in the tree
	String() string              //prints a CLI readable rendering of the tree
	Root() *Node[K, V]           // returns the root node of the tree
}

func New

func New[K constraints.Ordered, V any]() BSTer[K, V]

New returns a new empty BinarySearchTree. Most features require one or more nodes to be inserted. The first node inserted will be the root node and all subsequent nodes will be positioned automatically, often changing the root node.

type Bst

type Bst[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Bst is a generic binary search tree

func (*Bst[K, V]) InOrderTraverse

func (bst *Bst[K, V]) InOrderTraverse(f func(V))

InOrderTraverse visits all nodes with in-order traversing

func (*Bst[K, V]) Insert

func (bst *Bst[K, V]) Insert(key K, value V)

Insert inserts the item t in the tree

func (*Bst[K, V]) Max

func (bst *Bst[K, V]) Max() *V

Max returns the item with max value stored in the tree

func (*Bst[K, V]) Min

func (bst *Bst[K, V]) Min() *V

Min returns the item with min value stored in the tree

func (*Bst[K, V]) PostOrderTraverse

func (bst *Bst[K, V]) PostOrderTraverse(f func(V))

PostOrderTraverse visits all nodes with post-order traversing

func (*Bst[K, V]) PreOrderTraverse

func (bst *Bst[K, V]) PreOrderTraverse(f func(V))

PreOrderTraverse visits all nodes with pre-order traversing

func (*Bst[K, V]) Remove

func (bst *Bst[K, V]) Remove(key K) *Node[K, V]

Remove removes the item t from the tree

func (*Bst[K, V]) Root

func (bst *Bst[K, V]) Root() *Node[K, V]

func (*Bst[K, V]) Search

func (bst *Bst[K, V]) Search(key K) bool

Search returns true if the item t exists in the tree

func (*Bst[K, V]) String

func (bst *Bst[K, V]) String() string

String returns a CLI readable rendering of the tree

type Node

type Node[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Node a single Node that composes the tree