rbtree

README

Red-Black tree

Self balancing binary search tree

A red-black tree provides functionality similar to a map but keys can be iterated in order.

Documentation

Index

• type Iterator
  • func (it *Iterator[K, V]) Key() K
  • func (it *Iterator[K, V]) Next() bool
  • func (it *Iterator[K, V]) Reset()
  • func (it *Iterator[K, V]) Value() V
• type Node
• type Tree
  • func New[K cmp.Ordered, V any]() *Tree[K, V]
  • func (t *Tree[K, V]) Add(key K, value V)
  • func (t *Tree[K, V]) Iter() *Iterator[K, V]
  • func (t *Tree[K, V]) IterChan() <-chan Node[K, V]
  • func (t *Tree[K, V]) Len() int
  • func (t *Tree[K, V]) Remove(key K) bool
  • func (t *Tree[K, V]) Search(key K) (value V, ok bool)

Examples

• Tree.Add
• Tree.Iter

Types

type Iterator

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

Iterator represents an iterator used to iterate items in the tree.

func (*Iterator[K, V]) Key

func (it *Iterator[K, V]) Key() K

Key returns the key of the current item in the iteration.

func (*Iterator[K, V]) Next

func (it *Iterator[K, V]) Next() bool

Next moves the iterator forward, returning false when there are no more items to iterate. Next must be called before trying to access the key or value through the iterator

func (*Iterator[K, V]) Reset

func (it *Iterator[K, V]) Reset()

Reset resets the iterator to the begining.

func (*Iterator[K, V]) Value

func (it *Iterator[K, V]) Value() V

Value returns the value associated with the current item in the iteration.

type Node

type Node[K cmp.Ordered, V any] interface {
	// Key returns the key for the node in the tree.
	Key() K
	// Value returns the values associated with the node in the tree.
	Value() V
}

Node interface represents an entry in the tree.

type Tree

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

Tree is a red-black tree which is a self-balancing binary search tree.

func New

func New[K cmp.Ordered, V any]() *Tree[K, V]

New returns a new instance of a tree.

func (*Tree[K, V]) Add

func (t *Tree[K, V]) Add(key K, value V)

Add adds the key/value pair to the tree. If the key already exists in the tree, the value associated with the key is updated to the new value.

Example

package main

import (
	"fmt"

	"github.com/taylorza/go-generics/pkg/container/rbtree"
)

func main() {
	tree := rbtree.New[int, string]()
	tree.Add(0, "Zero")
	tree.Add(1, "One")
	tree.Add(2, "Two")
	tree.Add(3, "Three")
	tree.Add(4, "Four")
	tree.Add(5, "Five")
	tree.Add(6, "Six")
	tree.Add(7, "Seven")
	tree.Add(8, "Eight")
	tree.Add(9, "Nine")

	for i := 0; i < 10; i++ {
		if s, ok := tree.Search(i); ok {
			fmt.Printf("%v - %v\n", i, s)
		}
	}
}

Output:

0 - Zero
1 - One
2 - Two
3 - Three
4 - Four
5 - Five
6 - Six
7 - Seven
8 - Eight
9 - Nine

func (*Tree[K, V]) Iter

func (t *Tree[K, V]) Iter() *Iterator[K, V]

Iter returns a new instance of an Iteraator that can be used to iterate through the items in the tree.

Example

package main

import (
	"fmt"

	"github.com/taylorza/go-generics/pkg/container/rbtree"
)

func main() {
	tree := rbtree.New[int, string]()
	tree.Add(0, "Zero")
	tree.Add(1, "One")
	tree.Add(2, "Two")
	tree.Add(3, "Three")
	tree.Add(4, "Four")
	tree.Add(5, "Five")
	tree.Add(6, "Six")
	tree.Add(7, "Seven")
	tree.Add(8, "Eight")
	tree.Add(9, "Nine")

	it := tree.Iter()
	for it.Next() {
		fmt.Printf("%v - %v\n", it.Key(), it.Value())
	}
}

Output:

0 - Zero
1 - One
2 - Two
3 - Three
4 - Four
5 - Five
6 - Six
7 - Seven
8 - Eight
9 - Nine

func (*Tree[K, V]) IterChan

func (t *Tree[K, V]) IterChan() <-chan Node[K, V]

IterChan returns a channel used to iterate through all the items in the tree.

func (*Tree[K, V]) Len

func (t *Tree[K, V]) Len() int

Len returns the number of items in the tree.

func (*Tree[K, V]) Remove

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

Remove deletes the item from the tree. If the item does not exist the function returns false

func (*Tree[K, V]) Search

func (t *Tree[K, V]) Search(key K) (value V, ok bool)

Search searches the tree for an item with the specified key and returns the value if it exists. ok is false if the key does not exist.