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

• 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]

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

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[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 (b *BsTree[K, V]) Delete(key K) error

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

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 (b *BsTree[K, V]) Size() int

Size returns the size of the tree.

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 (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.

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
}

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[K constraints.Ordered, V any](key K, val V) *Node[K, V]

NewNode creates a new node.