JRC.Collections.RedBlackTree 1.0.1

JRC.Collections.RedBlackTree

⚡ Blazing fast sorted collections with index access — what .NET should have been

🚀 30% less memory than Microsoft's SortedSet/SortedDictionary
📍 Index-based access on all collections — set[i], dict.GetAt(i), IndexOf()
⚡ O(log n) Insert/Remove for List operations
🎯 Duplicate support in sorted sets

The Problem

Ever needed to:

• Get the 5th element from a SortedSet<T>? You can't.
• Find the index of a key in SortedDictionary<K,V>? Impossible.
• Do fast Insert/Remove in the middle of a large List<T>? O(n) kills you.

Microsoft's collections force you to choose: sorted OR indexed. Not anymore.

Features

Installation

dotnet add package JRC.Collections.RedBlackTree

Available Classes

RedBlackTreeSet<T>

A sorted set with index access and duplicate support.

var set = new RedBlackTreeSet<Person>(
    allowDuplicates: true, 
    (a, b) => a.Age - b.Age);

set.Add(new Person("Alice", 30));
set.Add(new Person("Bob", 25));
set.Add(new Person("Charlie", 25)); // Same age = duplicate OK

var youngest = set[0];              // O(log n) - index access!
int index = set.IndexOf(bob);       // O(log n)
var aged25 = set.FindKeys(p => p.Age - 25); // All persons aged 25

RedBlackTreeSet<TItem, TSortKey>

Simplified API when sorting by a property.

var set = new RedBlackTreeSet<Person, int>(
    allowDuplicates: true,
    person => person.Age,           // Sort key extractor
    (a, b) => a - b);               // Key comparer

set.Add(new Person("Alice", 30));
var person = set.FindKey(30);       // Find by age directly
var range = set.FindRange(20, 30);  // All persons aged 20-30

RedBlackTreeDictionary<TKey, TValue>

A sorted dictionary with index access.

var dict = new RedBlackTreeDictionary<int, string>();
dict.Add(100, "hundred");
dict.Add(50, "fifty");
dict.Add(75, "seventy-five");

var middle = dict.GetAt(1);         // O(log n) - {75, "seventy-five"}
int idx = dict.IndexOfKey(75);      // O(log n) - returns 1
var removed = dict.RemoveAt(0);     // O(log n) - removes {50, "fifty"}

RedBlackTreeList<T>

A list with O(log n) insert/remove operations.

var list = new RedBlackTreeList<string>();

// Insert 1 million items at random positions? No problem.
for (int i = 0; i < 1_000_000; i++)
    list.Insert(random.Next(list.Count), $"item{i}");  // O(log n) each!

list.RemoveAt(500_000);  // O(log n)
var item = list[250_000]; // O(log n)

RedBlackTreeIndex<T>

The underlying engine behind RedBlackTreeList<T>. Use this directly if you need to build your own IList<T> implementation or want maximum control.

var index = new RedBlackTreeIndex<MyItem>();

// Add returns the internal nodeId - store it for O(log n) operations later
int nodeId = index.Add(new MyItem("data"));

// If your items track their own nodeId, you get O(log n) IndexOf
int position = index.IndexOf(nodeId);       // O(log n) with nodeId!
index.Remove(nodeId);                        // O(log n) direct removal

// Without nodeId, you can still find items (but O(n))
int foundNodeId = index.FindNodeId(item);   // O(n) scan

Pro tip: If your T stores its nodeId internally, like the default wrapper RedBlackTreeList<T> does, you can achieve O(log n) for all operations including IndexOf and Remove — something even LinkedList<T> can't do efficiently.

Linq support:

enumerable.ToRedBlackTreeList<T>(), enumerable.ToRedBlackTreeDictionary<TKey, TValue>(...), enumerable.ToRedBlackTreeSet<T>(...) and enumerable.ToRedBlackTreeSet<T, TSortedKey>(...) are provided since you are using System.Linq.

Benchmarks

Set vs SortedSet (.NET 8)

Dictionary vs SortedDictionary (.NET 8)

100,000 items, average of multiple runs

Memory Usage (1M items)

30% less memory thanks to page-based allocation with contiguous arrays instead of individual heap-allocated nodes.

Serialization:

• RedBlackTreeList<T>, RedBlackTreeDictionary<K, V>, RedBlackTreeSet<K> and RedBlackTreeSet<T, TSortedKey> are Binary serializable (even since .NET 8.0, where Microsoft's binary serialization is marked obsolete).
• RedBlackTreeList<T>, RedBlackTreeDictionary<K, V>, RedBlackTreeSet<K> and RedBlackTreeSet<T, TSortedKey> are XML serializable. Comparers and SortKeyProvider must be XML serializable too, or binary serializable (if RedBlackTypeSerializationInfo.SubObjectsBinarySerializationAllowed is true).
• RedBlackTreeList<T>, RedBlackTreeDictionary<K, V>, RedBlackTreeSet<K> are Newtonsoft.Json serializable. If custom comparers are used, or if RedBlackTreeSet<T, TSortedKey> needs to be serialized, use a converter like these ones.
• RedBlackTreeList<T>, RedBlackTreeDictionary<K, V>, RedBlackTreeSet<K> are System.Text.Json serializable. If custom comparers are used, or if RedBlackTreeSet<T, TSortedKey> needs to be serialized, use a converter like these ones.
• RedBlackTreeList<T>, RedBlackTreeDictionary<K, V>, RedBlackTreeSet<K> are MessagePack serializable. If custom comparers are used, or if RedBlackTreeSet<T, TSortedKey> needs to be serialized, use a converter like these ones.
• RedBlackTreeList<T>, RedBlackTreeDictionary<K, V>, RedBlackTreeSet<K> are Protobuf serializable. If custom comparers are used, or if RedBlackTreeSet<T, TSortedKey> needs to be serialized, use a converter like these ones.

ℹ️ Info: RedBlackTreeList<T> requires no comparer and is serializable in all formats without additional converters.

Technical Notes

This library is based on Microsoft's internal RBTree<K> class from System.Data, with significant improvements:

• Successor chain: O(1) enumeration via linked successor pointers (vs O(log n) tree traversal) for RedBlackTreeList<K> (and RedBlackTreeIndex<K>), and also RedBlackTreeDictionary<K, V>()
• Simplified API & Optimized Performance: Unlike Microsoft's shared RBTree<K> implementation used across multiple collection types, this library provides dedicated classes with specialized optimizations for each use case, resulting in cleaner APIs and better performance.

Node Structure

┌────────────────────────────────────────────┐
│ LeftId    (4 bytes)                        │
│ RightId   (4 bytes)                        │
│ ParentId  (4 bytes)                        │
│ LinkId    (4 bytes) ─► Successor or Next   │
│ SubTreeSize (4 bytes)                      │
│ Color     (1 byte)                         │
│ Value     (variable)                       │
└────────────────────────────────────────────┘

Acknowledgments

• Microsoft for their internal RBTree<K> implementation in System.Data which served as the foundation for this library
• Claude (Anthropic) — an excellent pair programming partner for algorithm design, optimization, and thorough testing

License

MIT License - see LICENSE for details.

Contributing

Issues and PRs welcome! If you find a bug or have a feature request, please open an issue.