redblacktree

package module
v1.2.1 Latest Latest
Warning

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

 Go to latest Published: Jun 29, 2025 License: MIT Imports: 4 Imported by: 0

README

redblacktree

Package redblacktree provides a generic, iterative golang implementation of a left-leaning red-black balanced search tree as described by Robert Sedgewick and Kevin Wayne in their book "Algorithms - Fourth Edition".

%%{ init: { 'flowchart': { 'curve': 'linear' } } }%%

flowchart TD
    root((5)):::BlackNode --- B((2)):::RedNode
    root((5)):::BlackNode --- C((7)):::BlackNode
    B((2)):::RedNode --- D((1)):::BlackNode
    B((2)):::RedNode --- E((3)):::BlackNode
    
    classDef RedNode fill:#d11111,stroke:#d11111,color:#ffffff
    classDef BlackNode fill:#000000,stroke:#000000,color:#ffffff
    classDef NilNode fill:#ffffff,stroke:#ffffff,color:#ffffff

Example

A short example how to use this module.

package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Create a new tree using the concrete types int and string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")
	rbt.Put(4, "four")
	rbt.Put(5, "five")

	// Search the tree using a key.
	result, ok := rbt.Get(3)
	if ok {
		fmt.Printf("Result: %v\n", result)
	} else {
		fmt.Println("Key not found.")
	}

	// Delete a key-value pair.
	rbt.Remove(3)
}

Usage

New

Constructor for instantiating a new RedBlackTree. Types for keys and values are declared using type parameters. The key type must satisfy the cmp/Ordered interface defined in the standard library.

Example
// New tree with key type int and value type string.
rbt := redblacktree.New[int, string]()
Get

Retrieve a value to a corresponding key from the tree. An additional bool value indicates if a value was found.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pair to the tree.
rbt.Put(1, "one")

// result == "one", ok == "true"
result, ok := rbt.Get(1)

// result == nil, ok == false
result, ok = rbt.Get(2)
Count

Count returns the total amount of key-value pairs stored in the tree.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pair to the tree.
rbt.Put(1, "one")

// c == 1
c := rbt.Count()
Contains

Checks if a given key exists in the tree by returning a bool value.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pair to the tree.
rbt.Put(1, "one")

// ok == true
ok := rbt.Contains(1)

// ok == false
ok = rbt.Contains(2)
Minimum

Minimum returns the value corresponding to the smallest key inside the tree. An additional bool value indicates if the tree is empty.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")

// result == "one", ok == true
result, ok := rbt.Minimum()
Maximum

Maximum returns the value corresponding to the largest key inside the tree. An additional bool value indicates if the tree is empty.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")

// result == "three", ok == true
result, ok := rbt.Maximum()
Predecessor

Predecessor returns the in-order predecessor of a given key. It also returns a bool value indicating if a predecessor could be found. The bool value is false if the given key is the smallest key in the tree or not present at all.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")
rbt.Put(4, "four")

// result == "two", ok == true
result, ok := rbt.Predecessor(3)
Successor

Successor returns the in-order successor of a given key. It also returns a bool value indicating if a successor could be found. The bool value is false if the given key is the largest key in the tree or not present at all.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")
rbt.Put(4, "four")

// result == "three", ok == true
result, ok := rbt.Successor(2)
Floor

Floor returns the largest key which is less or equal a given key and returns its values. It also returns a bool value indicating a key matching this condition was found in the tree.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(4, "four")

// result == "two", ok == true
result, ok := rbt.Floor(2)

// result == "two", ok == true
result, ok = rbt.Floor(3)
Ceil

Ceil returns the smallest key which is greater or equal a given key and returns its values. It also returns a bool value indicating a key matching this condition was found in the tree.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(4, "four")

// result == "two", ok == true
result, ok := rbt.Ceil(2)

// result == "four", ok == true
result, ok = rbt.Ceil(3)
Put

Put stores a key-value pair in the tree. It returns a bool value indicating if new key was inserted (true) or an already existing key was updated.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pair to the tree.
// ok == true
ok := rbt.Put(1, "one")
// ok == false
ok = rbt.Put(1, "one")
Remove

Remove removes a key-value pair from the tree. It returns a bool value indicating if a key could be deleted.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")

// ok == true
ok := rbt.Remove(1)

// ok == false
ok = rbt.Remove(1)
RemoveMinimum

RemoveMinimum deletes the key-value pair with the smallest key in the tree. It returns a bool value indicating if a key could be deleted.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")

// ok == true, "one" was removed from the tree
ok := rbt.RemoveMinimum()
RemoveMaximum

