tree

Documentation

Index

• type BST
• type BSTNodePtr
• type CompareFunc
• type KeyValuePair
  • func (n *KeyValuePair[K, V]) Get() (*K, *V)
  • func (n *KeyValuePair[K, V]) GetKey() K
  • func (n *KeyValuePair[K, V]) Set(key *K, value *V)
  • func (n *KeyValuePair[K, V]) SetValue(v V)
  • func (n *KeyValuePair[K, V]) Value() V
• type RedBlackNode
  • func (n *RedBlackNode[K, V, P]) ForEachToTail(cmp CompareFunc[K], check func(*RedBlackNode[K, V, P]))
  • func (n *RedBlackNode[K, V, P]) Head(cmp CompareFunc[K]) *RedBlackNode[K, V, P]
  • func (n *RedBlackNode[K, V, P]) IsNull() bool
  • func (p *RedBlackNode) Max() *T
  • func (p *RedBlackNode) Min() *T
  • func (n *RedBlackNode) Predecessor() *T
  • func (n *RedBlackNode) Successor() *T
  • func (n *RedBlackNode[K, V, P]) Tail(cmp CompareFunc[K]) *RedBlackNode[K, V, P]
• type RedBlackTree
  • func (t *RedBlackTree[K, V, P]) Delete(cmp CompareFunc[K], key K) P
  • func (t *RedBlackTree[K, V, P]) DeleteNode(node *RedBlackNode[K, V, P]) P
  • func (t *RedBlackTree[K, V, P]) Insert(cmp CompareFunc[K], newNode P, key K, value V)
  • func (t *RedBlackTree[K, V, P]) InsertNode(cmp CompareFunc[K], n P)
  • func (t RedBlackTree[K, V, P]) Max() *RedBlackNode[K, V, P]
  • func (t RedBlackTree[K, V, P]) Min() *RedBlackNode[K, V, P]
  • func (t RedBlackTree[K, V, P]) Search(cmp CompareFunc[K], key K) (node *RedBlackNode[K, V, P], _ bool)
  • func (t RedBlackTree[K, V, P]) Size() int
• type RedBlackTreeOptions

Types

type BST

type BST[P alloc.Ptr[P], N BSTNodePtr[N, K, V], K, V any] interface {
	// Size reports number of nodes in this tree.
	Size() int

	// Min returns the node with the minimum value in this tree, nil if there
	// is no node.
	Min() N

	// Max returns the node with the maximum value in this tree, nil if there
	// is no node.
	Max() N

	// Search node by key, return false if not found
	// return node can be non-nil even if key was not found, and that non-nil node is the node with nearest key
	Search(cmp CompareFunc[K], key K) (N, bool)

	// Insert a new node into BST
	Insert(cmp CompareFunc[K], newNode P, key K, value V)

	// Delete one node by key, return pointer to the deleted node
	//
	// it returns nil pointer when key was not found
	Delete(cmp CompareFunc[K], key K) P

	// DeleteNode removes the node n from the tree, return pointer to the deleted node
	// the node passed in MUST be a valid node inside the tree
	//
	// usually you should use Delete(key) instead, but it would be useful
	// when you need to delete some node while iterating through the nodes using Successor/Predecessor
	DeleteNode(n N) P
}

BST defines the generic Binary Search Tree interface

type BSTNodePtr

type BSTNodePtr[Self any, KeyType, ValueType any] interface {
	// Key returns the key of the node
	GetKey() KeyType

	// Value returns the stored value inside the node
	Value() ValueType

	// SetValue updates the stored value inside the node
	SetValue(ValueType)

	// Min returns the minimum node in the left subtree of the node,
	// nil if there is no node smaller than current node
	Min() Self

	// Max returns the maximum node in the right subtree of the node,
	// nil if there is no node greater than current node
	Max() Self

	// Head returns the first in tree node with its Key equivalent to current node
	Head(cmp CompareFunc[KeyType]) Self

	// Tail returns the last in tree node with its Key equivalent to current node
	Tail(cmp CompareFunc[KeyType]) Self

	// Predecessor returns the in order predecessor of current node,
	// nil if there is no more node
	Predecessor() Self

	// Successor returns the in order successor of current node,
	// nil if there is no more node
	Successor() Self

	// IsNull reports whether the node pointer is nil
	IsNull() bool
}

BSTNodePtr

type parameter `Self` MUST be a pointer type of same tree node struct

type CompareFunc

type CompareFunc[T any] func(a, b T) int64

type KeyValuePair

type KeyValuePair[K, V any] struct {
	// K is the publicly accessible key
	//
	// SHOULD NOT be updated directly, or may cause unexpected behavior
	// depending on the implementation
	K K

	// V is the value
	V V
}

func (*KeyValuePair[K, V]) Get

func (n *KeyValuePair[K, V]) Get() (*K, *V)

func (*KeyValuePair[K, V]) GetKey

func (n *KeyValuePair[K, V]) GetKey() K

func (*KeyValuePair[K, V]) Set

func (n *KeyValuePair[K, V]) Set(key *K, value *V)

func (*KeyValuePair[K, V]) SetValue

func (n *KeyValuePair[K, V]) SetValue(v V)

func (*KeyValuePair[K, V]) Value

