tree

Documentation

Overview

For more details check out those links below here: Wikipedia article: https://en.wikipedia.org/wiki/Binary_search_tree authors [guuzaa](https://github.com/guuzaa)

Index

• type AVL
  • func NewAVL[T constraints.Ordered]() *AVL[T]
  • func (avl *AVL[T]) AccessNodesByLayer() [][]T
  • func (avl *AVL[T]) Delete(key T) bool
  • func (avl *AVL[T]) Depth() int
  • func (avl *AVL[T]) Empty() bool
  • func (avl *AVL[T]) Get(key T) (Node[T], bool)
  • func (avl *AVL[T]) Has(key T) bool
  • func (avl *AVL[T]) InOrder() []T
  • func (avl *AVL[T]) LevelOrder() []T
  • func (avl *AVL[T]) Max() (T, bool)
  • func (avl *AVL[T]) Min() (T, bool)
  • func (avl *AVL[T]) PostOrder() []T
  • func (avl *AVL[T]) PreOrder() []T
  • func (avl *AVL[T]) Predecessor(key T) (T, bool)
  • func (avl *AVL[T]) Push(keys ...T)
  • func (avl *AVL[T]) Successor(key T) (T, bool)
• type AVLNode
  • func (n *AVLNode[T]) Height() int
  • func (n *AVLNode[T]) Key() T
  • func (n *AVLNode[T]) Left() Node[T]
  • func (n *AVLNode[T]) Parent() Node[T]
  • func (n *AVLNode[T]) Right() Node[T]
• type BSNode
  • func (n *BSNode[T]) Key() T
  • func (n *BSNode[T]) Left() Node[T]
  • func (n *BSNode[T]) Parent() Node[T]
  • func (n *BSNode[T]) Right() Node[T]
• type BinarySearch
  • func NewBinarySearch[T constraints.Ordered]() *BinarySearch[T]
  • func (t *BinarySearch[T]) AccessNodesByLayer() [][]T
  • func (t *BinarySearch[T]) Delete(val T) bool
  • func (t *BinarySearch[T]) Depth() int
  • func (t *BinarySearch[T]) Empty() bool
  • func (t *BinarySearch[T]) Get(key T) (Node[T], bool)
  • func (t *BinarySearch[T]) Has(key T) bool
  • func (t *BinarySearch[T]) InOrder() []T
  • func (t *BinarySearch[T]) LevelOrder() []T
  • func (t *BinarySearch[T]) Max() (T, bool)
  • func (t *BinarySearch[T]) Min() (T, bool)
  • func (t *BinarySearch[T]) PostOrder() []T
  • func (t *BinarySearch[T]) PreOrder() []T
  • func (t *BinarySearch[T]) Predecessor(key T) (T, bool)
  • func (t *BinarySearch[T]) Push(keys ...T)
  • func (t *BinarySearch[T]) Successor(key T) (T, bool)
• type Color
• type Node
• type RB
  • func NewRB[T constraints.Ordered]() *RB[T]
  • func (t *RB[T]) AccessNodesByLayer() [][]T
  • func (t *RB[T]) Delete(data T) bool
  • func (t *RB[T]) Depth() int
  • func (t *RB[T]) Empty() bool
  • func (t *RB[T]) Get(key T) (Node[T], bool)
  • func (t *RB[T]) Has(key T) bool
  • func (t *RB[T]) InOrder() []T
  • func (t *RB[T]) LevelOrder() []T
  • func (t *RB[T]) Max() (T, bool)
  • func (t *RB[T]) Min() (T, bool)
  • func (t *RB[T]) PostOrder() []T
  • func (t *RB[T]) PreOrder() []T
  • func (t *RB[T]) Predecessor(key T) (T, bool)
  • func (t *RB[T]) Push(keys ...T)
  • func (t *RB[T]) Successor(key T) (T, bool)
• type RBNode
  • func (n *RBNode[T]) Key() T
  • func (n *RBNode[T]) Left() Node[T]
  • func (n *RBNode[T]) Parent() Node[T]
  • func (n *RBNode[T]) Right() Node[T]

Types

type AVL

type AVL[T constraints.Ordered] struct {
	Root *AVLNode[T]
	// contains filtered or unexported fields
}

AVL represents a AVL tree. By default, _NIL = nil.

func NewAVL

func NewAVL[T constraints.Ordered]() *AVL[T]

NewAVL creates a novel AVL tree

func (*AVL[T]) AccessNodesByLayer

func (avl *AVL[T]) AccessNodesByLayer() [][]T

AccessNodesByLayer accesses nodes layer by layer (2-D array), instead of printing the results as 1-D array.