RemoveMaximum deletes the key-value pair with the largest key in the tree. It returns a bool value indicating if a key could be deleted.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")

// ok == true, "three" was removed from the tree
ok := rbt.RemoveMaximum()
All

All returns an iterator which can be used to loop over all key-value pairs in the tree.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")

// Output:
// key: 1, value: one
// key: 2, value: two
// key: 3, value: three
for key, value := range rbt.All() {
    fmt.Printf("key: %v, value: %v\n", key, value)
}
InOrderTraversal

InOrderTraversal performs an iterative inorder traversal on the tree by using a stack. A function can be passed to do operations on single key-value pairs while traversing the tree.

This example will count all keys (nodes) in the tree.

var counter *int = new(int)

// Function to use for the InOrderTraversal. 
f := func(i int, j string) {
    *counter++
}

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")

// counter == 3
rbt.InOrderTraversal(f)
GetRange

GetRange returns a slice of values determined by a lower and a higher key. If the desired range of keys are not present in the tree, the additional return value 'ok' is set to false.

// New tree
rbt := redblacktree.New[int, string]()

// Insert key-value pairs to the tree.
rbt.Put(1, "one")
rbt.Put(2, "two")
rbt.Put(3, "three")
rbt.Put(4, "four")
rbt.Put(5, "five")

// results == ["two", "three", "four"], ok == true
results, ok := rbt.GetRange(2, 4)

License

MIT

Documentation

Overview

Package redblacktree provides a generic, iterative golang implementation of a left-leaning red-black balanced search tree as described by Robert Sedgewick and Kevin Wayne in their book "Algorithms - Fourth Edition". The main goal of this package is to provide an easy to use, feature-rich and fast implementation of a red-black tree ready for use in all kind of applications.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type RedBlackTree 

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

func New 

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

New instantiates a new RedBlackTree.

func (*RedBlackTree[K, V]) All added in v1.2.0 

func (rbt *RedBlackTree[K, V]) All() iter.Seq2[K, V]

All returns an iterator which can be used to loop over all key-value pairs in the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	for key, value := range rbt.All() {
		fmt.Printf("key: %v, value: %v\n", key, value)
	}

}

Output:

key: 1, value: one
key: 2, value: two
key: 3, value: three

func (*RedBlackTree[K, V]) Ceil 

func (rbt *RedBlackTree[K, V]) Ceil(key K) (value V, ok bool)

Ceil returns the smallest value which is greater than or equal to a given key. It also returns a bool value indicating a key matching this condition was found in the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(4, "four")

	result, ok := rbt.Ceil(3)
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: four, ok: true

func (*RedBlackTree[K, V]) Contains 

func (rbt *RedBlackTree[K, V]) Contains(key K) (ok bool)

Contains returns true if a given key was found in the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pair to the tree.
	rbt.Put(1, "one")

	ok := rbt.Contains(1)
	fmt.Printf("ok: %v\n", ok)
}

Output:

ok: true
Example (NotFound) 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pair to the tree.
	rbt.Put(1, "one")

	ok := rbt.Contains(2)
	fmt.Printf("ok: %v\n", ok)
}

Output:

ok: false

func (*RedBlackTree[K, V]) Count 

func (rbt *RedBlackTree[K, V]) Count() int

Count returns the total amount of key-value pairs stored in the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pair to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	count := rbt.Count()

	fmt.Printf("count: %v\n", count)
}

Output:

count: 3

func (*RedBlackTree[K, V]) Floor 

func (rbt *RedBlackTree[K, V]) Floor(key K) (value V, ok bool)

Floor returns the largest value which is less than or equal to a given key. It also returns a bool value indicating a key matching this condition was found in the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(4, "four")

	result, ok := rbt.Floor(3)
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: two, ok: true

func (*RedBlackTree[K, V]) Get 

func (rbt *RedBlackTree[K, V]) Get(key K) (value V, ok bool)

Get returns the value to a corresponding key and an additional bool value indicating if a matching key was found. This mimics the behaviour of the built-in type 'map'.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pair to the tree.
	rbt.Put(1, "one")

	result, ok := rbt.Get(1)
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: one, ok: true
Example (NotFound) 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pair to the tree.
	rbt.Put(1, "one")

	result, ok := rbt.Get(2)
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: , ok: false

func (*RedBlackTree[K, V]) GetRange 

func (rbt *RedBlackTree[K, V]) GetRange(min, max K) (values []V, ok bool)

