redblacktrees

package module
v0.0.6 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 26, 2025 License: MIT Imports: 2 Imported by: 0

README

redblacktrees GoDoc Go Report Card

A generic Red-Black Tree for Go with rank, range, and k-th queries.

✨ Features

  • Generic Red-Black Tree using Go generics
  • O(log n) insert, delete, and search
  • Rank, k-th element, ceiling, floor, range, predecessor/successor
  • In-order iterator
  • Tree size maintained for fast queries

✅ Use When

  • You need fast insertions and deletions
  • You want balanced performance across reads and writes
  • You need ordered map-like behavior with efficient range queries

🚫 Avoid If

  • You need maximum search performance → try AVL Tree
  • You need concurrent access (not thread-safe)

📦 Installation

go get github.com/byExist/redblacktrees

🚀 Quick Start

package main

import (
	"fmt"
	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 3, "three")
	rbts.Insert(tree, 1, "one")
	rbts.Insert(tree, 2, "two")

	if node, found := rbts.Search(tree, 2); found {
		fmt.Println("Found:", node.Value)
	}

	for node := range rbts.InOrder(tree) {
		fmt.Printf("%d: %s\n", node.Key, node.Value)
	}

	fmt.Println("Rank of 3:", rbts.Rank(tree, 3))

	if node, ok := rbts.Kth(tree, 0); ok {
		fmt.Println("0-th smallest:", node.Key)
	}
}

📊 Performance

Benchmarked on Apple M1 Pro:

Operation Time (ns/op) Memory (B/op) Allocations
Insert (Random) 791.1 64 B 1
Insert (Sequential) 101.5 64 B 1
Search (Hit) 10.60 0 B 0
Search (Miss) 12.21 0 B 0
Delete (Random) 2.36 0 B 0

📚 Documentation

Full API reference: pkg.go.dev/github.com/byExist/redblacktrees

🪪 License

MIT License. See LICENSE.

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Clear 

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

Clear sets the tree root to nil, effectively clearing the tree.

func Delete 

func Delete[K cmp.Ordered, V any](t *Tree[K, V], key K) bool

Delete removes a node with the given key from the red-black tree.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 10, "ten")
	rbts.Delete(tree, 10)
	fmt.Println(rbts.Len(tree))
}

Output:

0

func InOrder 

func InOrder[K cmp.Ordered, V any](t *Tree[K, V]) iter.Seq[Node[K, V]]

InOrder returns an iterator for in-order traversal of the tree.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 20, "")
	rbts.Insert(tree, 10, "")
	rbts.Insert(tree, 30, "")
	for n := range rbts.InOrder(tree) {
		fmt.Print(n.Key(), " ")
	}
	fmt.Println()
}

Output:

10 20 30

func Insert 

func Insert[K cmp.Ordered, V any](t *Tree[K, V], key K, value V) bool

Insert inserts a new key-value pair into the red-black tree. Returns true if inserted, false if replaced.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 10, "ten")
	rbts.Insert(tree, 5, "five")
	rbts.Insert(tree, 15, "fifteen")
	fmt.Println(rbts.Len(tree))
}

Output:

3

func Len 

func Len[K cmp.Ordered, V any](t *Tree[K, V]) int

Len returns the number of nodes in the tree.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	fmt.Println(rbts.Len(tree))
}

Output:

0

func Range 

func Range[K cmp.Ordered, V any](t *Tree[K, V], from, to K) iter.Seq[Node[K, V]]

Range returns an iterator over nodes with keys in [from, to).

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 10, "")
	rbts.Insert(tree, 20, "")
	rbts.Insert(tree, 30, "")
	for n := range rbts.Range(tree, 15, 25) {
		fmt.Print(n.Key(), " ")
	}
	fmt.Println()
}

Output:

20

func Rank 

func Rank[K cmp.Ordered, V any](t *Tree[K, V], key K) int

Rank returns the number of nodes with keys less than the given key.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 10, "")
	rbts.Insert(tree, 20, "")
	rank := rbts.Rank(tree, 15)
	fmt.Println(rank)
}

Output:

1

Types

type Node 

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

Node represents a node in a red-black tree.

func Ceiling added in v0.0.3 

