rbtree

README

Golang Generic Red-Black Tree

Package rbtree is a zero-dependencies library that provides methods to work with generic red-black tree. Both primitives and user-defined types can be used as values of the red-black tree nodes.

Go version

1.22+

Usage

package main

import (
	"fmt"

	"github.com/ol-se/rbtree"
)

func main() {
	t := rbtree.NewOrdered[int]()

	for i := range 10 {
		_, _ = t.Insert(i)
	}

	fmt.Println(t)
}

For more examples on how to use (e.g. iterate the tree or work with user-defined types), see examples.

Complexity

• Insert: O(log n)
• Delete: O(log n)

BenchmarkRW/InsertDelete-1000-4       2908       626676 ns/op
BenchmarkRW/InsertDelete-100000-4       14     74021303 ns/op
BenchmarkRW/InsertDelete-10000000-4      1   7736143898 ns/op

• Find: O(log n)

BenchmarkRW/Find-1000-4       8200576   150.4 ns/op
BenchmarkRW/Find-100000-4     5125063   234.4 ns/op
BenchmarkRW/Find-10000000-4   3669334   328.7 ns/op

License

Distributed under the Unlicense.

Documentation

Overview

Package rbtree provides methods to work with generic red-black tree.

Index

• type RBNode
  • func (rbn *RBNode[T]) Next() (*RBNode[T], bool)
  • func (rbn *RBNode[T]) Prev() (*RBNode[T], bool)
• type RBTree
  • func New[T any](cmp func(T, T) int) *RBTree[T]
  • func NewOrdered[T cmp.Ordered]() *RBTree[T]
  • func (rbt *RBTree[T]) Clone() *RBTree[T]
  • func (rbt *RBTree[T]) Delete(val T) (T, bool)
  • func (rbt *RBTree[T]) EqualTo(anotherRBT *RBTree[T]) bool
  • func (rbt *RBTree[T]) Find(val T) (*RBNode[T], bool)
  • func (rbt *RBTree[T]) Insert(val T) (*RBNode[T], bool)
  • func (rbt *RBTree[T]) IsValid() bool
  • func (rbt *RBTree[T]) String() string

Types

type RBNode

type RBNode[T any] struct {
	Val T
	// contains filtered or unexported fields
}

RBNode is a node of a red-black tree.

func (*RBNode[T]) Next

func (rbn *RBNode[T]) Next() (*RBNode[T], bool)

Next returns the node with the next closest value and true if this node exists.

func (*RBNode[T]) Prev

func (rbn *RBNode[T]) Prev() (*RBNode[T], bool)

Prev returns the node with the previous closest value and true if this node exists.

type RBTree

type RBTree[T any] struct {

	// Min is a pointer to the node with the smallest value of the tree.
	Min *RBNode[T]
	// Left is a pointer to the node with the biggest value of the tree.
	Max *RBNode[T]
	// Count is an amount of nodes in the tree.
	Count int
	// contains filtered or unexported fields
}

RBTree is a red-black tree. It contains the size and pointers to the first and the last nodes. RBTree consists of red and black nodes.

func New

func New[T any](cmp func(T, T) int) *RBTree[T]

New returns an empty red-black tree. cmp is a pointer to the function to compare user-defined types.

cmp returns the result of comparison:

• result < 0, if first value is smaller;
• result > 0, if first value is bigger;
• result == 0, if both values are equal.

For ordered primitive types, use NewOrdered.

func NewOrdered

func NewOrdered[T cmp.Ordered]() *RBTree[T]

NewOrdered returns an empty red-black tree for primitive types (cmp.Ordered).

func (*RBTree[T]) Clone

func (rbt *RBTree[T]) Clone() *RBTree[T]

Clone copies the red-black tree to a new red-black tree with the same values and structure. Clone returns a new red-black tree.

func (*RBTree[T]) Delete

func (rbt *RBTree[T]) Delete(val T) (T, bool)

Delete deletes a node with particular value from the red-black tree and fixes the tree if necessary. Delete returns the deleted value and true if deletion was successful. It returns an empty value and false otherwise.

func (*RBTree[T]) EqualTo

func (rbt *RBTree[T]) EqualTo(anotherRBT *RBTree[T]) bool

EqualTo checks if both trees have the same structure and nodes.

func (*RBTree[T]) Find

func (rbt *RBTree[T]) Find(val T) (*RBNode[T], bool)

Find returns the node pointer and true if a node with particular value was found in the red-black tree.

func (*RBTree[T]) Insert

func (rbt *RBTree[T]) Insert(val T) (*RBNode[T], bool)

Insert adds a new value to the red-black tree and fixes the tree afterwards if necessary. If the insertion was successful, the newly inserted node and true are returned. Otherwise the existent node and false are returned.

func (*RBTree[T]) IsValid

func (rbt *RBTree[T]) IsValid() bool

IsValid checks if the tree is a valid red-black tree.

func (*RBTree[T]) String

func (rbt *RBTree[T]) String() string