rbtree

Documentation

Index

• Constants
• type BST
  • func NewBSTree[K constraints.Ordered, T any]() *BST[K, T]
  • func (t *BST[K, T]) Insert(key K, data T)
  • func (t *BST[K, T]) Leftmost(n *RBNode[K, T]) *RBNode[K, T]
  • func (t *BST[K, T]) Min(n *RBNode[K, T]) *RBNode[K, T]
  • func (t *BST[K, T]) Print()
  • func (t *BST[K, T]) Search(key K) *RBNode[K, T]
• type Color
  • func (c Color) String() string
• type Compare
• type RBNode
  • func NewRBNode[K cmp.Ordered, T any](parent, left, right *RBNode[K, T], key K, data ...T) *RBNode[K, T]
  • func (n *RBNode[K, T]) Color() Color
  • func (n *RBNode[K, T]) Grandparent() *RBNode[K, T]
  • func (n *RBNode[K, T]) IsBlack() bool
  • func (n *RBNode[K, T]) IsLeftChild() bool
  • func (n *RBNode[K, T]) IsRed() bool
  • func (n *RBNode[K, T]) IsRightChild() bool
  • func (n *RBNode[K, T]) Left() *RBNode[K, T]
  • func (n *RBNode[K, T]) Parent() *RBNode[K, T]
  • func (n *RBNode[K, T]) Right() *RBNode[K, T]
  • func (n *RBNode[K, T]) Sibling() *RBNode[K, T]
  • func (n *RBNode[K, T]) Uncle() *RBNode[K, T]
• type RBTree
  • func NewRBTree[K cmp.Ordered, T any](customCompare ...Compare[K]) *RBTree[K, T]
  • func (t *RBTree[K, T]) Delete(n *RBNode[K, T]) bool
  • func (t *RBTree[K, T]) DeleteUnsafe(n *RBNode[K, T])
  • func (t *RBTree[K, T]) Insert(key K, data T) (*RBNode[K, T], bool)
  • func (t *RBTree[K, T]) InsertNode(n *RBNode[K, T]) (*RBNode[K, T], bool)
  • func (t *RBTree[K, T]) Leftmost() *RBNode[K, T]
  • func (t *RBTree[K, T]) Max(n *RBNode[K, T]) *RBNode[K, T]
  • func (t *RBTree[K, T]) Min(n *RBNode[K, T]) *RBNode[K, T]
  • func (t *RBTree[K, T]) Next(n *RBNode[K, T]) *RBNode[K, T]
  • func (t *RBTree[K, T]) Print()
  • func (t *RBTree[K, T]) Rightmost() *RBNode[K, T]
  • func (t *RBTree[K, T]) RotateLeft(n *RBNode[K, T])
  • func (t *RBTree[K, T]) RotateRight(n *RBNode[K, T])
  • func (t *RBTree[K, T]) Search(key K) *RBNode[K, T]
  • func (t *RBTree[K, T]) Walk(f func(int, bool, *RBNode[K, T]))

Constants

const (
	LESS = iota - 1
	EQUAL
	GREATER
)

Types

type BST

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

func NewBSTree

func NewBSTree[K constraints.Ordered, T any]() *BST[K, T]

func (*BST[K, T]) Insert

func (t *BST[K, T]) Insert(key K, data T)

func (*BST[K, T]) Leftmost

func (t *BST[K, T]) Leftmost(n *RBNode[K, T]) *RBNode[K, T]

func (*BST[K, T]) Min

func (t *BST[K, T]) Min(n *RBNode[K, T]) *RBNode[K, T]

func (*BST[K, T]) Print

func (t *BST[K, T]) Print()

func (*BST[K, T]) Search

func (t *BST[K, T]) Search(key K) *RBNode[K, T]

type Color

type Color uint8

const (
	RED Color = iota
	BLACK
)

func (Color) String

func (c Color) String() string

type Compare

type Compare[K cmp.Ordered] func(a, b K) int

this comparator sucks. However, we have to use it because when we need to use a custom comparator and this comparator is the fastest way to compare generics.

type RBNode

type RBNode[K cmp.Ordered, T any] struct {
	Key  K
	Data T
	// contains filtered or unexported fields
}

