Dive C4.02.3

Balancing & immutability

The levels are the cost. Keep them near log n and a thousand keys take ten steps to reach.

The number of levels in a tree is the cost of a search. A balanced tree of n nodes has about log₂ n levels — seven nodes in three, a thousand in ten — so a lookup descends ten steps, not a thousand. But balance is not automatic for a hand-rolled search tree: insert 1, 2, 3, 4 in sorted order and every node hangs to the right, a chain as tall as the list is long, and search is O(n) again. F#'s own Map and Set close that gap — they are immutable, self-balancing search trees that stay O(log n) however the keys arrive. The EchoMQ schedule rides that balancing without a line of tree code of its own.

Compare the heights Module hub

C4.02.3 · part 1

A search descends one side per level

On a binary search tree, a lookup compares once per level and descends one side — O(height) work. The F# find below is the same two-clause-plus-guards shape as insert: at each Node it either matches, goes left, or goes right. Finding 20 in the seven-node tree visits 12 → 30 → 20 — three comparisons, one per level.

let rec find x t =
    match t with
    | Leaf -> false
    | Node(_, v, _) when x = v -> true
    | Node(l, v, _) when x < v -> find x l
    | Node(_, _, r) -> find x r

// find 20 tree -> true   (descends 12 -> 30 -> 20)
// find 99 tree -> false

The cost is the number of levels touched, not the number of nodes. That is the whole reason a tree can beat a list: a balanced tree of a thousand keys is about ten levels deep, so find does ten comparisons where a list would do up to a thousand.

Balanced height against degenerate height

Set the number of keys. The readout gives the height of a balanced tree of that many keys — ⌈log₂(n + 1)⌉ levels — against a degenerate chain of the same keys inserted in sorted order, which is n levels tall. The bars are the two heights; the gap is the difference between O(log n) and O(n) search.

Tree height · balanced vs degenerate

keys (n) 1000

n = 1000 · balanced height 10 (⌈log₂ 1001⌉) · degenerate height 1000 · a balanced lookup does 10 comparisons where the chain does up to 1000.

balanced: ⌈log₂(n+1)⌉ = 10 · degenerate: n = 1000

Without JavaScript: for n = 1000, a balanced tree is about ⌈log₂ 1001⌉ = 10 levels; the same keys inserted in sorted order form a chain of 1000 levels. Balanced search is O(log n); the chain is O(n).

The bars never converge as n grows — the balanced one creeps up by one level each time the keys double, while the chain climbs with every single key. That gap is the entire payoff of keeping a tree balanced.

C4.02.3 · part 2

A degenerate tree is a list in disguise

Insert 1, 2, 3, 4 in sorted order with the hand insert from C4.02.1 and every key is larger than the last, so each hangs on the right. The result is a right-leaning chain — a linked list wearing a tree's clothes — and height confirms it: four nodes, four levels.

let degenerate =
    [1; 2; 3; 4] |> List.fold (fun t x -> insert x t) Leaf

// height degenerate -> 4   (a right-leaning chain — O(n) search)

Same keys, two shapes · balanced vs degenerate

Insert 1, 2, 3, 4 in sorted order and the right-hand shape is what the hand BST produces. Self-balancing trees (AVL, red-black) rotate subtrees after each insert to keep the left-hand shape; the trie family later in this chapter goes wider still.

C4.02.3 · part 3

F#'s Map and Set are balanced for you

The hand BST shows the mechanics; in real F# the answer is built in. Map and Set are immutable, self-balancing binary search trees in FSharp.Core. They stay balanced however the keys arrive — including the sorted order that wrecks a hand BST — so insert, lookup, and delete are O(log n), and each update shares the untouched part of the tree, the structural sharing of C4.02.1.

// Map and Set stay balanced even on sorted insertion order:
let bigMap = Map.ofList [ for i in 1..100000 -> (i, i) ]
// Map.tryFind 73000 bigMap -> Some 73000   (O(log n), not O(n))

let s = Set.ofList [42; 5; 12; 8; 30; 10; 20]
// Set.toList s     -> [5; 8; 10; 12; 20; 30; 42]   in-order, sorted
// Set.minElement s -> 5                             the front of the order

On the CLR the nodes are heap-allocated reference objects, and a value type like int is boxed once as the key, so a Map carries more per-node overhead than a BEAM term. The asymptotics and the structural sharing match the Elixir course's account exactly; the constant factor is where the runtimes differ.

The idea

Cost is the number of levels; balance keeps that near log n, and losing it costs you O(n).

In F#

Map and Set self-balance on every insert, so the descent stays at log₂ n with no rebalancing to write.

C4.02.3 · the bus

EchoMQ in F# — the schedule self-balances

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

EchoMQ in F#

The F# EchoMQ relies on this balancing without writing a line of tree code. Its retry schedule, EchoMQ.Store.Schedule, is a Map<string, int64>; every park is a Schedule.Add, every promote a Map.filter over the same tree. Because the Map self-balances, those stay O(log n) and O(n) no matter the order jobs arrive in, and structural sharing means parking one job does not copy the rest of the schedule.

// echo_fs/EchoMQ/Store.fs — the schedule, a self-balancing Map
/// id -> due-at (ms): jobs parked until their run-at time.
Schedule: Map<string, int64>

The pending set, EchoMQ.Store.Pending, is a Set<string> — the same tree without values — and a claim takes its front with Set.minElement in mint order. Because branded ids are time-ordered and sort as the integers do, the front of the set is the oldest job; the Set's ordering gives the bus "byte order is mint order" with no second index.

// echo_fs/EchoMQ/Store.fs — claim takes the front of the ordered Set
let id = Set.minElement st.Pending

Today: the schedule and the pending set are in-memory Map and Set, built and tested, self-balanced by FSharp.Core. Coming soon: the Valkey transport (EchoMQ.Connector) moves the same ordered structures onto the wire behind the same surface.

Where this completes the module

That closes C4.02. The type dictates the recursion, the order of the recursion is the traversal, and balance keeps the descent at O(log n) — which F#'s Map and Set hand you for free, and the EchoMQ schedule rides. The next module, C4.03 — Sorting & searching, applies the same halving to a sorted sequence; later, C4.05 — HAMT takes the wide-branch route to the same goal.

↑ C4.02 · Trees & traversals ← C4.02.2 · Traversals C4 · Algorithms →

References

Sources

Microsoft — F# documentation — the Map and Set collections.
FSharp.Core API reference — the balanced-tree Map and Set modules.
Microsoft — .NET documentation — value vs reference types and boxing on the CLR.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — F4.02.3 Breadth-first & balance — the E4 sibling for balance and O(log n).
C4.02 — Trees & traversals — the module hub.
C4.02.1 — Binary trees — the recursive shape and structural sharing.
C4 — Algorithms & Data Structures — where C4.05 HAMT takes the wide-branch route.