Data Structures & AlgorithmsSelf-Balancing Trees in Practice

Self-Balancing Trees in Practice

LevelIntermediate

Duration60 mins

TopicSelf-Balancing Trees in Practice

1 / 4

Standard Library Implementations

Standing on the Shoulders of Giants

Throughout our journey exploring AVL trees, red-black trees, 2-3 trees, and B-trees, we've developed deep theoretical understanding of how these remarkable data structures achieve guaranteed O(log n) performance. We've traced rotations, verified invariants, and analyzed why each design decision matters.

Now comes the most practical question of all: How do we actually use balanced trees in production code?

The answer, in most cases, is surprisingly simple: you don't implement them yourself. Every major programming language provides battle-tested, highly optimized balanced tree implementations in its standard library. Understanding what's available—and how to leverage it effectively—is essential knowledge for any practicing software engineer.

What You Will Learn

By the end of this page, you will understand exactly which balanced tree implementations are available in C++, Java, Python, JavaScript/TypeScript, C#, Go, and Rust. You'll learn the specific tree types each language uses, their API patterns, performance characteristics, and the design philosophy behind each implementation.

Why Use Standard Library Implementations?

Before exploring specific implementations, let's establish why standard library balanced trees are almost always the right choice for production code. This isn't about laziness or avoiding work—it's about engineering wisdom.

The case for standard libraries is overwhelming:

Advantages of Standard Library Trees

•Decades of Testing — Standard library implementations have been tested by millions of developers across billions of applications. Edge cases that would take you months to discover have already been found and fixed.
•Performance Optimization — Library maintainers have spent thousands of hours optimizing these implementations. They understand CPU cache behavior, memory allocation patterns, and compiler optimizations that most developers never consider.
•Memory Safety — In languages with manual memory management (C++, Rust), standard library trees handle complex ownership, deallocation, and iterator invalidation scenarios correctly.
•Thread Safety Documentation — Each library clearly documents its concurrency guarantees. You know exactly what's safe and what requires external synchronization.
•API Stability — Standard library APIs are stable for decades. Code written 20 years ago using std::map still compiles and runs correctly today.
•Interoperability — Standard types are understood by all developers on your team, integrate with other library code, and work with debugging tools.

The Cost of Rolling Your Own

Implementing a correct, efficient balanced tree from scratch typically requires 500-2000 lines of careful code. More importantly, subtle bugs in balancing logic can go undetected for years—silently corrupting data or causing performance degradation only under specific workloads. Unless you have an extremely compelling reason, use the standard library.

C++ Standard Library: The Red-Black Foundation

C++ provides arguably the most comprehensive suite of balanced tree containers in any mainstream language. The C++ Standard Library uses red-black trees as the underlying implementation for its ordered associative containers—a choice that has stood the test of time since the 1990s.

Available Containers:

Container	Description	Key Characteristic
`std::set<T>`	Ordered set of unique elements	Keys only, no duplicates
`std::multiset<T>`	Ordered set allowing duplicates	Keys only, duplicates allowed
`std::map<K,V>`	Ordered key-value pairs, unique keys	Key-value, no duplicate keys
`std::multimap<K,V>`	Ordered key-value pairs, duplicate keys allowed	Key-value, duplicate keys allowed

cpp_balanced_trees.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <set>
#include <map>
#include <string>
 
int main() {
    // std::set - ordered unique elements
    std::set<int> orderedSet;
    orderedSet.insert(50);
    orderedSet.insert(30);
    orderedSet.insert(70);
    orderedSet.insert(30);  // Duplicate ignored
    
    // Iteration is always in sorted order: 30, 50, 70
    std::cout << "Set contents: ";
    for (int val : orderedSet) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    
    // O(log n) lookup
    if (orderedSet.find(50) != orderedSet.end()) {
        std::cout << "Found 50 in set" << std::endl;
    }
    
    // Range queries: elements in [30, 60)
    auto low = orderedSet.lower_bound(30);   // First >= 30
    auto high = orderedSet.lower_bound(60);  // First >= 60
    std::cout << "Elements in [30, 60): ";
    for (auto it = low; it != high; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // std::map - ordered key-value pairs
    std::map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    
    // Keys are always ordered alphabetically
    std::cout << "\nScores by name:" << std::endl;
    for (const auto& [name, score] : scores) {
        std::cout << "  " << name << ": " << score << std::endl;
    }
    
    // O(log n) lookup and modification
    scores["Bob"] += 5;  // Update existing
    
    // std::multiset - allows duplicates
    std::multiset<int> frequencies;
    frequencies.insert(5);
    frequencies.insert(5);
    frequencies.insert(5);
    frequencies.insert(3);
    
    std::cout << "\nCount of 5s: " << frequencies.count(5) << std::endl;
    
    return 0;
}

Key Implementation Details:

Red-Black Tree Internals: While the C++ standard doesn't mandate red-black trees specifically, in practice, every major implementation (GCC's libstdc++, LLVM's libc++, MSVC's STL) uses red-black trees. This choice balances insertion/deletion performance against lookup speed.
Node-Based Storage: Each element lives in its own heap-allocated node containing the element, color bit, and three pointers (parent, left child, right child). This means cache performance is worse than contiguous containers like std::vector, but enables stable iterators and O(1) element movement.
Custom Comparators: All ordered containers accept a comparison function as a template parameter:
```
std::set<int, std::greater<int>> descendingSet;  // Reverse order
```
Iterator Stability: Inserting or erasing elements never invalidates iterators to other elements. This is crucial for algorithms that modify the container while iterating.

C++ Ordered Container Complexity Guarantees
Operation	Time Complexity	Notes
insert()	O(log n)	Inserts element, maintains order
erase()	O(log n)	Removes element, rebalances tree
find()	O(log n)	Searches for element
lower_bound()	O(log n)	First element ≥ value
upper_bound()	O(log n)	First element > value
count()	O(log n + k)	Count of elements equal to value
operator[]	O(log n)	Map only: access/insert by key
begin(), end()	O(1)	Iterator access
size()	O(1)	Element count

Java Collections Framework: TreeMap and TreeSet

Java's Collections Framework provides TreeMap<K,V> and TreeSet<E> as its balanced tree implementations. Both are backed by red-black trees and implement the NavigableMap and NavigableSet interfaces respectively—providing rich APIs for range operations and ordered traversal.

The NavigableSet/NavigableMap APIs are particularly powerful, offering methods that many other languages' standard libraries lack:

JavaBalancedTrees.java
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.*;
 