func NewRBNode

func NewRBNode[K cmp.Ordered, T any](parent, left, right *RBNode[K, T], key K, data ...T) *RBNode[K, T]

func (*RBNode[K, T]) Color

func (n *RBNode[K, T]) Color() Color

func (*RBNode[K, T]) Grandparent

func (n *RBNode[K, T]) Grandparent() *RBNode[K, T]

func (*RBNode[K, T]) IsBlack

func (n *RBNode[K, T]) IsBlack() bool

func (*RBNode[K, T]) IsLeftChild

func (n *RBNode[K, T]) IsLeftChild() bool

func (*RBNode[K, T]) IsRed

func (n *RBNode[K, T]) IsRed() bool

func (*RBNode[K, T]) IsRightChild

func (n *RBNode[K, T]) IsRightChild() bool

func (*RBNode[K, T]) Left

func (n *RBNode[K, T]) Left() *RBNode[K, T]

func (*RBNode[K, T]) Parent

func (n *RBNode[K, T]) Parent() *RBNode[K, T]

func (*RBNode[K, T]) Right

func (n *RBNode[K, T]) Right() *RBNode[K, T]

func (*RBNode[K, T]) Sibling

func (n *RBNode[K, T]) Sibling() *RBNode[K, T]

func (*RBNode[K, T]) Uncle

func (n *RBNode[K, T]) Uncle() *RBNode[K, T]

type RBTree

type RBTree[K cmp.Ordered, T any] struct {
	// contains filtered or unexported fields
}

func NewRBTree

func NewRBTree[K cmp.Ordered, T any](customCompare ...Compare[K]) *RBTree[K, T]

func (*RBTree[K, T]) Delete

func (t *RBTree[K, T]) Delete(n *RBNode[K, T]) bool

func (*RBTree[K, T]) DeleteUnsafe

func (t *RBTree[K, T]) DeleteUnsafe(n *RBNode[K, T])

Unsafe delete, it will not check wether the n is in the tree if n is not in the tree, it will panic. this function is for performance when you can ensure n is in the tree, otherwise, use Delete() instead.

func (*RBTree[K, T]) Insert

func (t *RBTree[K, T]) Insert(key K, data T) (*RBNode[K, T], bool)

Insert a key and data into the RBTree, if the key exists, return the node and wether it's inserted or not.

func (*RBTree[K, T]) InsertNode

func (t *RBTree[K, T]) InsertNode(n *RBNode[K, T]) (*RBNode[K, T], bool)

func (*RBTree[K, T]) Leftmost

func (t *RBTree[K, T]) Leftmost() *RBNode[K, T]

func (*RBTree[K, T]) Max

func (t *RBTree[K, T]) Max(n *RBNode[K, T]) *RBNode[K, T]

func (*RBTree[K, T]) Min

func (t *RBTree[K, T]) Min(n *RBNode[K, T]) *RBNode[K, T]

func (*RBTree[K, T]) Next

func (t *RBTree[K, T]) Next(n *RBNode[K, T]) *RBNode[K, T]

func (*RBTree[K, T]) Print

func (t *RBTree[K, T]) Print()

func (*RBTree[K, T]) Rightmost

func (t *RBTree[K, T]) Rightmost() *RBNode[K, T]

func (*RBTree[K, T]) RotateLeft

func (t *RBTree[K, T]) RotateLeft(n *RBNode[K, T])

	 	  |                       |
		  N                       S
		 / \     l-rotate(N)     / \
   		L   S    ==========>    N   R
	   	   / \                 / \
	 	  M   R               L   M

func (*RBTree[K, T]) RotateRight

func (t *RBTree[K, T]) RotateRight(n *RBNode[K, T])

		  |                       |
		  N                       L
		 / \     r-rotate(N)     / \
	 	L   S    ==========>    M   N
	   / \					       / \
   	  M   R						  R   S

func (*RBTree[K, T]) Search

func (t *RBTree[K, T]) Search(key K) *RBNode[K, T]

func (*RBTree[K, T]) Walk

func (t *RBTree[K, T]) Walk(f func(int, bool, *RBNode[K, T]))