Generic left-leaning red-black tree implementation in Go.
package main
import "github.com/AnthonyLonsMax/rbtree"
func main() {
tree := rbtree.New(func(x, y int) int { return x - y })
tree.Add(5)
tree.Add(3)
tree.Add(7)
tree.Contains(5) // true
tree.Min() // 3
tree.Max() // 7
tree.Size() // 3
}| Operation | Description |
|---|---|
| Add | Insert element |
| Remove | Delete element |
| Contains | Check if element exists |
| Min / Max | Get smallest/largest element |
| DeleteMin / DeleteMax | Remove smallest/largest element |
| Floor / Ceil | Get closest element <= or >= value |
| Rank | Count elements less than value |
| Select | Get k-th smallest element (0-indexed) |
| Predecessor / Successor | Get element strictly < or > value |
| Size | Total element count |
| RangeSize | Count elements in range |
| Height | Number of levels in the tree |
| Clone | Deep copy of the tree |
| All / AllInv | Iterate all elements in ascending/descending order |
| Ceiled / Floored | Iterate elements greater than/less than value |
| Range / RangeInclusive | Iterate elements in range |
| ToSlice | Collect all elements as slice |
| IsEmpty | Check if tree is empty |
| Clear | Remove all elements |
Results from go test -benchmem -bench=. on an Intel Core i5-5200U @ 2.20GHz:
| Benchmark | Iterations | Time/op | Bytes/op | Allocs/op |
|---|---|---|---|---|
| All (10k elements) | 16,665 | 70,524 ns | 247 B | 4 |
| AllInv (10k elements) | 16,389 | 73,535 ns | 247 B | 4 |
| Ceiled [5000,] (10k elements) | 19,947 | 57,750 ns | 247 B | 4 |
| Floored [,5000) (10k elements) | 20,230 | 56,273 ns | 247 B | 4 |
| Range [1000,5000) (10k elements) | 23,718 | 51,295 ns | 240 B | 4 |
| RangeSize [1000,5000] (10k elements) | 7,490,719 | 150.4 ns | 0 B | 0 |
| Size (10k elements) | 1,000,000,000 | 0.55 ns | 0 B | 0 |
| Select [5000] (10k elements) | 25,866,837 | 44.32 ns | 0 B | 0 |
| Predecessor [5000] (10k elements) | 15,566,646 | 71.95 ns | 0 B | 0 |
| Successor [5000] (10k elements) | 15,081,792 | 70.90 ns | 0 B | 0 |
| Height (10k elements) | 10,000 | 111,562 ns | 0 B | 0 |
| Clone (10k elements) | 1,282 | 884,260 ns | 480,001 B | 10,000 |
| All (100k elements) | 793 | 1,461,083 ns | 503 B | 5 |
| Ceiled [50000,] (100k elements) | 1,359 | 900,379 ns | 247 B | 4 |
| Floored [,50000) (100k elements) | 1,575 | 842,623 ns | 503 B | 5 |
| Select [50000] (100k elements) | 17,782,222 | 73.90 ns | 0 B | 0 |
| Clone (100k elements) | 80 | 19,353,693 ns | 4,800,004 B | 100,000 |
| RangeSize [10000,50000] (100k elements) | 4,239,688 | 267.2 ns | 0 B | 0 |
All running times are in terms of n, the number of elements in the tree.
| Operation | Complexity | Notes |
|---|---|---|
| Add | O(log n) | Element insertion |
| Remove | O(log n) | Element deletion |
| Contains | O(log n) | Membership check |
| Min / Max | O(log n) | Follows left/right spine |
| DeleteMin / DeleteMax | O(log n) | Remove extreme elements |
| Floor / Ceil | O(log n) | Nearest value search |
| Rank | O(log n) | Count less than value |
| Select | O(log n) | k-th smallest element via childCount |
| Predecessor / Successor | O(log n) | Strictly previous/next element |
| Size | O(1) | Cached count, no traversal |
| Height | O(n) | Full tree walk |
| RangeSize | O(log n) | Uses rank, no iteration |
| Clone | O(n) | Deep copy, allocates all nodes |
| IsEmpty / Clear | O(1) | Root pointer check or nil |
| All / AllInv | O(n) | Full traversal, constant allocs |
| Ceiled / Floored | O(log n + k) | k = elements yielded, stops early |
| Range / RangeInclusive | O(log n + k) | k = elements in range, stops early |
| ToSlice | O(n) | Collects all elements |
The tree is a left-leaning red-black BST. Every lookup, insert, and delete walks at most one root-to-leaf path. For 10,000 elements that is ~14 comparisons; for 1,000,000 it is ~20. No operation reallocates per element during traversal — iterators use a fixed stack of pointers, so iterating 10, 10k, or 100k elements costs the same 4 allocations.
Examples:
- A
Containscheck on a tree with 1,000,000 elements costs about the same as on a tree with 1,000 elements — well under a microsecond. - Calling
Size()orIsEmpty()is free — just reads a cached field or a nil check, no tree walk. - Iterating all elements with
All()on a 10k tree takes ~71μs. The same iteration on a 100k tree takes ~1.4ms — linear, predictable, and allocation-free beyond the initial stack. - Range queries (
Range,Ceiled,Floored) only visit the nodes they need. Asking for the top 100 elements from a million-tree set costs about the same as from a thousand-tree set.