public class JavaBalancedTrees {
    public static void main(String[] args) {
        // TreeSet - ordered unique elements
        TreeSet<Integer> orderedSet = new TreeSet<>();
        orderedSet.add(50);
        orderedSet.add(30);
        orderedSet.add(70);
        orderedSet.add(20);
        orderedSet.add(40);
        orderedSet.add(60);
        orderedSet.add(80);
        
        // Standard operations
        System.out.println("Set: " + orderedSet);  // [20, 30, 40, 50, 60, 70, 80]
        System.out.println("Contains 50: " + orderedSet.contains(50));  // O(log n)
        
        // NavigableSet-specific operations
        System.out.println("\nNavigable operations:");
        System.out.println("first(): " + orderedSet.first());        // 20 - smallest
        System.out.println("last(): " + orderedSet.last());          // 80 - largest
        System.out.println("lower(50): " + orderedSet.lower(50));    // 40 - greatest < 50
        System.out.println("floor(50): " + orderedSet.floor(50));    // 50 - greatest <= 50
        System.out.println("ceiling(50): " + orderedSet.ceiling(50)); // 50 - least >= 50
        System.out.println("higher(50): " + orderedSet.higher(50));  // 60 - least > 50
        
        // Range views - these are LIVE views backed by the original tree!
        System.out.println("\nRange views:");
        System.out.println("subSet(30, 70): " + orderedSet.subSet(30, 70));     // [30, 40, 50, 60]
        System.out.println("headSet(50): " + orderedSet.headSet(50));           // [20, 30, 40]
        System.out.println("tailSet(50): " + orderedSet.tailSet(50));           // [50, 60, 70, 80]
        
        // Descending iteration - no need to copy and sort!
        System.out.println("\nDescending order:");
        for (Integer val : orderedSet.descendingSet()) {
            System.out.print(val + " ");
        }
        System.out.println();
        
        // Polling operations - remove and return
        System.out.println("\nPolling:");
        System.out.println("pollFirst(): " + orderedSet.pollFirst()); // 20, removed
        System.out.println("pollLast(): " + orderedSet.pollLast());   // 80, removed
        System.out.println("After polling: " + orderedSet);           // [30, 40, 50, 60, 70]
        
        // TreeMap - ordered key-value pairs
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        scores.put("Diana", 88);
        scores.put("Eve", 91);
        
        System.out.println("\nTreeMap operations:");
        System.out.println("Scores: " + scores);
        System.out.println("firstKey(): " + scores.firstKey());       // Alice
        System.out.println("lastEntry(): " + scores.lastEntry());     // Eve=91
        
        // Range map view
        System.out.println("subMap(Bob, Diana): " + 
            scores.subMap("Bob", "Diana"));  // {Bob=87, Charlie=92}
        
        // Custom comparator - reverse alphabetical
        TreeMap<String, Integer> reverseScores = 
            new TreeMap<>(Comparator.reverseOrder());
        reverseScores.putAll(scores);
        System.out.println("\nReverse order: " + reverseScores);
    }
}

Live Range Views

Java's subSet(), headSet(), and tailSet() return live views backed by the original tree. Changes to the view reflect in the original, and vice versa. This is extremely powerful for algorithms that need to operate on ranges—you get O(log n) access to any range without copying data. However, it also means you must be careful: modifying the backing tree can invalidate range view iterators.

Thread Safety Considerations:

Java's TreeMap and TreeSet are not thread-safe by default. For concurrent access, you have several options:

External Synchronization: Wrap with Collections.synchronizedSortedMap() or Collections.synchronizedSortedSet(). However, these only synchronize individual method calls—compound operations still require explicit locking.
ConcurrentSkipListMap/Set: Java provides ConcurrentSkipListMap<K,V> and ConcurrentSkipListSet<E> in java.util.concurrent. These aren't trees—they use skip lists—but provide the same NavigableMap/NavigableSet APIs with full thread-safety and excellent concurrent performance.
Read-Write Locks: For read-heavy workloads, use ReentrantReadWriteLock to allow multiple concurrent readers.

Why Skip Lists for Concurrency?

Skip lists can be modified with localized locking (only the nodes being changed need locking), while tree rotations affect multiple nodes and require locking larger portions of the structure. This makes skip lists inherently more amenable to concurrent access.

Python's Approach: No Native Balanced Trees

Unlike C++ and Java, Python's standard library does not include a balanced tree implementation. This often surprises developers coming from other languages. Let's understand why, and what alternatives exist.

Python's Philosophy:

Python's standard library emphasizes simplicity and 'batteries included' for common use cases. The Python developers made a deliberate choice: for most use cases, dict (hash table) and list (dynamic array) are sufficient. When you need sorted data, they provide sorted() and the bisect module for binary search on sorted lists.

What Python Provides

•dict: O(1) average lookup, no ordering guarantee
•set: O(1) average membership test
•list + bisect: Binary search on sorted lists
•heapq: Min-heap via array representation
•collections.OrderedDict: Remembers insertion order (not sorted order)

What Python Lacks

•SortedSet: No native ordered set
•SortedDict: No native ordered dictionary
•Range Queries: No O(log n) range operations
•Predecessor/Successor: No floor/ceiling operations
•Ordered Iteration: Must sort manually

python_alternatives.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import bisect
from collections import OrderedDict
 
# Using bisect for binary search on sorted lists
# This gives O(log n) search but O(n) insert/delete
 
sorted_list = [10, 20, 30, 40, 50, 60, 70]
 
# Find insertion point for 35 (index where 35 would go)
pos = bisect.bisect_left(sorted_list, 35)
print(f"35 would be inserted at index {pos}")  # 3
 
# Find insertion point for 40 (existing element)
pos = bisect.bisect_left(sorted_list, 40)
print(f"40 found/inserted at index {pos}")  # 3
 
# Insert while maintaining sorted order - O(n) operation!
sorted_list_copy = sorted_list.copy()
bisect.insort(sorted_list_copy, 35)
print(f"After inserting 35: {sorted_list_copy}")  # [10, 20, 30, 35, 40, 50, 60, 70]
 
# Simulating floor/ceiling operations
def floor(sorted_list, x):
    """Find largest element <= x, or None if no such element"""
    pos = bisect.bisect_right(sorted_list, x) - 1
    return sorted_list[pos] if pos >= 0 else None
 
def ceiling(sorted_list, x):
    """Find smallest element >= x, or None if no such element"""
    pos = bisect.bisect_left(sorted_list, x)
    return sorted_list[pos] if pos < len(sorted_list) else None
 
print(f"Floor of 45: {floor(sorted_list, 45)}")     # 40
print(f"Ceiling of 45: {ceiling(sorted_list, 45)}") # 50
 
# Third-party library: sortedcontainers (highly recommended)
# pip install sortedcontainers
 
"""
from sortedcontainers import SortedList, SortedDict, SortedSet
 
# SortedList - O(log n) insert and delete!
sl = SortedList([50, 30, 70, 20, 40])
print(sl)  # SortedList([20, 30, 40, 50, 70])
 
sl.add(35)  # O(log n) insertion
sl.remove(30)  # O(log n) deletion
 
# Range queries
print(sl.irange(30, 60))  # Elements in [30, 60]
 
# SortedDict - ordered by keys
sd = SortedDict({'banana': 3, 'apple': 5, 'cherry': 1})
print(sd.peekitem(0))  # ('apple', 5) - smallest key
print(sd.peekitem(-1)) # ('cherry', 1) - largest key
 
# SortedSet - ordered unique elements  
ss = SortedSet([3, 1, 4, 1, 5, 9, 2, 6])
print(ss)  # SortedSet([1, 2, 3, 4, 5, 6, 9])
"""
 
print("\n=== Performance Comparison ===")
print("bisect + list:  O(log n) search, O(n) insert/delete")
print("sortedcontainers: O(log n) for all operations")
print("Recommend: Use sortedcontainers for production code")

The sortedcontainers Library

The sortedcontainers library (pip install sortedcontainers) is the de facto standard for sorted data structures in Python. It's pure Python (no C dependencies), thoroughly tested, and remarkably fast—often faster than C-extension alternatives due to its clever use of Python's list optimizations. It provides SortedList, SortedDict, and SortedSet with full O(log n) guarantees. Interestingly, it uses a 'sorted list of lists' design rather than trees, exploiting Python's C-optimized list operations.

JavaScript/TypeScript: Building Blocks Required

JavaScript, like Python, does not include balanced tree implementations in its standard library. The language provides Object, Map, Set, Array, and their weak variants, but nothing that maintains sorted order with O(log n) operations.

The JavaScript Standard Library Landscape:

Structure	Ordering	Lookup	Insert/Delete	Use Case
`Object`	None (historically)	O(1) avg	O(1) avg	Simple key-value, string keys
`Map`	Insertion order	O(1) avg	O(1) avg	Any key type, maintains insertion order
`Set`	Insertion order	O(1) avg	O(1) avg	Unique values, maintains insertion order
`Array`	Index-based	O(n)	O(n)	Ordered sequences, random access

Important Note: JavaScript's Map and Set maintain insertion order, not sorted order. This is a common point of confusion.

javascript_workarounds.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// Native JavaScript/TypeScript - no balanced trees
 
// Map maintains INSERTION order, not sorted order
const map = new Map<string, number>();
map.set("banana", 3);
map.set("apple", 5);
map.set("cherry", 1);
 
console.log([...map.keys()]); // ["banana", "apple", "cherry"] - insertion order!
 
// To get sorted iteration, you must sort manually - O(n log n)
const sortedKeys = [...map.keys()].sort();
console.log(sortedKeys); // ["apple", "banana", "cherry"]
 
// Binary search on sorted arrays (like Python's bisect)
function binarySearch<T>(arr: T[], target: T, compare: (a: T, b: T) => number): number {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = (left + right) >>> 1;
        if (compare(arr[mid], target) < 0) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
 
// Maintaining a sorted array - O(n) insert!
const sortedArray: number[] = [10, 20, 30, 40, 50];
const insertValue = 35;
const insertPos = binarySearch(sortedArray, insertValue, (a, b) => a - b);
sortedArray.splice(insertPos, 0, insertValue); // O(n) due to array shifting
console.log(sortedArray); // [10, 20, 30, 35, 40, 50]
 
// ============================================
// Third-party libraries for balanced trees
// ============================================
 
/*
Popular npm packages for balanced trees:
 
1. "functional-red-black-tree" - Immutable red-black tree
   npm install functional-red-black-tree
   
   import createRBTree from 'functional-red-black-tree';
   let tree = createRBTree<number, string>();
   tree = tree.insert(5, "five");
   tree = tree.insert(3, "three");
   console.log(tree.get(5)); // "five"
   
2. "avl" - AVL tree implementation
   npm install avl
   
   import AVLTree from 'avl';
   const tree = new AVLTree<number, string>();
   tree.insert(5, "five");
   tree.insert(3, "three");
   
3. "bintrees" - Red-black tree and binary trees
   npm install bintrees
   
   import { RBTree } from 'bintrees';
   const tree = new RBTree<number>((a, b) => a - b);
   tree.insert(5);
   tree.insert(3);
   tree.insert(7);
   console.log(tree.min()); // 3
   console.log(tree.max()); // 7
 
4. "sorted-btree" - B+ tree with TypeScript support
   npm install sorted-btree
   
   import BTree from 'sorted-btree';
   const tree = new BTree<number, string>();
   tree.set(5, "five");
   tree.set(3, "three");
   // Supports range queries!
   for (const [k, v] of tree.entriesRange(2, 6)) {
       console.log(k, v);
   }
*/
 
// For interview practice and learning, here's a minimal tree interface:
interface BalancedTree<K, V> {
    insert(key: K, value: V): void;
    delete(key: K): boolean;
    get(key: K): V | undefined;
    has(key: K): boolean;
    min(): [K, V] | undefined;
    max(): [K, V] | undefined;
    floor(key: K): [K, V] | undefined;    // largest key <= given
    ceiling(key: K): [K, V] | undefined;  // smallest key >= given
    range(low: K, high: K): Array<[K, V]>; // keys in [low, high]
    size: number;
}
 
console.log("JavaScript requires third-party libraries for balanced trees.");
console.log("Popular choices: functional-red-black-tree, avl, bintrees, sorted-btree");

Choosing a JavaScript Tree Library

When selecting a JavaScript balanced tree library, consider: (1) TypeScript support if using TS, (2) whether you need mutable or immutable operations (functional-red-black-tree is immutable, which is great for React/Redux but may have performance overhead), (3) specific operations needed (range queries, rank operations, etc.), and (4) maintenance activity of the package. The 'sorted-btree' package is particularly well-maintained and offers excellent TypeScript support with B+ tree semantics.

C# and .NET: SortedDictionary and SortedSet

.NET provides excellent balanced tree support through the System.Collections.Generic namespace. Like C++ and Java, .NET uses red-black trees for its sorted collections.

Available Types:

Type	Description	Underlying Structure
`SortedDictionary<TKey, TValue>`	Key-value pairs, sorted by key	Red-black tree
`SortedSet<T>`	Unique elements in sorted order	Red-black tree
`SortedList<TKey, TValue>`	Key-value pairs, sorted by key	Two synced arrays (not a tree!)

Important Distinction: SortedList<K,V> is not a tree—it maintains two synchronized arrays. It has O(n) insert/delete but O(1) indexed access and lower memory overhead. Use it when data changes rarely.

CSharpBalancedTrees.cs
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using System;
using System.Collections.Generic;
 
class BalancedTreesDemo
{
    static void Main()
    {
        // SortedSet<T> - ordered unique elements (red-black tree)
        var orderedSet = new SortedSet<int> { 50, 30, 70, 20, 40, 60, 80 };
        
        Console.WriteLine("SortedSet contents:");
        foreach (var item in orderedSet)
        {
            Console.Write($"{item} ");  // 20 30 40 50 60 70 80
        }
        Console.WriteLine();
        
        // Min and Max - O(log n) in .NET Core, O(1) in some implementations
        Console.WriteLine($"Min: {orderedSet.Min}");  // 20
        Console.WriteLine($"Max: {orderedSet.Max}");  // 80
        
        // GetViewBetween - range view (like Java's subSet)
        var rangeView = orderedSet.GetViewBetween(30, 60);
        Console.WriteLine("\nElements in [30, 60]:");
        foreach (var item in rangeView)
        {
            Console.Write($"{item} ");  // 30 40 50 60
        }
        Console.WriteLine();
        
        // Modifying the view modifies the original!
        rangeView.Add(35);
        Console.WriteLine($"After adding 35 to view: {string.Join(", ", orderedSet)}");
        
        // Set operations - all O(n) but tree-optimized
        var otherSet = new SortedSet<int> { 40, 50, 60, 90 };
        orderedSet.IntersectWith(otherSet);  // Modifies orderedSet in-place
        Console.WriteLine($"\nAfter intersection: {string.Join(", ", orderedSet)}");
        
        // SortedDictionary<TKey, TValue> - ordered key-value pairs
        var scores = new SortedDictionary<string, int>
        {
            ["Alice"] = 95,
            ["Bob"] = 87,
            ["Charlie"] = 92
        };
        
        Console.WriteLine("\nSortedDictionary:");
        foreach (var kvp in scores)
        {
            Console.WriteLine($"  {kvp.Key}: {kvp.Value}");
        }
        
        // First and last keys
        Console.WriteLine($"First key: {scores.Keys.First()}");  // Alice
        Console.WriteLine($"Last key: {scores.Keys.Last()}");    // Charlie
        
        // Custom comparer - reverse order
        var reverseSet = new SortedSet<int>(Comparer<int>.Create((a, b) => b - a));
        reverseSet.Add(3);
        reverseSet.Add(1);
        reverseSet.Add(4);
        Console.WriteLine($"\nReverse order: {string.Join(", ", reverseSet)}");  // 4, 3, 1
        
        // TryGetValue for safe lookup
        if (scores.TryGetValue("Bob", out int bobScore))
        {
            Console.WriteLine($"\nBob's score: {bobScore}");
        }
    }
}

.NET's GetViewBetween Caveat

.NET's GetViewBetween() returns a live view backed by the original tree, similar to Java. However, .NET enforces stricter bounds checking: if you try to add an element to the view that falls outside the view's range, it throws an ArgumentOutOfRangeException. This is different from Java, which allows it (the element simply won't appear in the subSet view). This strictness prevents subtle bugs but requires awareness.

Go: Pragmatic Simplicity, No Built-in Trees

Go exemplifies a minimalist philosophy in its standard library. Go does not provide balanced tree implementations. It offers map (hash table) and slices, and leaves sorted data structures to third-party packages or custom implementations.

Go's Standard Library Approach:

map[K]V: Hash table with O(1) average operations, no ordering
Slices: Dynamic arrays with O(n) insert/delete
sort package: Sorting slices, binary search on sorted slices
container/heap: Binary heap for priority queues
container/list: Doubly-linked list (not sorted)
container/ring: Circular list

Noticeably absent: Any tree-based sorted collection.

Why? Go's designers believe that simple data structures (maps, slices) solve 95% of real problems. For the 5% requiring sorted collections, they expect developers to either use third-party packages or implement purpose-built solutions that fit their exact needs.

go_workarounds.go
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package main
 
import (
    "fmt"
    "sort"
)
 
func main() {
    // Go's built-in map has NO ordering guarantees
    scores := map[string]int{
        "banana": 3,
        "apple":  5,
        "cherry": 1,
    }
    
    // Iteration order is RANDOM in Go maps!
    fmt.Println("Map iteration (random order):")
    for k, v := range scores {
        fmt.Printf("  %s: %d\n", k, v)
    }
    
    // To iterate in sorted order, extract keys and sort
    keys := make([]string, 0, len(scores))
    for k := range scores {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    
    fmt.Println("\nSorted iteration:")
    for _, k := range keys {
        fmt.Printf("  %s: %d\n", k, scores[k])
    }
    
    // Maintaining a sorted slice (O(n) insert)
    sortedNums := []int{10, 20, 30, 40, 50}
    target := 35
    
    // Binary search to find insertion point
    pos := sort.SearchInts(sortedNums, target)
    
    // Insert at position - O(n) due to shifting
    sortedNums = append(sortedNums[:pos], append([]int{target}, sortedNums[pos:]...)...)
    fmt.Printf("\nAfter inserting %d: %v\n", target, sortedNums)
    
    // Floor and ceiling operations
    nums := []int{10, 20, 30, 40, 50}
    key := 35
    
    // Ceiling: smallest >= key
    ceilIdx := sort.SearchInts(nums, key)
    if ceilIdx < len(nums) {
        fmt.Printf("Ceiling of %d: %d\n", key, nums[ceilIdx])
    }
    
    // Floor: largest <= key
    if ceilIdx > 0 && (ceilIdx >= len(nums) || nums[ceilIdx] != key) {
        fmt.Printf("Floor of %d: %d\n", key, nums[ceilIdx-1])
    }
    
    /* 
    Third-party packages for balanced trees:
    
    1. github.com/emirpasic/gods - Comprehensive data structures
       - RedBlackTree, AVLTree, BTree, TreeMap, TreeSet
       
       import "github.com/emirpasic/gods/trees/redblacktree"
       tree := redblacktree.NewWithIntComparator()
       tree.Put(5, "five")
       tree.Put(3, "three")
       value, found := tree.Get(5)
       
    2. github.com/petar/GoLLRB - Left-Leaning Red-Black Tree
       - Focuses on simplicity and correctness
       
    3. github.com/google/btree - B-tree implementation by Google
       - Excellent for large datasets, cache-friendly
       
       import "github.com/google/btree"
       tree := btree.New(32)  // degree 32
       tree.ReplaceOrInsert(IntItem(5))
    */
    
    fmt.Println("\nGo requires third-party packages for balanced trees.")
    fmt.Println("Recommended: github.com/emirpasic/gods or github.com/google/btree")
}
 
// For use with google/btree
type IntItem int
 
func (a IntItem) Less(b IntItem) bool {
    return a < b
}

Rust: B-Trees for Cache Efficiency

Rust takes a unique approach among systems programming languages: its standard library sorted collections use B-trees rather than red-black trees. This is a deliberate choice based on modern hardware characteristics.

Why B-Trees?

Rust's designers prioritized cache efficiency. Modern CPUs access memory in cache lines (typically 64 bytes). B-tree nodes store multiple keys contiguously, meaning a single cache miss loads many keys at once. Red-black trees, with one key per node scattered across memory, cause more cache misses for the same operations.

For n = 1 million elements:

Red-black tree: ~20 node accesses, ~20 potential cache misses
B-tree (degree 16): ~5 node accesses, ~5 potential cache misses

This makes Rust's B-tree collections significantly faster in practice than red-black tree equivalents would be.

rust_btree.rs
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
use std::collections::{BTreeMap, BTreeSet};
 
fn main() {
    // BTreeSet - ordered unique elements
    let mut ordered_set: BTreeSet<i32> = BTreeSet::new();
    ordered_set.insert(50);
    ordered_set.insert(30);
    ordered_set.insert(70);
    ordered_set.insert(20);
    ordered_set.insert(40);
    
    // Iteration is always sorted
    println!("BTreeSet contents:");
    for val in &ordered_set {
        print!("{} ", val);  // 20 30 40 50 70
    }
    println!();
    
    // O(log n) operations
    println!("Contains 50: {}", ordered_set.contains(&50));
    
    // Range queries - this is where B-trees shine!
    println!("\nElements in range [30, 60):");
    for val in ordered_set.range(30..60) {
        print!("{} ", val);  // 30 40 50
    }
    println!();
    
    // First and last
    println!("First: {:?}", ordered_set.first());  // Some(20)
    println!("Last: {:?}", ordered_set.last());    // Some(70)
    
    // Difference, intersection, union (returns iterators, no allocation!)
    let other_set: BTreeSet<i32> = [40, 50, 60, 90].into();
    
    println!("\nSet operations:");
    print!("Intersection: ");
    for val in ordered_set.intersection(&other_set) {
        print!("{} ", val);  // 40 50
    }
    println!();
    
    print!("Difference: ");
    for val in ordered_set.difference(&other_set) {
        print!("{} ", val);  // 20 30 70
    }
    println!();
    
    // BTreeMap - ordered key-value pairs
    let mut scores: BTreeMap<&str, i32> = BTreeMap::new();
    scores.insert("Alice", 95);
    scores.insert("Bob", 87);
    scores.insert("Charlie", 92);
    
    println!("\nBTreeMap:");
    for (name, score) in &scores {
        println!("  {}: {}", name, score);
    }
    
    // Entry API for efficient get-or-insert patterns
    scores.entry("Diana").or_insert(88);
    *scores.entry("Bob").or_insert(0) += 10;  // Bob is now 97
    
    println!("\nAfter updates:");
    for (name, score) in &scores {
        println!("  {}: {}", name, score);
    }
    
    // Range queries on map
    println!("\nScores from Alice to Charlie:");
    for (name, score) in scores.range("Alice"..="Charlie") {
        println!("  {}: {}", name, score);
    }
    
    // Pop operations (remove and return first/last)
    if let Some((first_key, first_val)) = scores.pop_first() {
        println!("\nPopped first: {} = {}", first_key, first_val);
    }
    
    // Custom ordering with wrapper type
    #[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
    struct ReverseInt(i32);
    
    impl ReverseInt {
        fn new(val: i32) -> Self {
            ReverseInt(-val)  // Negate for reverse ordering
        }
    }
    
    let mut reverse_set: BTreeSet<ReverseInt> = BTreeSet::new();
    reverse_set.insert(ReverseInt::new(1));
    reverse_set.insert(ReverseInt::new(3));
    reverse_set.insert(ReverseInt::new(2));
    
    // Iterates in reverse order: 3, 2, 1
    println!("\nReverse order:");
    for ReverseInt(neg_val) in &reverse_set {
        print!("{} ", -neg_val);
    }
    println!();
}

Rust's Zero-Cost Abstractions

Rust's set operations (intersection, difference, union, symmetric_difference) return lazy iterators, not new collections. This means a.intersection(&b) allocates nothing—it produces an iterator that computes results on demand. To materialize the result, you call .collect(). This follows Rust's philosophy of zero-cost abstractions: you only pay for what you use.

Rust BTreeMap/BTreeSet Complexity
Operation	Time Complexity	Notes
insert()	O(log n)	Returns Option with old value if key existed
remove()	O(log n)	Returns Option with removed value
get()	O(log n)	Returns Option reference
contains()	O(log n)	Membership test
first(), last()	O(log n)	Min/max access
range()	O(log n + k)	Iterator over range, k = result size
entry()	O(log n)	Get-or-insert pattern
len()	O(1)	Cached count

Summary: Navigating the Standard Library Landscape

We've surveyed balanced tree implementations across seven major languages. Here's the strategic overview:

Balanced Tree Standard Library Summary
Language	Sorted Dict	Sorted Set	Tree Type	Range Queries
C++	std::map	std::set	Red-black	lower_bound/upper_bound
Java	TreeMap	TreeSet	Red-black	subMap, headMap, tailMap
Python	—	—	None (use sortedcontainers)	—
JavaScript	—	—	None (use npm packages)	—
C#/.NET	SortedDictionary	SortedSet	Red-black	GetViewBetween
Go	—	—	None (use third-party)	—
Rust	BTreeMap	BTreeSet	B-tree	range() method

Key Takeaways

•C++, Java, and C# provide comprehensive balanced tree support with red-black tree implementations offering O(log n) for all core operations plus rich range query APIs.
•Rust chose B-trees for cache efficiency, a forward-thinking decision that often outperforms red-black trees on modern hardware.
•Python, JavaScript, and Go require third-party libraries for balanced tree functionality. This isn't a deficiency—it reflects different design philosophies prioritizing simplicity.
•Range queries are a crucial differentiator between hash-based and tree-based collections. If you need operations like 'find all users with scores between 80-90', trees are essential.
•Standard library trees are almost always the right choice for production code due to decades of testing, optimization, and API stability.

Page Complete

You now have a comprehensive map of balanced tree implementations across major programming languages. In the next page, we'll dive deep into the trade-offs between different tree types—helping you understand why each language made its specific implementation choices and how those choices affect your code.

1 / 4

Loading learning content...

Data Structures & AlgorithmsSelf-Balancing Trees in Practice

Self-Balancing Trees in Practice

LevelIntermediate

Duration60 mins

TopicSelf-Balancing Trees in Practice

1 / 4

Standard Library Implementations

Standing on the Shoulders of Giants

Now comes the most practical question of all: How do we actually use balanced trees in production code?

What You Will Learn

Why Use Standard Library Implementations?

The case for standard libraries is overwhelming:

Advantages of Standard Library Trees

•Decades of Testing — Standard library implementations have been tested by millions of developers across billions of applications. Edge cases that would take you months to discover have already been found and fixed.
•Performance Optimization — Library maintainers have spent thousands of hours optimizing these implementations. They understand CPU cache behavior, memory allocation patterns, and compiler optimizations that most developers never consider.
•Memory Safety — In languages with manual memory management (C++, Rust), standard library trees handle complex ownership, deallocation, and iterator invalidation scenarios correctly.
•Thread Safety Documentation — Each library clearly documents its concurrency guarantees. You know exactly what's safe and what requires external synchronization.
•API Stability — Standard library APIs are stable for decades. Code written 20 years ago using std::map still compiles and runs correctly today.
•Interoperability — Standard types are understood by all developers on your team, integrate with other library code, and work with debugging tools.

The Cost of Rolling Your Own

C++ Standard Library: The Red-Black Foundation

Available Containers:

Container	Description	Key Characteristic
`std::set<T>`	Ordered set of unique elements	Keys only, no duplicates
`std::multiset<T>`	Ordered set allowing duplicates	Keys only, duplicates allowed
`std::map<K,V>`	Ordered key-value pairs, unique keys	Key-value, no duplicate keys
`std::multimap<K,V>`	Ordered key-value pairs, duplicate keys allowed	Key-value, duplicate keys allowed

cpp_balanced_trees.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <set>
#include <map>
#include <string>
 
int main() {
    // std::set - ordered unique elements
    std::set<int> orderedSet;
    orderedSet.insert(50);
    orderedSet.insert(30);
    orderedSet.insert(70);
    orderedSet.insert(30);  // Duplicate ignored
    
    // Iteration is always in sorted order: 30, 50, 70
    std::cout << "Set contents: ";
    for (int val : orderedSet) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    
    // O(log n) lookup
    if (orderedSet.find(50) != orderedSet.end()) {
        std::cout << "Found 50 in set" << std::endl;
    }
    
    // Range queries: elements in [30, 60)
    auto low = orderedSet.lower_bound(30);   // First >= 30
    auto high = orderedSet.lower_bound(60);  // First >= 60
    std::cout << "Elements in [30, 60): ";
    for (auto it = low; it != high; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // std::map - ordered key-value pairs
    std::map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    
    // Keys are always ordered alphabetically
    std::cout << "\nScores by name:" << std::endl;
    for (const auto& [name, score] : scores) {
        std::cout << "  " << name << ": " << score << std::endl;
    }
    
    // O(log n) lookup and modification
    scores["Bob"] += 5;  // Update existing
    
    // std::multiset - allows duplicates
    std::multiset<int> frequencies;
    frequencies.insert(5);
    frequencies.insert(5);
    frequencies.insert(5);
    frequencies.insert(3);
    
    std::cout << "\nCount of 5s: " << frequencies.count(5) << std::endl;
    
    return 0;
}

Key Implementation Details:

Red-Black Tree Internals: While the C++ standard doesn't mandate red-black trees specifically, in practice, every major implementation (GCC's libstdc++, LLVM's libc++, MSVC's STL) uses red-black trees. This choice balances insertion/deletion performance against lookup speed.
Node-Based Storage: Each element lives in its own heap-allocated node containing the element, color bit, and three pointers (parent, left child, right child). This means cache performance is worse than contiguous containers like std::vector, but enables stable iterators and O(1) element movement.
Custom Comparators: All ordered containers accept a comparison function as a template parameter:
```
std::set<int, std::greater<int>> descendingSet;  // Reverse order
```
Iterator Stability: Inserting or erasing elements never invalidates iterators to other elements. This is crucial for algorithms that modify the container while iterating.

C++ Ordered Container Complexity Guarantees
Operation	Time Complexity	Notes
insert()	O(log n)	Inserts element, maintains order
erase()	O(log n)	Removes element, rebalances tree
find()	O(log n)	Searches for element
lower_bound()	O(log n)	First element ≥ value
upper_bound()	O(log n)	First element > value
count()	O(log n + k)	Count of elements equal to value
operator[]	O(log n)	Map only: access/insert by key
begin(), end()	O(1)	Iterator access
size()	O(1)	Element count

Java Collections Framework: TreeMap and TreeSet

The NavigableSet/NavigableMap APIs are particularly powerful, offering methods that many other languages' standard libraries lack:

JavaBalancedTrees.java
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.*;
 
public class JavaBalancedTrees {
    public static void main(String[] args) {
        // TreeSet - ordered unique elements
        TreeSet<Integer> orderedSet = new TreeSet<>();
        orderedSet.add(50);
        orderedSet.add(30);
        orderedSet.add(70);
        orderedSet.add(20);
        orderedSet.add(40);
        orderedSet.add(60);
        orderedSet.add(80);
        
        // Standard operations
        System.out.println("Set: " + orderedSet);  // [20, 30, 40, 50, 60, 70, 80]
        System.out.println("Contains 50: " + orderedSet.contains(50));  // O(log n)
        
        // NavigableSet-specific operations
        System.out.println("\nNavigable operations:");
        System.out.println("first(): " + orderedSet.first());        // 20 - smallest
        System.out.println("last(): " + orderedSet.last());          // 80 - largest
        System.out.println("lower(50): " + orderedSet.lower(50));    // 40 - greatest < 50
        System.out.println("floor(50): " + orderedSet.floor(50));    // 50 - greatest <= 50
        System.out.println("ceiling(50): " + orderedSet.ceiling(50)); // 50 - least >= 50
        System.out.println("higher(50): " + orderedSet.higher(50));  // 60 - least > 50
        
        // Range views - these are LIVE views backed by the original tree!
        System.out.println("\nRange views:");
        System.out.println("subSet(30, 70): " + orderedSet.subSet(30, 70));     // [30, 40, 50, 60]
        System.out.println("headSet(50): " + orderedSet.headSet(50));           // [20, 30, 40]
        System.out.println("tailSet(50): " + orderedSet.tailSet(50));           // [50, 60, 70, 80]
        
        // Descending iteration - no need to copy and sort!
        System.out.println("\nDescending order:");
        for (Integer val : orderedSet.descendingSet()) {
            System.out.print(val + " ");
        }
        System.out.println();
        
        // Polling operations - remove and return
        System.out.println("\nPolling:");
        System.out.println("pollFirst(): " + orderedSet.pollFirst()); // 20, removed
        System.out.println("pollLast(): " + orderedSet.pollLast());   // 80, removed
        System.out.println("After polling: " + orderedSet);           // [30, 40, 50, 60, 70]
        
        // TreeMap - ordered key-value pairs
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        scores.put("Diana", 88);
        scores.put("Eve", 91);
        
        System.out.println("\nTreeMap operations:");
        System.out.println("Scores: " + scores);
        System.out.println("firstKey(): " + scores.firstKey());       // Alice
        System.out.println("lastEntry(): " + scores.lastEntry());     // Eve=91
        
        // Range map view
        System.out.println("subMap(Bob, Diana): " + 
            scores.subMap("Bob", "Diana"));  // {Bob=87, Charlie=92}
        
        // Custom comparator - reverse alphabetical
        TreeMap<String, Integer> reverseScores = 
            new TreeMap<>(Comparator.reverseOrder());
        reverseScores.putAll(scores);
        System.out.println("\nReverse order: " + reverseScores);
    }
}

Live Range Views

Thread Safety Considerations:

Java's TreeMap and TreeSet are not thread-safe by default. For concurrent access, you have several options:

External Synchronization: Wrap with Collections.synchronizedSortedMap() or Collections.synchronizedSortedSet(). However, these only synchronize individual method calls—compound operations still require explicit locking.
ConcurrentSkipListMap/Set: Java provides ConcurrentSkipListMap<K,V> and ConcurrentSkipListSet<E> in java.util.concurrent. These aren't trees—they use skip lists—but provide the same NavigableMap/NavigableSet APIs with full thread-safety and excellent concurrent performance.
Read-Write Locks: For read-heavy workloads, use ReentrantReadWriteLock to allow multiple concurrent readers.

Why Skip Lists for Concurrency?

Python's Approach: No Native Balanced Trees

Python's Philosophy:

What Python Provides

•dict: O(1) average lookup, no ordering guarantee
•set: O(1) average membership test
•list + bisect: Binary search on sorted lists
•heapq: Min-heap via array representation
•collections.OrderedDict: Remembers insertion order (not sorted order)

What Python Lacks

•SortedSet: No native ordered set
•SortedDict: No native ordered dictionary
•Range Queries: No O(log n) range operations
•Predecessor/Successor: No floor/ceiling operations
•Ordered Iteration: Must sort manually

python_alternatives.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import bisect
from collections import OrderedDict
 
# Using bisect for binary search on sorted lists
# This gives O(log n) search but O(n) insert/delete
 
sorted_list = [10, 20, 30, 40, 50, 60, 70]
 
# Find insertion point for 35 (index where 35 would go)
pos = bisect.bisect_left(sorted_list, 35)
print(f"35 would be inserted at index {pos}")  # 3
 
# Find insertion point for 40 (existing element)
pos = bisect.bisect_left(sorted_list, 40)
print(f"40 found/inserted at index {pos}")  # 3
 
# Insert while maintaining sorted order - O(n) operation!
sorted_list_copy = sorted_list.copy()
bisect.insort(sorted_list_copy, 35)
print(f"After inserting 35: {sorted_list_copy}")  # [10, 20, 30, 35, 40, 50, 60, 70]
 
# Simulating floor/ceiling operations
def floor(sorted_list, x):
    """Find largest element <= x, or None if no such element"""
    pos = bisect.bisect_right(sorted_list, x) - 1
    return sorted_list[pos] if pos >= 0 else None
 
def ceiling(sorted_list, x):
    """Find smallest element >= x, or None if no such element"""
    pos = bisect.bisect_left(sorted_list, x)
    return sorted_list[pos] if pos < len(sorted_list) else None
 
print(f"Floor of 45: {floor(sorted_list, 45)}")     # 40
print(f"Ceiling of 45: {ceiling(sorted_list, 45)}") # 50
 
# Third-party library: sortedcontainers (highly recommended)
# pip install sortedcontainers
 
"""
from sortedcontainers import SortedList, SortedDict, SortedSet
 
# SortedList - O(log n) insert and delete!
sl = SortedList([50, 30, 70, 20, 40])
print(sl)  # SortedList([20, 30, 40, 50, 70])
 
sl.add(35)  # O(log n) insertion
sl.remove(30)  # O(log n) deletion
 
# Range queries
print(sl.irange(30, 60))  # Elements in [30, 60]
 
# SortedDict - ordered by keys
sd = SortedDict({'banana': 3, 'apple': 5, 'cherry': 1})
print(sd.peekitem(0))  # ('apple', 5) - smallest key
print(sd.peekitem(-1)) # ('cherry', 1) - largest key
 
# SortedSet - ordered unique elements  
ss = SortedSet([3, 1, 4, 1, 5, 9, 2, 6])
print(ss)  # SortedSet([1, 2, 3, 4, 5, 6, 9])
"""
 
print("\n=== Performance Comparison ===")
print("bisect + list:  O(log n) search, O(n) insert/delete")
print("sortedcontainers: O(log n) for all operations")
print("Recommend: Use sortedcontainers for production code")

The sortedcontainers Library

JavaScript/TypeScript: Building Blocks Required

The JavaScript Standard Library Landscape:

Structure	Ordering	Lookup	Insert/Delete	Use Case
`Object`	None (historically)	O(1) avg	O(1) avg	Simple key-value, string keys
`Map`	Insertion order	O(1) avg	O(1) avg	Any key type, maintains insertion order
`Set`	Insertion order	O(1) avg	O(1) avg	Unique values, maintains insertion order
`Array`	Index-based	O(n)	O(n)	Ordered sequences, random access

Important Note: JavaScript's Map and Set maintain insertion order, not sorted order. This is a common point of confusion.

javascript_workarounds.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// Native JavaScript/TypeScript - no balanced trees
 
// Map maintains INSERTION order, not sorted order
const map = new Map<string, number>();
map.set("banana", 3);
map.set("apple", 5);
map.set("cherry", 1);
 
console.log([...map.keys()]); // ["banana", "apple", "cherry"] - insertion order!
 
// To get sorted iteration, you must sort manually - O(n log n)
const sortedKeys = [...map.keys()].sort();
console.log(sortedKeys); // ["apple", "banana", "cherry"]
 
// Binary search on sorted arrays (like Python's bisect)
function binarySearch<T>(arr: T[], target: T, compare: (a: T, b: T) => number): number {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = (left + right) >>> 1;
        if (compare(arr[mid], target) < 0) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
 
// Maintaining a sorted array - O(n) insert!
const sortedArray: number[] = [10, 20, 30, 40, 50];
const insertValue = 35;
const insertPos = binarySearch(sortedArray, insertValue, (a, b) => a - b);
sortedArray.splice(insertPos, 0, insertValue); // O(n) due to array shifting
console.log(sortedArray); // [10, 20, 30, 35, 40, 50]
 
// ============================================
// Third-party libraries for balanced trees
// ============================================
 
/*
Popular npm packages for balanced trees:
 
1. "functional-red-black-tree" - Immutable red-black tree
   npm install functional-red-black-tree
   
   import createRBTree from 'functional-red-black-tree';
   let tree = createRBTree<number, string>();
   tree = tree.insert(5, "five");
   tree = tree.insert(3, "three");
   console.log(tree.get(5)); // "five"
   
2. "avl" - AVL tree implementation
   npm install avl
   
   import AVLTree from 'avl';
   const tree = new AVLTree<number, string>();
   tree.insert(5, "five");
   tree.insert(3, "three");
   
3. "bintrees" - Red-black tree and binary trees
   npm install bintrees
   
   import { RBTree } from 'bintrees';
   const tree = new RBTree<number>((a, b) => a - b);
   tree.insert(5);
   tree.insert(3);
   tree.insert(7);
   console.log(tree.min()); // 3
   console.log(tree.max()); // 7
 
4. "sorted-btree" - B+ tree with TypeScript support
   npm install sorted-btree
   
   import BTree from 'sorted-btree';
   const tree = new BTree<number, string>();
   tree.set(5, "five");
   tree.set(3, "three");
   // Supports range queries!
   for (const [k, v] of tree.entriesRange(2, 6)) {
       console.log(k, v);
   }
*/
 
// For interview practice and learning, here's a minimal tree interface:
interface BalancedTree<K, V> {
    insert(key: K, value: V): void;
    delete(key: K): boolean;
    get(key: K): V | undefined;
    has(key: K): boolean;
    min(): [K, V] | undefined;
    max(): [K, V] | undefined;
    floor(key: K): [K, V] | undefined;    // largest key <= given
    ceiling(key: K): [K, V] | undefined;  // smallest key >= given
    range(low: K, high: K): Array<[K, V]>; // keys in [low, high]
    size: number;
}
 
console.log("JavaScript requires third-party libraries for balanced trees.");
console.log("Popular choices: functional-red-black-tree, avl, bintrees, sorted-btree");

Choosing a JavaScript Tree Library

C# and .NET: SortedDictionary and SortedSet

.NET provides excellent balanced tree support through the System.Collections.Generic namespace. Like C++ and Java, .NET uses red-black trees for its sorted collections.

Available Types:

Type	Description	Underlying Structure
`SortedDictionary<TKey, TValue>`	Key-value pairs, sorted by key	Red-black tree
`SortedSet<T>`	Unique elements in sorted order	Red-black tree
`SortedList<TKey, TValue>`	Key-value pairs, sorted by key	Two synced arrays (not a tree!)

CSharpBalancedTrees.cs
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using System;
using System.Collections.Generic;
 
class BalancedTreesDemo
{
    static void Main()
    {
        // SortedSet<T> - ordered unique elements (red-black tree)
        var orderedSet = new SortedSet<int> { 50, 30, 70, 20, 40, 60, 80 };
        
        Console.WriteLine("SortedSet contents:");
        foreach (var item in orderedSet)
        {
            Console.Write($"{item} ");  // 20 30 40 50 60 70 80
        }
        Console.WriteLine();
        
        // Min and Max - O(log n) in .NET Core, O(1) in some implementations
        Console.WriteLine($"Min: {orderedSet.Min}");  // 20
        Console.WriteLine($"Max: {orderedSet.Max}");  // 80
        
        // GetViewBetween - range view (like Java's subSet)
        var rangeView = orderedSet.GetViewBetween(30, 60);
        Console.WriteLine("\nElements in [30, 60]:");
        foreach (var item in rangeView)
        {
            Console.Write($"{item} ");  // 30 40 50 60
        }
        Console.WriteLine();
        
        // Modifying the view modifies the original!
        rangeView.Add(35);
        Console.WriteLine($"After adding 35 to view: {string.Join(", ", orderedSet)}");
        
        // Set operations - all O(n) but tree-optimized
        var otherSet = new SortedSet<int> { 40, 50, 60, 90 };
        orderedSet.IntersectWith(otherSet);  // Modifies orderedSet in-place
        Console.WriteLine($"\nAfter intersection: {string.Join(", ", orderedSet)}");
        
        // SortedDictionary<TKey, TValue> - ordered key-value pairs
        var scores = new SortedDictionary<string, int>
        {
            ["Alice"] = 95,
            ["Bob"] = 87,
            ["Charlie"] = 92
        };
        
        Console.WriteLine("\nSortedDictionary:");
        foreach (var kvp in scores)
        {
            Console.WriteLine($"  {kvp.Key}: {kvp.Value}");
        }
        
        // First and last keys
        Console.WriteLine($"First key: {scores.Keys.First()}");  // Alice
        Console.WriteLine($"Last key: {scores.Keys.Last()}");    // Charlie
        
        // Custom comparer - reverse order
        var reverseSet = new SortedSet<int>(Comparer<int>.Create((a, b) => b - a));
        reverseSet.Add(3);
        reverseSet.Add(1);
        reverseSet.Add(4);
        Console.WriteLine($"\nReverse order: {string.Join(", ", reverseSet)}");  // 4, 3, 1
        
        // TryGetValue for safe lookup
        if (scores.TryGetValue("Bob", out int bobScore))
        {
            Console.WriteLine($"\nBob's score: {bobScore}");
        }
    }
}

.NET's GetViewBetween Caveat

Go: Pragmatic Simplicity, No Built-in Trees

Go's Standard Library Approach:

map[K]V: Hash table with O(1) average operations, no ordering
Slices: Dynamic arrays with O(n) insert/delete
sort package: Sorting slices, binary search on sorted slices
container/heap: Binary heap for priority queues
container/list: Doubly-linked list (not sorted)
container/ring: Circular list

Noticeably absent: Any tree-based sorted collection.

go_workarounds.go
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package main
 
import (
    "fmt"
    "sort"
)
 
func main() {
    // Go's built-in map has NO ordering guarantees
    scores := map[string]int{
        "banana": 3,
        "apple":  5,
        "cherry": 1,
    }
    
    // Iteration order is RANDOM in Go maps!
    fmt.Println("Map iteration (random order):")
    for k, v := range scores {
        fmt.Printf("  %s: %d\n", k, v)
    }
    
    // To iterate in sorted order, extract keys and sort
    keys := make([]string, 0, len(scores))
    for k := range scores {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    
    fmt.Println("\nSorted iteration:")
    for _, k := range keys {
        fmt.Printf("  %s: %d\n", k, scores[k])
    }
    
    // Maintaining a sorted slice (O(n) insert)
    sortedNums := []int{10, 20, 30, 40, 50}
    target := 35
    
    // Binary search to find insertion point
    pos := sort.SearchInts(sortedNums, target)
    
    // Insert at position - O(n) due to shifting
    sortedNums = append(sortedNums[:pos], append([]int{target}, sortedNums[pos:]...)...)
    fmt.Printf("\nAfter inserting %d: %v\n", target, sortedNums)
    
    // Floor and ceiling operations
    nums := []int{10, 20, 30, 40, 50}
    key := 35
    
    // Ceiling: smallest >= key
    ceilIdx := sort.SearchInts(nums, key)
    if ceilIdx < len(nums) {
        fmt.Printf("Ceiling of %d: %d\n", key, nums[ceilIdx])
    }
    
    // Floor: largest <= key
    if ceilIdx > 0 && (ceilIdx >= len(nums) || nums[ceilIdx] != key) {
        fmt.Printf("Floor of %d: %d\n", key, nums[ceilIdx-1])
    }
    
    /* 
    Third-party packages for balanced trees:
    
    1. github.com/emirpasic/gods - Comprehensive data structures
       - RedBlackTree, AVLTree, BTree, TreeMap, TreeSet
       
       import "github.com/emirpasic/gods/trees/redblacktree"
       tree := redblacktree.NewWithIntComparator()
       tree.Put(5, "five")
       tree.Put(3, "three")
       value, found := tree.Get(5)
       
    2. github.com/petar/GoLLRB - Left-Leaning Red-Black Tree
       - Focuses on simplicity and correctness
       
    3. github.com/google/btree - B-tree implementation by Google
       - Excellent for large datasets, cache-friendly
       
       import "github.com/google/btree"
       tree := btree.New(32)  // degree 32
       tree.ReplaceOrInsert(IntItem(5))
    */
    
    fmt.Println("\nGo requires third-party packages for balanced trees.")
    fmt.Println("Recommended: github.com/emirpasic/gods or github.com/google/btree")
}
 
// For use with google/btree
type IntItem int
 
func (a IntItem) Less(b IntItem) bool {
    return a < b
}

Rust: B-Trees for Cache Efficiency

Why B-Trees?

For n = 1 million elements:

Red-black tree: ~20 node accesses, ~20 potential cache misses
B-tree (degree 16): ~5 node accesses, ~5 potential cache misses

This makes Rust's B-tree collections significantly faster in practice than red-black tree equivalents would be.

rust_btree.rs
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
use std::collections::{BTreeMap, BTreeSet};
 
fn main() {
    // BTreeSet - ordered unique elements
    let mut ordered_set: BTreeSet<i32> = BTreeSet::new();
    ordered_set.insert(50);
    ordered_set.insert(30);
    ordered_set.insert(70);
    ordered_set.insert(20);
    ordered_set.insert(40);
    
    // Iteration is always sorted
    println!("BTreeSet contents:");
    for val in &ordered_set {
        print!("{} ", val);  // 20 30 40 50 70
    }
    println!();
    
    // O(log n) operations
    println!("Contains 50: {}", ordered_set.contains(&50));
    
    // Range queries - this is where B-trees shine!
    println!("\nElements in range [30, 60):");
    for val in ordered_set.range(30..60) {
        print!("{} ", val);  // 30 40 50
    }
    println!();
    
    // First and last
    println!("First: {:?}", ordered_set.first());  // Some(20)
    println!("Last: {:?}", ordered_set.last());    // Some(70)
    
    // Difference, intersection, union (returns iterators, no allocation!)
    let other_set: BTreeSet<i32> = [40, 50, 60, 90].into();
    
    println!("\nSet operations:");
    print!("Intersection: ");
    for val in ordered_set.intersection(&other_set) {
        print!("{} ", val);  // 40 50
    }
    println!();
    
    print!("Difference: ");
    for val in ordered_set.difference(&other_set) {
        print!("{} ", val);  // 20 30 70
    }
    println!();
    
    // BTreeMap - ordered key-value pairs
    let mut scores: BTreeMap<&str, i32> = BTreeMap::new();
    scores.insert("Alice", 95);
    scores.insert("Bob", 87);
    scores.insert("Charlie", 92);
    
    println!("\nBTreeMap:");
    for (name, score) in &scores {
        println!("  {}: {}", name, score);
    }
    
    // Entry API for efficient get-or-insert patterns
    scores.entry("Diana").or_insert(88);
    *scores.entry("Bob").or_insert(0) += 10;  // Bob is now 97
    
    println!("\nAfter updates:");
    for (name, score) in &scores {
        println!("  {}: {}", name, score);
    }
    
    // Range queries on map
    println!("\nScores from Alice to Charlie:");
    for (name, score) in scores.range("Alice"..="Charlie") {
        println!("  {}: {}", name, score);
    }
    
    // Pop operations (remove and return first/last)
    if let Some((first_key, first_val)) = scores.pop_first() {
        println!("\nPopped first: {} = {}", first_key, first_val);
    }
    
    // Custom ordering with wrapper type
    #[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
    struct ReverseInt(i32);
    
    impl ReverseInt {
        fn new(val: i32) -> Self {
            ReverseInt(-val)  // Negate for reverse ordering
        }
    }
    
    let mut reverse_set: BTreeSet<ReverseInt> = BTreeSet::new();
    reverse_set.insert(ReverseInt::new(1));
    reverse_set.insert(ReverseInt::new(3));
    reverse_set.insert(ReverseInt::new(2));
    
    // Iterates in reverse order: 3, 2, 1
    println!("\nReverse order:");
    for ReverseInt(neg_val) in &reverse_set {
        print!("{} ", -neg_val);
    }
    println!();
}

Rust's Zero-Cost Abstractions

Rust BTreeMap/BTreeSet Complexity
Operation	Time Complexity	Notes
insert()	O(log n)	Returns Option with old value if key existed
remove()	O(log n)	Returns Option with removed value
get()	O(log n)	Returns Option reference
contains()	O(log n)	Membership test
first(), last()	O(log n)	Min/max access
range()	O(log n + k)	Iterator over range, k = result size
entry()	O(log n)	Get-or-insert pattern
len()	O(1)	Cached count

Summary: Navigating the Standard Library Landscape

We've surveyed balanced tree implementations across seven major languages. Here's the strategic overview:

Balanced Tree Standard Library Summary
Language	Sorted Dict	Sorted Set	Tree Type	Range Queries
C++	std::map	std::set	Red-black	lower_bound/upper_bound
Java	TreeMap	TreeSet	Red-black	subMap, headMap, tailMap
Python	—	—	None (use sortedcontainers)	—
JavaScript	—	—	None (use npm packages)	—
C#/.NET	SortedDictionary	SortedSet	Red-black	GetViewBetween
Go	—	—	None (use third-party)	—
Rust	BTreeMap	BTreeSet	B-tree	range() method

Key Takeaways

•C++, Java, and C# provide comprehensive balanced tree support with red-black tree implementations offering O(log n) for all core operations plus rich range query APIs.
•Rust chose B-trees for cache efficiency, a forward-thinking decision that often outperforms red-black trees on modern hardware.
•Python, JavaScript, and Go require third-party libraries for balanced tree functionality. This isn't a deficiency—it reflects different design philosophies prioritizing simplicity.
•Range queries are a crucial differentiator between hash-based and tree-based collections. If you need operations like 'find all users with scores between 80-90', trees are essential.
•Standard library trees are almost always the right choice for production code due to decades of testing, optimization, and API stability.

Page Complete

1 / 4