GetRange returns a slice of values determined by a lower and a higher key. If the desired range of keys are not present in the tree, the additional return value 'ok' is set to false.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")
	rbt.Put(4, "four")
	rbt.Put(5, "five")

	results, ok := rbt.GetRange(2, 4)

	fmt.Printf("results: %v, ok: %v\n", results, ok)
}

Output:

results: [two three four], ok: true

func (*RedBlackTree[K, V]) InOrderTraversal 

func (rbt *RedBlackTree[K, V]) InOrderTraversal(f func(K, V))

InOrderTraversal performs an iterative inorder traversal on the tree by using a stack. A function can be passed to do operations on single key-value pairs while traversing the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	var counter *int = new(int)

	// Function to use for the InOrderTraversal.
	f := func(i int, s string) {
		*counter++
	}

	rbt.InOrderTraversal(f)

	fmt.Printf("counter: %v\n", *counter)
}

Output:

counter: 3

func (*RedBlackTree[K, V]) Maximum 

func (rbt *RedBlackTree[K, V]) Maximum() (value V, ok bool)

Maximum returns the value corresponding to the largest key inside the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	result, ok := rbt.Maximum()
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: three, ok: true

func (*RedBlackTree[K, V]) Minimum 

func (rbt *RedBlackTree[K, V]) Minimum() (value V, ok bool)

Minimum returns the value corresponding to the smallest key inside the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	result, ok := rbt.Minimum()
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: one, ok: true

func (*RedBlackTree[K, V]) Predecessor added in v1.1.0 

func (rbt *RedBlackTree[K, V]) Predecessor(key K) (value V, ok bool)

Predecessor returns the in-order predecessor of a given key. It also returns a bool value indicating if a predecessor could be found. The bool value is false if the given key is the smallest key in the tree or not present at all.

Example

----------------------- Predecessor ----------------------- 

package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")
	rbt.Put(4, "four")

	result, ok := rbt.Predecessor(3)
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: two, ok: true

func (*RedBlackTree[K, V]) Put 

func (rbt *RedBlackTree[K, V]) Put(key K, value V) (inserted bool)

Put stores a key-value pair in the tree. It returns a bool value indicating if new key was inserted (true) or an already existing key was updated.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pair to the tree.
	inserted := rbt.Put(1, "one")

	fmt.Printf("inserted: %v\n", inserted)
}

Output:

inserted: true
Example (Update) 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pair to the tree.
	rbt.Put(1, "on")
	// Update existing key-value pair.
	inserted := rbt.Put(1, "one")

	fmt.Printf("inserted: %v\n", inserted)
}

Output:

inserted: false

func (*RedBlackTree[K, V]) Remove 

func (rbt *RedBlackTree[K, V]) Remove(key K) (ok bool)

Remove removes a key-value pair from the tree. It returns a bool value indicating if a key could be deleted.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	ok := rbt.Remove(1)
	fmt.Printf("ok: %v\n", ok)
}

Output:

ok: true

func (*RedBlackTree[K, V]) RemoveMaximum 

func (rbt *RedBlackTree[K, V]) RemoveMaximum() (ok bool)

RemoveMaximum deletes the key-value pair with the largest key in the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	ok := rbt.RemoveMaximum()
	fmt.Printf("ok: %v\n", ok)
}

Output:

ok: true

func (*RedBlackTree[K, V]) RemoveMinimum 

func (rbt *RedBlackTree[K, V]) RemoveMinimum() (ok bool)

RemoveMinimum deletes the key-value pair with the smallest key in the tree.

Example 
package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")

	ok := rbt.RemoveMinimum()
	fmt.Printf("ok: %v\n", ok)
}

Output:

ok: true

func (*RedBlackTree[K, V]) Successor added in v1.1.0 

func (rbt *RedBlackTree[K, V]) Successor(key K) (value V, ok bool)

Successor returns the in-order successor of a given key. It also returns a bool value indicating if a successor could be found. The bool value is false if the given key is the largest key in the tree or not present at all.

Example

----------------------- Successor ----------------------- 

package main

import (
	"fmt"
	"gitlab.com/baerlabs.dev/redblacktree"
)

func main() {
	// Instantiate a new red black tree with key type int and value type string.
	rbt := redblacktree.New[int, string]()

	// Insert key-value pairs to the tree.
	rbt.Put(1, "one")
	rbt.Put(2, "two")
	rbt.Put(3, "three")
	rbt.Put(4, "four")

	result, ok := rbt.Successor(2)
	fmt.Printf("result: %v, ok: %v\n", result, ok)
}

Output:

result: three, ok: true

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.