tree

Documentation

Index

• func BlackViolationValidate[K infra.OrderedKey, V any](tree RBTree[K, V]) error
• func RedViolationValidate[K infra.OrderedKey, V any](tree RBTree[K, V]) error
• type RBColor
  • func (i RBColor) String() string
• type RBDirection
  • func (i RBDirection) String() string
• type RBNode
• type RBTree
  • func NewRBTree[K infra.OrderedKey, V any](opts ...RBTreeOpt[K, V]) RBTree[K, V]
• type RBTreeOpt
  • func WithRBTreeDesc[K infra.OrderedKey, V any]() RBTreeOpt[K, V]
  • func WithRBTreeRemoveBorrowSucc[K infra.OrderedKey, V any]() RBTreeOpt[K, V]

Functions

func BlackViolationValidate

func BlackViolationValidate[K infra.OrderedKey, V any](tree RBTree[K, V]) error

<X> is a RED node. [X] is a BLACK node (or NIL).

        [13]
		/  \
	 <8>    [15]
	 / \    /  \
  [6] [11] [14] [17]
  /              /
<1>            [16]

2-3-4 tree like:

       <8> --- [13] --- <15>
	  /  \             /    \
	 /    \           /      \
  <1>-[6][11]      [14] <16>-[17]

Each leaf node to root node black depth are equal.

func RedViolationValidate

func RedViolationValidate[K infra.OrderedKey, V any](tree RBTree[K, V]) error

Inorder traversal to validate the rbtree properties.

Types

type RBColor

type RBColor uint8

const (
	Black RBColor = iota
	Red
)

func (RBColor) String

func (i RBColor) String() string

type RBDirection

type RBDirection int8

const (
	Left RBDirection = -1 + iota
	Root
	Right
)

func (RBDirection) String

func (i RBDirection) String() string

type RBNode

type RBNode[K infra.OrderedKey, V any] interface {
	Key() K
	Val() V
	HasKeyVal() bool
	Color() RBColor
	Left() RBNode[K, V]
	Right() RBNode[K, V]
	Parent() RBNode[K, V]
}

type RBTree

type RBTree[K infra.OrderedKey, V any] interface {
	Len() int64
	Root() RBNode[K, V]
	Insert(key K, val V, ifNotPresent ...bool) error
	Remove(key K) (RBNode[K, V], error)
	RemoveMin() (RBNode[K, V], error)
	Foreach(action func(idx int64, color RBColor, key K, val V) bool)
	Release()
}

func NewRBTree

func NewRBTree[K infra.OrderedKey, V any](opts ...RBTreeOpt[K, V]) RBTree[K, V]

type RBTreeOpt

type RBTreeOpt[K infra.OrderedKey, V any] func(*rbTree[K, V])

func WithRBTreeDesc

func WithRBTreeDesc[K infra.OrderedKey, V any]() RBTreeOpt[K, V]

func WithRBTreeRemoveBorrowSucc

func WithRBTreeRemoveBorrowSucc[K infra.OrderedKey, V any]() RBTreeOpt[K, V]