README
¶
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.
Example
{
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())
}
Output
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
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.
Documentation
¶
Overview ¶
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.
Example ¶
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())
Output: 4 [qux baz bar foo] 0
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrorNotFound = fmt.Errorf("BST node not found")
Functions ¶
This section is empty.
Types ¶
type BsTree ¶
type BsTree[K constraints.Ordered, V any] struct { // contains filtered or unexported fields }
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.
func New ¶
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]) Get ¶
Get retrieves the node item and an error in case the requested node does not exists.
type Item ¶
type Item[K constraints.Ordered, V any] struct { Key K Val V }
Item contains the node's data as a key-value pair data structure.
Source Files