README
¶
Canopy
A collection of binary tree data structures.
Example usage:
tree := binary.NewBinarySearchTree[int]()
binary.InsertAll(tree, 3, 2, 4)
printer := func(n binary.Node[int]) bool {
fmt.Println("node value: ", n.Value())
return true
}
tree.Traverse(binary.InOrder[int], printer)
Binary Search Tree
A standard binary search tree.
tree := canopy.NewBinarySearchTree[int]()
Splay Tree
A Splay Tree is a binary tree which has the following properties:
- Binary tree
- Not necessarily balanced
- Any node with the most recent access is brought to the root
tree := canopy.NewSplayTree[int]()
Resources
Red Black Tree
A self-balancing binary tree where each node is colored red or black.
tree := canopy.NewRedBlackTree[int]()
Resources
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
- Michael Sambol's videos on Red-Black Trees
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 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 Tree[E])
- type BSTree
- type Node
- type RBTree
- type RedBlackTree
- type SplayTree
- type Tree
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BreadthFirst ¶
BreadthFirst traverses a binary tree with breadth first ordering.
Types ¶
type BSTree ¶
BSTree is a binary search tree.
func NewBinarySearchTree ¶
NewBinarySearchTree creates a binary search tree.
type RBTree ¶
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 ¶
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
type SplayTree ¶
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 (*SplayTree[E]) Delete ¶
Delete Remove nodes from the splay tree. Based off the wikipedia description: https://en.wikipedia.org/wiki/Splay_tree#Deletion
type Tree ¶
type Tree[E cmp.Ordered] interface { // Insert Places a value into the tree. // Returns true if the value was inserted, false if the value exists already. Insert(value E) bool // Delete Removes a value into the tree. // Returns true if the value was removed. Delete(value E) bool // Find Returns true if a value exists in the tree. Find(value E) bool // Traverse provides a way to visit the nodes in a binary tree. Traverse(method func(node Node[E], v func(node Node[E]) bool) bool, visitor func(node Node[E]) bool) }
Tree The interface for all tree types.
Source Files