bstree

bstree

import "github.com/esimov/gogu/bstree"

Package bstree provides an implementation of the Binary Search Tree (BST) data structure algorithm, where each node has at most two child nodes and the key of its internal node is greater than all the keys in the respective node's left subtree and less than the ones in the right subtree.

{
	bst := New[int, string](func(a, b int) bool {
		return a < b
	})

	bst.Upsert(10, "foo")
	bst.Upsert(-1, "baz")
	bst.Upsert(2, "bar")
	bst.Upsert(-4, "qux")

	fmt.Println(bst.Size())

	tree := []string{}
	bst.Traverse(func(item Item[int, string]) {
		node, _ := bst.Get(item.Key)
		tree = append(tree, node.Val)
	})
	fmt.Println(tree)

	for key := range tree {
		bst.Delete(key)
	}

	fmt.Println(bst.Size())

}

4
[qux baz bar foo]
0

Index

• Variables
• type BsTree
  • func New[K constraints.Ordered, V any](comp gogu.CompFn[K]) *BsTree[K, V]
  • func (b *BsTree[K, V]) Delete(key K) error
  • func (b *BsTree[K, V]) Get(key K) (Item[K, V], error)
  • func (b *BsTree[K, V]) Size() int
  • func (b *BsTree[K, V]) Traverse(fn func(Item[K, V]))
  • func (b *BsTree[K, V]) Upsert(key K, val V)
• type Item
• type Node
  • func NewNode[K constraints.Ordered, V any](key K, val V) *Node[K, V]

Variables

var ErrorNotFound = fmt.Errorf("BST node not found")

type BsTree

BsTree is the basic component for the BST data structure initialization. It incorporates a thread safe mechanism using sync.Mutex to guarantee the data consistency on concurrent read and write operation.

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

func New

func New[K constraints.Ordered, V any](comp gogu.CompFn[K]) *BsTree[K, V]

New initializes a new BST data structure together with a comparison operator. Depending on the comparator it sorts the tree in ascending or descending order.

func (*BsTree[K, V]) Delete

func (b *BsTree[K, V]) Delete(key K) error

Delete removes a node defined by its key from the tree structure.

func (*BsTree[K, V]) Get

func (b *BsTree[K, V]) Get(key K) (Item[K, V], error)

Get retrieves the node item and an error in case the requested node does not exists.

func (*BsTree[K, V]) Size

func (b *BsTree[K, V]) Size() int

Size returns the size of the tree.

func (*BsTree[K, V]) Traverse

func (b *BsTree[K, V]) Traverse(fn func(Item[K, V]))

Traverse iterates over the tree structure and invokes the callback function provided as a parameter.

func (*BsTree[K, V]) Upsert

func (b *BsTree[K, V]) Upsert(key K, val V)

Upsert insert a new node or update an existing node in case the key is found in the tree list.

type Item

Item contains the node's data as a key-value pair data structure.

type Item[K constraints.Ordered, V any] struct {
    Key K
    Val V
}

type Node

Node represents the BST internal Node, having as components the Node item defined as a key-value pair and two separate pointers to the left and right child nodes.

type Node[K constraints.Ordered, V any] struct {
    Left  *Node[K, V]
    Right *Node[K, V]
    // contains filtered or unexported fields
}

func NewNode

func NewNode[K constraints.Ordered, V any](key K, val V) *Node[K, V]

NewNode creates a new node.