binary

Documentation

Index

• func BreadthFirst[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool
• func InOrder[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool
• func InsertAll[E cmp.Ordered](t canopy.Tree[E], values ...E)
• func PostOrder[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool
• func PreOrder[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool
• func PrintTree[E cmp.Ordered](tree Traverser[E])
• type BSTree
  • func NewBinarySearchTree[E cmp.Ordered]() *BSTree[E]
  • func (t *BSTree[E]) Balance()
  • func (t *BSTree[E]) Delete(value E) bool
  • func (t *BSTree[E]) Find(value E) bool
  • func (t *BSTree[E]) Insert(value E) bool
  • func (t *BSTree[E]) Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, ...)
• type Node
• type RBTree
• type RedBlackTree
  • func NewRedBlackTree[E cmp.Ordered]() *RedBlackTree[E]
  • func (t *RedBlackTree[E]) Delete(value E) bool
  • func (t *RedBlackTree[E]) Find(value E) bool
  • func (t *RedBlackTree[E]) Insert(value E) bool
  • func (t *RedBlackTree[E]) Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, ...)
• type SplayTree
  • func NewSplayTree[E cmp.Ordered]() *SplayTree[E]
  • func (t *SplayTree[E]) Delete(value E) bool
  • func (t *SplayTree[E]) Find(value E) bool
  • func (t *SplayTree[E]) Insert(value E) bool
  • func (t *SplayTree[E]) Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, ...)
• type Traverser

Functions

func BreadthFirst

func BreadthFirst[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool

BreadthFirst traverses a binary tree with breadth first ordering.

func InOrder

func InOrder[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool

InOrder recursively traverses a binary tree "in order".

func InsertAll

func InsertAll[E cmp.Ordered](t canopy.Tree[E], values ...E)

InsertAll Inserts a slice of values into a given tree.

func PostOrder

func PostOrder[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool

PostOrder recursively traverses a binary tree in post order.

func PreOrder

func PreOrder[E cmp.Ordered](node Node[E], v func(node Node[E]) bool) bool

PreOrder recursively traverses a binary tree with "pre order".

func PrintTree

func PrintTree[E cmp.Ordered](tree Traverser[E])

PrintTree prints a binary tree in pre-order.

Types

type BSTree

type BSTree[E cmp.Ordered] struct {
	// contains filtered or unexported fields
}

BSTree is a binary search tree.

func NewBinarySearchTree

func NewBinarySearchTree[E cmp.Ordered]() *BSTree[E]

NewBinarySearchTree creates a binary search tree.

func (*BSTree[E]) Balance

func (t *BSTree[E]) Balance()

func (*BSTree[E]) Delete

func (t *BSTree[E]) Delete(value E) bool

func (*BSTree[E]) Find

func (t *BSTree[E]) Find(value E) bool

Find Returns true if the tree contains value.

func (*BSTree[E]) Insert

func (t *BSTree[E]) Insert(value E) bool

func (*BSTree[E]) Traverse

func (t *BSTree[E]) Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, v func(node Node[E]) bool)

type Node

type Node[E cmp.Ordered] interface {
	Value() E
	// contains filtered or unexported methods
}

Node is a common interface for all binary tree nodes.

type RBTree

type RBTree[E cmp.Ordered] struct {
	// contains filtered or unexported fields
}

RBTree a struct for red black trees. Red Black Trees have the following properties: 1) Every node is either red or black. 2) nil nodes are considered black 3) A red node cannot have a red child 4) The path from any given node goes through the same number of black nodes. 5) If a node has a single child, it must be a red child.

type RedBlackTree

type RedBlackTree[E cmp.Ordered] struct {
	// contains filtered or unexported fields
}

func NewRedBlackTree

func NewRedBlackTree[E cmp.Ordered]() *RedBlackTree[E]

NewRedBlackTree creates a new red black tree.

func (*RedBlackTree[E]) Delete

func (t *RedBlackTree[E]) Delete(value E) bool

func (*RedBlackTree[E]) Find

func (t *RedBlackTree[E]) Find(value E) bool

func (*RedBlackTree[E]) Insert

func (t *RedBlackTree[E]) Insert(value E) bool

func (*RedBlackTree[E]) Traverse

func (t *RedBlackTree[E]) Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, v func(node Node[E]) bool)

type SplayTree

type SplayTree[E cmp.Ordered] struct {
	// contains filtered or unexported fields
}

SplayTree A splay tree where the most recently accessed bsNode is rotated to the root. A splay tree does not have to be in strict balance.

func NewSplayTree

func NewSplayTree[E cmp.Ordered]() *SplayTree[E]

func (*SplayTree[E]) Delete

func (t *SplayTree[E]) Delete(value E) bool

Delete Remove nodes from the splay tree. Based off the wikipedia description: https://en.wikipedia.org/wiki/Splay_tree#Deletion

func (*SplayTree[E]) Find

func (t *SplayTree[E]) Find(value E) bool

Find - Returns true if the tree contains value. Note that the tree will splay on the bsNode containing the value, and in the case the value isn't found, on the leaf bsNode with the closest value.

func (*SplayTree[E]) Insert

func (t *SplayTree[E]) Insert(value E) bool

func (*SplayTree[E]) Traverse

func (t *SplayTree[E]) Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, v func(node Node[E]) bool)

type Traverser

type Traverser[E cmp.Ordered] interface {
	Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, visitor func(node Node[E]) bool)
}

Traverser provides a method to traverse any binary tree. method defines how the tree is traversed: PreOrder, InOrder, PostOrder, or BreadthFirst. visitor is a user defined implementation called on each node in the binary tree.