func Ceiling[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Ceiling returns the node with the smallest key greater than or equal to the given key.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		rbts.Insert(tree, v, "")
	}

	n, _ := rbts.Ceiling(tree, 15)
	fmt.Println(n.Key())
	n, _ = rbts.Ceiling(tree, 20)
	fmt.Println(n.Key())
}

Output:

20
20

func Floor added in v0.0.3 

func Floor[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Floor returns the node with the greatest key less than or equal to the given key.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		rbts.Insert(tree, v, "")
	}

	n, _ := rbts.Floor(tree, 25)
	fmt.Println(n.Key())
	n, _ = rbts.Floor(tree, 20)
	fmt.Println(n.Key())
}

Output:

20
20

func Higher added in v0.0.3 

func Higher[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Higher returns the node with the smallest key greater than the given key.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		rbts.Insert(tree, v, "")
	}

	n, _ := rbts.Higher(tree, 15)
	fmt.Println(n.Key())
	n, _ = rbts.Higher(tree, 20)
	fmt.Println(n.Key())
}

Output:

20
30

func Kth 

func Kth[K cmp.Ordered, V any](t *Tree[K, V], k int) (*Node[K, V], bool)

Kth returns the node with the given 0-based rank (k).

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 10, "")
	rbts.Insert(tree, 20, "")
	n, _ := rbts.Kth(tree, 1)
	fmt.Println(n.Key())
}

Output:

20

func Lower added in v0.0.3 

func Lower[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Lower returns the node with the greatest key less than the given key.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	for _, v := range []int{10, 20, 30} {
		rbts.Insert(tree, v, "")
	}

	n, _ := rbts.Lower(tree, 15)
	fmt.Println(n.Key())
	n, _ = rbts.Lower(tree, 20)
	fmt.Println(n.Key())
}

Output:

10
10

func Max 

func Max[K cmp.Ordered, V any](t *Tree[K, V]) (*Node[K, V], bool)

Max returns the node with the maximum key in the tree.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 20, "")
	rbts.Insert(tree, 30, "")
	max, ok := rbts.Max(tree)
	if ok {
		fmt.Println(max.Key())
	}
}

Output:

30

func Min 

func Min[K cmp.Ordered, V any](t *Tree[K, V]) (*Node[K, V], bool)

Min returns the node with the minimum key in the tree.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 20, "")
	rbts.Insert(tree, 10, "")
	min, ok := rbts.Min(tree)
	if ok {
		fmt.Println(min.Key())
	}
}

Output:

10

func Predecessor 

func Predecessor[K cmp.Ordered, V any](n *Node[K, V]) (*Node[K, V], bool)

Predecessor returns the in-order predecessor node of n, if any.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 20, "")
	rbts.Insert(tree, 10, "")
	node, _ := rbts.Search(tree, 20)
	pred, ok := rbts.Predecessor(node)
	if ok {
		fmt.Println(pred.Key())
	}
}

Output:

10

func Search[K cmp.Ordered, V any](t *Tree[K, V], key K) (*Node[K, V], bool)

Search finds a node with the given key in the red-black tree.

func Successor 

func Successor[K cmp.Ordered, V any](n *Node[K, V]) (*Node[K, V], bool)

Successor returns the in-order successor node of n, if any.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	rbts.Insert(tree, 20, "")
	rbts.Insert(tree, 30, "")
	node, _ := rbts.Search(tree, 20)
	succ, ok := rbts.Successor(node)
	if ok {
		fmt.Println(succ.Key())
	}
}

Output:

30

func (*Node[K, V]) Key 

func (n *Node[K, V]) Key() K

Key returns the key of the node.

func (*Node[K, V]) Value 

func (n *Node[K, V]) Value() V

Value returns the value of the node.

type Tree 

type Tree[K cmp.Ordered, V any] struct {
	Root *Node[K, V]
}

Tree represents the root of a red-black tree.

func New 

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

New returns a new empty Red-Black Tree.

Example 
package main

import (
	"fmt"

	rbts "github.com/byExist/redblacktrees"
)

func main() {
	tree := rbts.New[int, string]()
	fmt.Println(rbts.Len(tree))
}

Output:

0

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.