Documentation
¶
Overview ¶
Package btree implements a B tree.
According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties: - Every node has at most m children. - Every node, except for the root and the leaves, has at least ⌈m/2⌉ children. - The root node has at least two children unless it is a leaf. - A non-leaf node with k children contains k−1 keys. - All leaves appear on the same level.
Reference: https://en.wikipedia.org/wiki/B-tree
Index ¶
- type Entry
- type Node
- func (n *Node[K, V]) Children() []*Node[K, V]
- func (n *Node[K, V]) Height() int
- func (n *Node[K, V]) Len() int
- func (n *Node[K, V]) Max() *Entry[K, V]
- func (n *Node[K, V]) MaxNode() *Node[K, V]
- func (n *Node[K, V]) Min() *Entry[K, V]
- func (n *Node[K, V]) MinNode() *Node[K, V]
- func (n *Node[K, V]) Parent() *Node[K, V]
- type Tree
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Get(k K) (value V, ok bool)
- func (t *Tree[K, V]) Height() int
- func (t *Tree[K, V]) InOrder() []*Entry[K, V]
- func (t *Tree[K, V]) Insert(k K, v V)
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) Len() int
- func (t *Tree[K, V]) LevelOrder() []*Entry[K, V]
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) Max() (entry *Entry[K, V])
- func (t *Tree[K, V]) Min() (entry *Entry[K, V])
- func (t *Tree[K, V]) Range(f func(k K, v V) bool)
- func (t *Tree[K, V]) Remove(k K)
- func (t *Tree[K, V]) Root() *Node[K, V]
- func (t *Tree[K, V]) Search(k K) (node *Node[K, V], index int)
- func (t *Tree[K, V]) String() string
- func (t *Tree[K, V]) UnmarshalJSON(data []byte) error
- func (t *Tree[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Entry ¶
type Entry[K comparable, V any] struct { // The value stored with this entry. Value V // contains filtered or unexported fields }
Entry represents a key-value pair of a node.
type Node ¶
type Node[K comparable, V any] struct { // The entries stored with this node. Entries []*Entry[K, V] // contains filtered or unexported fields }
Node is a node of a B-tree.
func (*Node[K, V]) Len ¶
Len returns the number of entries of subtree with node n as the root. The complexity is O(n).
func (*Node[K, V]) Max ¶
Max returns the entry which key is the maximum key of subtree with node n as the root.
func (*Node[K, V]) MaxNode ¶
MaxNode returns the right-most (max) node which entries contains the maximum key of subtree with node n as the root.
func (*Node[K, V]) Min ¶
Min returns the entry which key is the minimum key of subtree with node n as the root.
type Tree ¶
type Tree[K comparable, V any] struct { // contains filtered or unexported fields }
Tree represents a B-tree.
func New ¶
New returns an initialized tree with cmp.Compare as the cmp function.
func (*Tree[K, V]) Get ¶
Get returns the value which key equals to the given key k. The ok result indicates whether such value was found in tree.
func (*Tree[K, V]) InOrder ¶
InOrder performs in-order traversal for tree, and returns a slice of entries as the result.
func (*Tree[K, V]) Insert ¶
func (t *Tree[K, V]) Insert(k K, v V)
Insert inserts a new entry with the given key-value pair (k, v) to tree, or update the key and value if key k already exists in tree.
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Values returns all keys in tree (in in-order traversal order).
func (*Tree[K, V]) LevelOrder ¶
LevelOrder performs level-order traversal for tree, and returns a slice of entries as the result.
func (*Tree[K, V]) MarshalJSON ¶
MarshalJSON marshals tree into valid JSON. Ref: std json.Marshaler.
func (*Tree[K, V]) Range ¶
Range calls f sequentially for each entry present in tree in in-order traversal order. If f returns false, range stops the iteration.
func (*Tree[K, V]) Remove ¶
func (t *Tree[K, V]) Remove(k K)
Remove removes the entry (and node) which key equals to the given key k from tree.
func (*Tree[K, V]) Search ¶
Search returns the node which entries contains the given key k and the corresponding index in tree, or nil and -1 if no such node found.
func (*Tree[K, V]) String ¶
String returns the string representation of tree. Ref: std fmt.Stringer.
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON unmarshals a JSON description of tree. The input can be assumed to be a valid encoding of a JSON value. UnmarshalJSON must copy the JSON data if it wishes to retain the data after returning. Ref: std json.Unmarshaler.
Source Files