This document explains why this library uses weight-balanced trees instead of the more common red-black trees (used by Clojure's sorted-map) or AVL trees (used by data.avl).
Weight-balanced trees have a distinguished lineage in functional programming, powering Haskell's Data.Set and Data.Map, MIT Scheme's wt-tree, and several other persistent collection libraries. This isn't an accident — their structure is uniquely suited to functional programming's needs.
In this library, that split/join structure also serves as the extensibility boundary: one shared tree implementation supports generic, primitive-specialized, and augmented variants by varying the comparator and node constructor.
Red-black trees maintain balance through a coloring invariant: no root-to-leaf path has more than twice as many nodes as any other. This gives O(log n) operations with low constant factors.
Strengths:
Weaknesses:
nth, rank) and split-at-by-index are not natural parts of the representationAVL trees maintain strict height balance: the heights of left and right subtrees differ by at most 1. This creates slightly shorter trees than red-black, giving marginally faster lookups.
Strengths:
nth operationWeaknesses:
r/fold falls back to sequential reduceWeight-balanced trees maintain balance based on subtree sizes: using the Hirai-Yamamoto parameters (δ=3, γ=2), no subtree's weight can exceed 3× its sibling's weight. This seemingly simple invariant unlocks powerful capabilities.
Strengths:
nth, rank, median, percentilefirst/last via SortedSet interfaceWeaknesses:
The defining advantage of weight-balanced trees is efficient split and join:
split(tree, key) → (left, present?, right)
join(left, key, value, right) → tree
Both operations run in O(log n) time. Adams (1992) showed that given just these two primitives, you can implement union, intersection, and difference as simple recursive algorithms:
union(T₁, T₂):
if T₁ is empty: return T₂
if T₂ is empty: return T₁
let (k, v) = root(T₂)
let (L₁, _, R₁) = split(T₁, k)
return join(union(L₁, left(T₂)), k, v, union(R₁, right(T₂)))
This divide-and-conquer structure has two remarkable properties:
Work-optimality: The total work is O(m log(n/m + 1)) where m ≤ n are the set sizes. This is information-theoretically optimal — it matches the lower bound for comparison-based set operations. When one set is much smaller than the other, this is significantly better than generic element-wise set-algebra paths over ordered collections.
Low span: The two recursive calls are independent and can execute in parallel. Blelloch, Ferizovic, and Sun (2016) proved the span is O(log² n), giving near-linear speedup on many cores.
Split and join are efficient for weight-balanced trees because the balance invariant is based on sizes, and sizes compose trivially: size(join(L, k, R)) = size(L) + 1 + size(R). After a split or join, we know the exact sizes of all subtrees without any recomputation.
Compare with red-black trees, where a join must reconcile potentially incompatible color invariants at the junction point. Or AVL trees, where heights must be recomputed bottom-up. In both cases, the auxiliary balance information doesn't compose as cleanly.
Every node in a weight-balanced tree stores its subtree size. This is not auxiliary overhead — it is the balance invariant. And it enables operations that other tree types cannot provide efficiently:
To find the i-th element, compare i against the left subtree's size and recurse:
(def s (ordered-set (range 1000000)))
(nth s 500000) ;=> 500000 O(log n)
(rank-of s 500000) ;=> 500000 O(log n)
Red-black trees have no size information, so nth requires O(n) traversal. AVL trees can add cached sizes (as data.avl does), but it's bolted on rather than inherent to the balance scheme.
Because sizes are tracked, we can split a tree at a position (not just a key):
(split-at 3 (ordered-set [10 20 30 40 50]))
;=> [#{10 20 30} #{40 50}]
This is the foundation for parallel fold: split the tree into roughly equal halves, reduce each in parallel, combine results.
The weight-balanced structure supports augmentation: storing additional per-node aggregates that are maintained during rotations. This library uses augmentation to build:
Interval trees: Each node stores the maximum right endpoint in its subtree. This enables O(log n + k) overlap queries ("what intervals contain point p?").
Segment trees: Each node stores an aggregate (sum, max, min) over its subtree. This enables O(log n) range queries ("what's the sum from key a to key b?").
Augmentation works naturally with weight-balanced trees because rotations update a fixed number of nodes, and the aggregate at each node is a function of its children's aggregates. The same approach is harder with red-black trees, where color changes can propagate unpredictably.
The PAM framework (Sun, Ferizovic, Blelloch 2018) formalized this: any augmented map where the augment is a monoid over subtree values can be maintained in O(log n) per update, and the full suite of split/join/union/intersection operations carries augmentation through automatically.
The ability to efficiently split trees enables true parallel reduction:
(require '[clojure.core.reducers :as r])
(r/fold + (ordered-set (range 500000)))
The tree is split into larger balanced chunks, and those chunks are reduced in parallel via r/fold. In this library, CollFold is implemented explicitly by eager chunking with node-split and a minimum chunk-size floor of 4096, so fold only enters the parallel regime when splitting overhead is worth paying. Clojure's sorted-set and data.avl do not provide an equivalent tree-aware CollFold implementation here, so they effectively remain sequential in these benchmarks.
In these measurements, parallel fold is about 9.7x faster than sorted-set and 3.4x faster than data.avl at N=500K.
Weight-balanced trees use two parameters, traditionally called δ (delta) and γ (gamma):
The balance condition is:
weight(left) + 1 ≤ δ × (weight(right) + 1)
weight(right) + 1 ≤ δ × (weight(left) + 1)
This ensures a height bound of O(log n) — specifically, height ≤ log_{δ/(δ-1)} n = log_{3/2} n ≈ 1.71 log₂ n.
Adams' original work left the choice of δ and γ somewhat informal. Different implementations used different values, and some combinations led to subtle correctness bugs — trees that could become unbalanced after certain deletion sequences.
Hirai and Yamamoto (2011) resolved this definitively using the Coq proof assistant. They proved that (δ=3, γ=2) is the unique integer parameter pair that guarantees:
Kazu Yamamoto subsequently patched MIT Scheme and SLIB to use these parameters.
Weight-balanced trees are competitive with red-black and AVL trees on basic operations (lookup, insert, iteration) and significantly faster on operations that leverage split/join.
Weight-balanced trees have a rich history spanning five decades:
Nievergelt and Reingold introduced "binary search trees of bounded balance" (BB[α] trees). The key insight: balance based on subtree sizes rather than heights. This predates red-black trees (Guibas & Sedgewick, 1978) by six years.
Stephen Adams revolutionized the use of weight-balanced trees for functional programming:
join as the single balancing-scheme-specific operation from which all set operations derive.Adams showed that weight-balanced trees need only one balancing-scheme-specific function (join) to implement all set operations. His divide-and-conquer algorithms for union, intersection, and difference became the standard approach in functional languages.
Adams' work directly influenced several major implementations:
Haskell containers (Data.Set, Data.Map): The de facto standard collections in Haskell. From the source: "The implementation is based on size balanced binary trees as described by Stephen Adams."
MIT Scheme wt-tree (mid-1980s onwards): One of the earliest production implementations, providing a comprehensive API for sets and maps. The MIT Scheme Reference Manual notes: "Weight-balanced binary trees have several advantages over the other data structures for large aggregates."
FSet (Common Lisp and Java): Scott Burson's functional collections library uses "an evolution of Stephen Adams' weight-balanced binary trees," providing heterogeneous collections with correct ordering-collision handling.
SLIB (Scheme): Aubrey Jaffer's portable Scheme library includes weight-balanced trees as a core data structure.
Hirai and Yamamoto resolved the balance parameter question definitively in "Balancing Weight-Balanced Trees" (Journal of Functional Programming, 2011). Using the Coq proof assistant, they proved that (δ=3, γ=2) is the unique integer solution for correct balancing. Kazu Yamamoto patched MIT Scheme and SLIB accordingly.
Blelloch, Ferizovic, and Sun published "Just Join for Parallel Ordered Sets" (SPAA 2016), proving that Adams' algorithms are both work-optimal — O(m log(n/m + 1)) — and highly parallel — O(log² n) span. Their PAM library demonstrates 45x+ speedup on 64 cores.
Sun, Ferizovic, and Blelloch followed with "PAM: Parallel Augmented Maps" (PPoPP 2018), showing that the same join-based framework extends to augmented trees (interval trees, segment trees, range trees) while preserving work-optimality and parallelism.
These papers vindicated Adams' 1992 design: the elegant join-based approach wasn't just beautiful — it was optimal.
The pattern is clear: when functional programmers need ordered collections, they reach for weight-balanced trees. Why?
As the MIT Scheme manual puts it: "Weight-balanced binary trees have several advantages over the other data structures for large aggregates... The implementation is functional rather than imperative."
Nievergelt, J. & Reingold, E. (1972). "Binary Search Trees of Bounded Balance". SIAM Journal of Computing 2(1).
Adams, S. (1992). "Implementing Sets Efficiently in a Functional Language". Technical Report CSTR 92-10, University of Southampton.
Adams, S. (1993). "Efficient sets — a balancing act". Journal of Functional Programming 3(4):553-562.
Hirai, Y. & Yamamoto, K. (2011). "Balancing Weight-Balanced Trees". Journal of Functional Programming 21(3):287-307.
Blelloch, G., Ferizovic, D., & Sun, Y. (2016). "Just Join for Parallel Ordered Sets". ACM SPAA.
Sun, Y., Ferizovic, D., & Blelloch, G. (2018). "PAM: Parallel Augmented Maps". ACM PPoPP.
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |