btree

btree

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

Package btree provides an implementation of the B-tree data structure, which is a self-balancing tree data structure maintaining its values in sorted order and allowing each node to have more than two children, compared to the standard BST where each node has only two leaves. The implementation is an adapted version of https://algs4.cs.princeton.edu/62btree/BTree.java.

This package is NOT thread-safe. For data consistency some sort of concurrency safe mechanism should be implemented on the client side.

Index

• type BTree
  • [func NewK constraints.Ordered, V any *BTree[K, V]](<#func-new>)
  • func (t *BTree[K, V]) Get(key K) (V, bool)
  • func (t *BTree[K, V]) Height() int
  • func (t *BTree[K, V]) IsEmpty() bool
  • func (t *BTree[K, V]) Put(key K, val V)
  • func (t *BTree[K, V]) Remove(key K)
  • func (t *BTree[K, V]) Size() int
  • func (t *BTree[K, V]) Traverse(fn func(key K, val V))

type BTree

BTree defines a data structure with one node, which is the root node.

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

{
	btree := New[int, string]()
	fmt.Println(btree.IsEmpty())

	btree.Put(10, "foo")
	btree.Put(-1, "baz")
	btree.Put(2, "bar")
	btree.Put(-4, "qux")

	fmt.Println(btree.Size())

	tree := []string{}
	btree.Traverse(func(key int, val string) {
		item, _ := btree.Get(key)
		tree = append(tree, item)
	})
	fmt.Println(tree)

}

true
4
[qux baz bar foo]

func New

func New[K constraints.Ordered, V any]() *BTree[K, V]

New creates a new B-tree.

func (*BTree[K, V]) Get

func (t *BTree[K, V]) Get(key K) (V, bool)

Get searches for a key and in case it's found it returns the key's value together with a boolean flag signaling the key existence in the tree data structure.

func (*BTree[K, V]) Height

func (t *BTree[K, V]) Height() int

Height returns the B-tree size (how many levels it has).

func (*BTree[K, V]) IsEmpty

func (t *BTree[K, V]) IsEmpty() bool

IsEmpty checks if a B-tree is empty or not.

func (*BTree[K, V]) Put

func (t *BTree[K, V]) Put(key K, val V)

Put inserts a new value into the B-tree.

func (*BTree[K, V]) Remove

func (t *BTree[K, V]) Remove(key K)

Remove deletes a node from the B-tree.

func (*BTree[K, V]) Size

func (t *BTree[K, V]) Size() int

Size returns the B-tree size (the number of elements).

func (*BTree[K, V]) Traverse

func (t *BTree[K, V]) Traverse(fn func(key K, val V))

Traverse iterates over the tree nodes and invokes the callback function provided as argument.