README
¶
BST
Generic binary search tree data structure and algorithms
The bst package implements a binary search tree, with the following associative-array (map) operations:
- Get
- Put
- Delete
- Size
and the following ordered-collection operations:
- VisitInOrder
- Min
- Max
Trees can be either unbalanced or balanced. Balanced trees are implemented using a Red-Black tree algorithm.
This implementation does not maintain parent pointers within the nodes of the tree. As such, many operations (in particular re-balancing after insertion and deletion) must remember the path from the root to an impacted node for the duration of the operation.
Documentation
¶
Overview ¶
Copyright (c) 2024 Thomas Mikalsen. Subject to the MIT License
Index ¶
- type BST
- func (t *BST[K, V]) Delete(key K) (ok bool)
- func (t *BST[K, V]) Get(key K) (val V, found bool)
- func (t *BST[K, V]) Max() (maxKey K, ok bool)
- func (t *BST[K, V]) Min() (minKey K, ok bool)
- func (t *BST[K, V]) MustGet(key K) (val V)
- func (t *BST[K, V]) Put(key K, val V)
- func (t *BST[K, V]) Size() int
- func (t *BST[K, V]) VisitInOrder(v types.Visitor[K, V])
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BST ¶
func (*BST[K, V]) Delete ¶
Delete removes the given key, and associated value, from the tree, and returns true if the key existed and false if it did not.
func (*BST[K, V]) Get ¶
Get returns the value associated with the given key. If not found, returns the zero value for the value type and ok=false.
func (*BST[K, V]) Put ¶
func (t *BST[K, V]) Put(key K, val V)
Put adds the given key value pair to the tree. If the key already exists in the tree, the given value replaces the existing value.
func (*BST[K, V]) VisitInOrder ¶
VisitInOrder performs an in-order traversal of all key/value pairs in the tree.
Source Files