func (*AVL[T]) Delete

func (avl *AVL[T]) Delete(key T) bool

Delete a Node from the AVL Tree

func (*AVL[T]) Depth

func (avl *AVL[T]) Depth() int

Depth returns the calculated depth of the AVL tree

func (*AVL[T]) Empty

func (avl *AVL[T]) Empty() bool

Empty determines the AVL tree is empty

func (*AVL[T]) Get

func (avl *AVL[T]) Get(key T) (Node[T], bool)

Get a Node from the AVL Tree

func (*AVL[T]) Has

func (avl *AVL[T]) Has(key T) bool

Has Determines the tree has the node of Key

func (*AVL[T]) InOrder

func (avl *AVL[T]) InOrder() []T

InOrder Traverses the tree in the following order Left --> Root --> Right

func (*AVL[T]) LevelOrder

func (avl *AVL[T]) LevelOrder() []T

LevelOrder returns the level order traversal of the tree

func (*AVL[T]) Max

func (avl *AVL[T]) Max() (T, bool)

Max returns the Max value of the tree

func (*AVL[T]) Min

func (avl *AVL[T]) Min() (T, bool)

Min returns the Min value of the tree

func (*AVL[T]) PostOrder

func (avl *AVL[T]) PostOrder() []T

PostOrder traverses the tree in the following order Left --> Right --> Root

func (*AVL[T]) PreOrder

func (avl *AVL[T]) PreOrder() []T

PreOrder Traverses the tree in the following order Root --> Left --> Right

func (*AVL[T]) Predecessor

func (avl *AVL[T]) Predecessor(key T) (T, bool)

Predecessor returns the Predecessor of the node of Key if there is no predecessor, return default value of type T and false otherwise return the Key of predecessor and true

func (*AVL[T]) Push

func (avl *AVL[T]) Push(keys ...T)

Push a chain of Node's into the AVL Tree

func (*AVL[T]) Successor

func (avl *AVL[T]) Successor(key T) (T, bool)

Successor returns the Successor of the node of Key if there is no successor, return default value of type T and false otherwise return the Key of successor and true

type AVLNode