func (n *KeyValuePair[K, V]) Value() V

type RedBlackNode

type RedBlackNode[K, V any, P alloc.Ptr[P]] struct {
	KeyValuePair[K, V] // implements Key(), Value() methods of BSTNodePointer
	// contains filtered or unexported fields
}

func (*RedBlackNode[K, V, P]) ForEachToTail

func (n *RedBlackNode[K, V, P]) ForEachToTail(cmp CompareFunc[K], check func(*RedBlackNode[K, V, P]))

func (*RedBlackNode[K, V, P]) Head

func (n *RedBlackNode[K, V, P]) Head(cmp CompareFunc[K]) *RedBlackNode[K, V, P]

Head implements BSTNodePointer

func (*RedBlackNode[K, V, P]) IsNull

func (n *RedBlackNode[K, V, P]) IsNull() bool

IsNull implements BSTNodePointer

func (*RedBlackNode) Max

func (p *RedBlackNode) Max() *T

Max implements BSTNodePointer

func (*RedBlackNode) Min

func (p *RedBlackNode) Min() *T

Min implements BSTNodePointer.

func (*RedBlackNode) Predecessor

func (n *RedBlackNode) Predecessor() *T

Predecessor implements BSTNodePointer

func (*RedBlackNode) Successor

func (n *RedBlackNode) Successor() *T

Successor implements BSTNodePointer

func (*RedBlackNode[K, V, P]) Tail

func (n *RedBlackNode[K, V, P]) Tail(cmp CompareFunc[K]) *RedBlackNode[K, V, P]

Tail implements BSTNodePointer

type RedBlackTree

type RedBlackTree[K, V any, P alloc.Ptr[P]] struct {
	RedBlackTreeOptions
	// contains filtered or unexported fields
}

RedBlackTree (1972) is the simplified implementation of a 2-3-4-Node tree to maintain (almost) perfect balance

To generalize nodes in 2-3-4-Node tree, color RED is used in RedBlackTree to join a node to its parent

A RED node <=> a node with a RED link to its parent A [BLACK] node <=> a node is either nil or with a BLACK link to its parent

2-3-4-Node tree nodes:

Kind 1: 2-Child node

     (a1)     where: c1 < a2 < c2
    /   \
   c1   c2

in RedBlackTree it's a node with no RED child node

        P (a1)
      /        \
c1 [Black]   c2 [Black]

Kind 2: 3-Child node, a node with 2 values and up to 3 children

           (a1, a2)        where: a1   <    a2
          /   |   \          c1 < a1
         c1   c2  c3              a1 < c2 < a2
                                            a2 < c3

    in RedBlackTree it's a node with exactly one RED child node

         P (a2)                       P (a1)
       /       \         or         /       \
   a1 Red    c3 [Black]       c1 [Black]   a2 Red
  /    \                                  /    \
c1     c2                               c1     c2

Kind 3: 4-Child node, a node with 3 values and up to 4 children

          (x1, x2, x3)             where: a1   <    a2   <    a3
        /    |    |    \             c1 < a1
      c1    c2    c3    c4                a1 < c2 < a2
                                                    a2 < c3 < a3
                                                              a3 < c4

  in RedBlackTree it's a node with two RED child nodes

         P (a2)
      /         \
  a1 Red       a3 Red
  /    \      /    \
c1     c2   c3     c4

RBNode requirements:

1. Every node is either red or black. 2. All NIL nodes (figure 1) are considered black. 3. A red node does not have a red child. 4. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

refs: - https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

func (*RedBlackTree[K, V, P]) Delete

func (t *RedBlackTree[K, V, P]) Delete(cmp CompareFunc[K], key K) P

Delete implements BST

func (*RedBlackTree[K, V, P]) DeleteNode

func (t *RedBlackTree[K, V, P]) DeleteNode(node *RedBlackNode[K, V, P]) P

DeleteNode deletes node from this red-black tree

func (*RedBlackTree[K, V, P]) Insert

func (t *RedBlackTree[K, V, P]) Insert(cmp CompareFunc[K], newNode P, key K, value V)

Insert implements BST

func (*RedBlackTree[K, V, P]) InsertNode

func (t *RedBlackTree[K, V, P]) InsertNode(cmp CompareFunc[K], n P)

InsertNode

func (RedBlackTree[K, V, P]) Max

func (t RedBlackTree[K, V, P]) Max() *RedBlackNode[K, V, P]

Max implements BST

func (RedBlackTree[K, V, P]) Min

func (t RedBlackTree[K, V, P]) Min() *RedBlackNode[K, V, P]

Min implements BST

func (RedBlackTree[K, V, P]) Search

func (t RedBlackTree[K, V, P]) Search(cmp CompareFunc[K], key K) (node *RedBlackNode[K, V, P], _ bool)

Search implements BST

func (RedBlackTree[K, V, P]) Size

func (t RedBlackTree[K, V, P]) Size() int

Size implements BST

type RedBlackTreeOptions

type RedBlackTreeOptions struct {
	// Allow duplication of keys, if true, there can be mulitple nodes with equivalent key
	// insert sequence of these nodes are preserved as if the later holds a greater key
	//
	// NOTE: use Head()/Tail() of returned node from Search to navigate to first/last node with equivalent key
	AllowDupKey bool
}