ds-red-black-tree-generic
rbtree/rbtree.go)The Red-Black tree is implemented using Go generics with a generic Node[K, V] and RBTree[K, V] type. The tree uses a sentinel nil node for all leaf references, avoiding nil pointer checks.
Key design decisions:
Generic key type — The tree accepts any key type K via a caller-provided comparison function cmp(a, b K) int, plus a convenience NewOrdered for types implementing a Less() method.
Sentinel nil node — Instead of using Go's nil, we use a sentinel *Node[K, V] with color = BLACK. All leaf pointers point to this sentinel, simplifying rotation and fixup logic.
Duplicate key handling — Insert first searches for an existing key; if found, it updates the value in place rather than creating a duplicate node. This keeps the tree size correct.
Insert fixup — Standard CLRS algorithm with 3 cases for each side (uncle red → recolor; uncle black + inner child → rotate to outer; uncle black + outer child → rotate grandparent).
Delete fixup — Standard CLRS algorithm with 4 cases per side, handling the 4 sibling-color/niece-color configurations that arise when a black node is removed.
Verification — Verify() checks all RB invariants: root is black, no red-red parent-child edges, and equal black-height across all paths.
// Red-Black tree invariants maintained:
// 1. Every node is either RED or BLACK
// 2. The root is always BLACK
// 3. Every leaf (sentinel nil) is BLACK
// 4. If a node is RED, both children are BLACK
// 5. For each node, all paths to descendant leaves have
// the same number of BLACK nodes
**All 15 tests pass** including race detection: | Test | What it verifies | |---|---| | `TestInsertAndSearch` | Basic insert + search correctness | | `TestMinMax` | Min/Max on empty and populated tree | | `TestInOrder` | In-order traversal produces sorted output | | `TestDelete` | Delete leaf, 1-child, 2-children, root, and non-existent key | | `TestVerifyEmptyTree` | Empty tree passes invariants | | `TestVerifySingleNode` | Single-node tree passes invariants | | `TestLargeRandom` | 1000 random inserts + deletes, Verify() after each mutation | | `TestStringKeys` | Works with `string` keys | | `TestDuplicateKeys` | Duplicate insert updates value, doesn't add duplicate nodes | | `TestKeysAndValues` | `Keys()` and `Values()` return sorted lists | | `TestDeleteAllEdgeCases` | Left-skewed and right-skewed sequential delete chains | | `TestUpdateValue` | Value updates preserve other keys | | `TestStructKeys` | Works with struct keys using custom comparator | | `TestDeleteWithDeepSuccessor` | Delete node where successor ≠ direct right child | | `TestNodeColors` | Root is always black after every insert | **Edge cases tested:** - Empty tree (Min/Max return false, Verify passes) - Single node (root is black, Verify passes) - Duplicate keys (value updated, no node duplication) - Left-skewed tree (all inserts go left; sequential delete from min to max) - Right-skewed tree (all inserts go right; sequential delete from max to min) - Delete where successor is NOT the direct right child (tests `y.parent != z` branch) - 1000 random inserts + deletes with `Verify()` after each operation - String keys and struct keys with custom comparators ---
{"model": "gpt-4o", "problem_class": "ds-red-black-tree-generic", "result": "passed", "tests": 15}