type AVLNode[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

AVLNode represents a single node in the AVL.

func (*AVLNode[T]) Height

func (n *AVLNode[T]) Height() int

func (*AVLNode[T]) Key

func (n *AVLNode[T]) Key() T

func (*AVLNode[T]) Left

func (n *AVLNode[T]) Left() Node[T]

func (*AVLNode[T]) Parent

func (n *AVLNode[T]) Parent() Node[T]

func (*AVLNode[T]) Right

func (n *AVLNode[T]) Right() Node[T]

type BSNode

type BSNode[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

BSNode represents a single node in the BinarySearch.

func (*BSNode[T]) Key

func (n *BSNode[T]) Key() T

func (*BSNode[T]) Left

func (n *BSNode[T]) Left() Node[T]

func (*BSNode[T]) Parent

func (n *BSNode[T]) Parent() Node[T]

func (*BSNode[T]) Right

func (n *BSNode[T]) Right() Node[T]

type BinarySearch

type BinarySearch[T constraints.Ordered] struct {
	Root *BSNode[T]
	// contains filtered or unexported fields
}

BinarySearch represents a Binary-Search tree. By default, _NIL = nil.

func NewBinarySearch

func NewBinarySearch[T constraints.Ordered]() *BinarySearch[T]

NewBinarySearch creates a novel Binary-Search tree

func (*BinarySearch[T]) AccessNodesByLayer

func (t *BinarySearch[T]) AccessNodesByLayer() [][]T

AccessNodesByLayer accesses nodes layer by layer (2-D array), instead of printing the results as 1-D array.

func (*BinarySearch[T]) Delete

func (t *BinarySearch[T]) Delete(val T) bool

Delete removes the node of val

func (*BinarySearch[T]) Depth

func (t *BinarySearch[T]) Depth() int

Depth returns the calculated depth of a binary search tree

func (*BinarySearch[T]) Empty

func (t *BinarySearch[T]) Empty() bool

Empty determines the Binary-Search tree is empty

func (*BinarySearch[T]) Get

func (t *BinarySearch[T]) Get(key T) (Node[T], bool)

Get a Node from the Binary-Search Tree

func (*BinarySearch[T]) Has

func (t *BinarySearch[T]) Has(key T) bool

Has Determines the tree has the node of Key

func (*BinarySearch[T]) InOrder

func (t *BinarySearch[T]) InOrder() []T

InOrder Traverses the tree in the following order Left --> Root --> Right

func (*BinarySearch[T]) LevelOrder

func (t *BinarySearch[T]) LevelOrder() []T

LevelOrder returns the level order traversal of the tree

func (*BinarySearch[T]) Max

func (t *BinarySearch[T]) Max() (T, bool)

Max returns the Max value of the tree

func (*BinarySearch[T]) Min

func (t *BinarySearch[T]) Min() (T, bool)

Min returns the Min value of the tree

func (*BinarySearch[T]) PostOrder

func (t *BinarySearch[T]) PostOrder() []T

PostOrder traverses the tree in the following order Left --> Right --> Root

func (*BinarySearch[T]) PreOrder

func (t *BinarySearch[T]) PreOrder() []T

PreOrder Traverses the tree in the following order Root --> Left --> Right

func (*BinarySearch[T]) Predecessor

func (t *BinarySearch[T]) Predecessor(key T) (T, bool)

Predecessor returns the Predecessor of the node of Key if there is no predecessor, return default value of type T and false otherwise return the Key of predecessor and true

func (*BinarySearch[T]) Push

func (t *BinarySearch[T]) Push(keys ...T)

Push a chain of Node's into the BinarySearch

func (*BinarySearch[T]) Successor

func (t *BinarySearch[T]) Successor(key T) (T, bool)

Successor returns the Successor of the node of Key if there is no successor, return default value of type T and false otherwise return the Key of successor and true

type Color

type Color byte

const (
	Red Color = iota
	Black
)

type Node

type Node[T constraints.Ordered] interface {
	Key() T
	Parent() Node[T]
	Left() Node[T]
	Right() Node[T]
}

type RB

type RB[T constraints.Ordered] struct {
	Root *RBNode[T]
	// contains filtered or unexported fields
}

RB represents a Red-Black tree. By default, _NIL = leaf, a dummy variable.

func NewRB

func NewRB[T constraints.Ordered]() *RB[T]

NewRB creates a new Red-Black Tree

func (*RB[T]) AccessNodesByLayer

func (t *RB[T]) AccessNodesByLayer() [][]T

AccessNodesByLayer accesses nodes layer by layer (2-D array), instead of printing the results as 1-D array.

func (*RB[T]) Delete

func (t *RB[T]) Delete(data T) bool

Delete a node of Red-Black Tree Returns false if the node does not exist, otherwise returns true.

func (*RB[T]) Depth

func (t *RB[T]) Depth() int

Depth returns the calculated depth of a Red-Black tree

func (*RB[T]) Empty

func (t *RB[T]) Empty() bool

Empty determines the Red-Black tree is empty

func (*RB[T]) Get

func (t *RB[T]) Get(key T) (Node[T], bool)

Get a Node from the Red-Black Tree

func (*RB[T]) Has

func (t *RB[T]) Has(key T) bool

Has Determines the tree has the node of Key

func (*RB[T]) InOrder

func (t *RB[T]) InOrder() []T

InOrder Traverses the tree in the following order Left --> Root --> Right

func (*RB[T]) LevelOrder

func (t *RB[T]) LevelOrder() []T

LevelOrder returns the level order traversal of the tree

func (*RB[T]) Max

func (t *RB[T]) Max() (T, bool)

Max returns the Max value of the tree

func (*RB[T]) Min

func (t *RB[T]) Min() (T, bool)

Min returns the Min value of the tree

func (*RB[T]) PostOrder

func (t *RB[T]) PostOrder() []T

PostOrder traverses the tree in the following order Left --> Right --> Root

func (*RB[T]) PreOrder

func (t *RB[T]) PreOrder() []T

PreOrder Traverses the tree in the following order Root --> Left --> Right

func (*RB[T]) Predecessor

func (t *RB[T]) Predecessor(key T) (T, bool)

Predecessor returns the Predecessor of the node of Key if there is no predecessor, return default value of type T and false otherwise return the Key of predecessor and true

func (*RB[T]) Push

func (t *RB[T]) Push(keys ...T)

Push a chain of Node's into the Red-Black Tree

func (*RB[T]) Successor

func (t *RB[T]) Successor(key T) (T, bool)

Successor returns the Successor of the node of Key if there is no successor, return default value of type T and false otherwise return the Key of successor and true

type RBNode

type RBNode[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

RBNode represents a single node in the RB.

func (*RBNode[T]) Key

func (n *RBNode[T]) Key() T

func (*RBNode[T]) Left

func (n *RBNode[T]) Left() Node[T]

func (*RBNode[T]) Parent

func (n *RBNode[T]) Parent() Node[T]

func (*RBNode[T]) Right

func (n *RBNode[T]) Right() Node[T]