Weight-Balanced Trees and the Ratio That Bounds Depth

AVL and red-black trees define balance in terms of height. A third family defines it in terms of weight, where the weight of a node is the number of keys in its subtree. The invariant is that the two subtree weights of any node stay within a fixed ratio δ. Weight is a global property of a subtree rather than a local one, and that changes what the structure is good at: single-key updates become slightly more expensive to reason about, while split and join — operations that cut a tree at a key and concatenate two trees — become the natural primitives, and every other operation can be defined in terms of them.

The trade is worth understanding because it is the reason some functional language libraries, and the parallel ordered-set implementations derived from them, do not use red-black trees at all.

Why size is a usable balance measure

Height balance constrains depth directly: an AVL node whose subtree heights differ by at most one guarantees that no path is much longer than another. Weight balance constrains depth indirectly, through a counting argument. State the invariant with a ratio δ: for every node, neither subtree’s weight exceeds δ times the other’s. Then descending into the smaller subtree leaves at most a fraction δ/(δ + 1) of the parent’s weight behind, so the depth is at most log_{(δ+1)/δ} n, and the height constant is 1 / log₂((δ + 1)/δ).

That constant is a decreasing function of δ. At δ = 2 it is about 1.71, at δ = 3 about 2.41, at δ = 4 about 3.11. Small δ gives a tighter height bound but makes the invariant harder to restore: below a threshold that depends on how the invariant is stated, a single rotation can no longer repair a violation, and the implementation has to allow double rotations or larger rebalancing steps. The commonly used value is δ = 3, which keeps single rotations sufficient while staying within a factor of about 1.2 of the red-black bound of 2 log₂(n + 1).

The important structural difference from height balance is that weight is monotone. A rotation changes the weights of exactly two nodes and leaves the weights of all other nodes unchanged. Height, by contrast, changes for every ancestor when a leaf is added, which is why AVL trees must walk all the way up. With weights, a subtree’s weight changes only when its contents change, and a rotation’s effect on the two rotated nodes can be computed from the weights of the three subtrees involved, in constant time, with no upward walk needed to recompute anything.

The rotation condition in terms of weight

Consider a node x with left child y, and let a, b, c be the weights of y->left, y->right, and x->right. A right rotation makes y the parent with subtrees a and x, where x now has subtrees b and c. The weights are w(y) = a + b + 1 and w(x) = a + b + c + 2 before, and w(y) = a + b + c + 2, w(x) = b + c + 1 after.

The invariant requires that at y neither a nor b + c + 1 exceed δ times the other, and at x neither b nor c exceed δ times the other. Both conditions are linear inequalities in a, b, c, which means the decision to rotate is a comparison of three integers, not a comparison of computed heights. The implementation therefore stores one integer per node — the subtree size — and needs no height field, no balance factor, and no upward propagation of metadata.

data Tree a = Empty | Node a (Tree a) (Tree a)

-- Weight of a node; leaves are empty trees of weight 0.
size :: Tree a -> Int
size Empty        = 0
size (Node _ l r) = 1 + size l + size r

-- A tree is balanced when, for every node, neither subtree exceeds
-- delta times the other (delta = 3 gives the classic 1:3 ratio).
delta :: Int
delta = 3

balanced :: Tree a -> Bool
balanced Empty = True
balanced (Node _ l r) =
  let sl = size l
      sr = size r
  in sl <= delta * sr + 1 && sr <= delta * sl + 1
       && balanced l && balanced r

The + 1 in the test is not cosmetic. Without it, a node with one empty child and one single-node child has weights 0 and 1, the ratio is unbounded, and the invariant fails at the bottom of every tree. The constant term absorbs the discreteness of small subtrees; the asymptotic argument is unaffected by it.

Why a single rotation suffices

The claim that makes weight balance practical is that if a node violates the ratio, one rotation — or one double rotation, in the size analogue of the AVL case — restores it. The proof is a case analysis on the three weights, and the reason it works is that a rotation moves weight between the two nodes in proportion to the subtrees it moves.

Take x violating on the left: w(y) > δ · w(c). If y’s left subtree is the heavy one, a right rotation moves b from y to x, reducing the imbalance. If y’s right subtree is heavy, the rotation moves b to x and makes the new x heavier than the new y, so the violation moves rather than disappears; a left rotation about y first rearranges the weights so that the subsequent right rotation works. The double rotation is the size analogue of the AVL double rotation described in balance factors and deletion cascades.

The critical difference is what happens after the repair. A rotation restores the ratio at the two nodes it touches and leaves every other node’s weight unchanged, so no ancestor can be newly violated. Single- key insertion therefore needs at most one repair and no upward walk beyond the descent, and deletion needs at most one repair as well — unlike AVL, where deletion can cascade. This is the property that makes the structure attractive for functional implementations, where the repair must be expressed as a pure function returning a new path.

Join is the primitive, insert is derived

In a weight-balanced tree, join(l, k, r) takes two trees and a key known to lie between all keys of l and all keys of r, and returns a single tree. The algorithm descends the heavier tree, recursing on the appropriate side, and rebalances on the way back. Its cost is O(|h(l) − h(r)|) — proportional to the difference in heights, not to the size of either tree. For trees of comparable height it is O(log n); for a small tree joined to a large one it is proportional to the small tree’s height.

Insert reduces to join: split the tree at the new key, then join the two halves with the key in the middle. Delete reduces to split and join: split at the key, then join the two remaining halves. Split itself is O(log n) and produces two trees whose heights differ from the original by at most a logarithmic amount, because the recursion follows one path and each level does constant work.

This decomposition is what makes the structure parallelizable. A union of two sets can be computed by splitting one set at the root key of the other and recursing on the two halves, and the recursion tree has logarithmic depth, so the work parallelizes without the sequential dependency that a rotation-based insert has. The same two primitives give a merge of two trees in time proportional to the height difference, which is why the structure appears in libraries built around bulk set operations rather than single-key mutation.

Where the ratio choice bites

The parameter δ is not free, and the constraints on it come from three directions at once.

Too small a δ and single rotations cannot restore the invariant. There is a threshold below which a violating configuration requires more than one rotation to fix, and the threshold depends on whether the implementation allows double rotations and on how the invariant is stated with the constant term. Implementations that permit only single rotations must keep δ well above the threshold.

Too large a δ and the height bound degrades. At δ = 8 the bound is log_{9/8} n, about 5.9 log₂ n, worse than red-black. The useful window is narrow, roughly 2 to 4, and the choice inside it is a compromise between the tightness of the height bound and the ease of the rotation proof.

The third constraint is that the invariant must be preserved by join. Join can produce a node whose two subtree weights differ by an amount proportional to the height difference of the inputs, and the repair must reduce that to the ratio in one pass without re-descending. A ratio that is too tight leaves join producing violations that a single rotation cannot repair, so the requirement pulls in the opposite direction from the height bound. The practical window settles around a ratio of 2 to 3, which is the same constraint expressed as a minimum subtree fraction of about 0.29 — the form in which the parallel ordered-set implementations state it.

The cost relative to height-balanced trees

Weight-balanced trees store a full integer per node, where red-black trees store one bit. For a tree of a million 8-byte keys the metadata is a word per node against a packed bit, which is the difference described in the red-black colour bit. The extra word buys two things: a repair that never cascades, and split/join primitives that are O(log n) with a small constant.

The repair property is what matters for functional and persistent use. In a persistent tree every node on the update path is copied, so a repair that cascades to the root copies every level; a repair that stops after one rotation copies only the nodes above the repair point, which is still the whole path but with less restructuring work. The difference is a constant factor in allocation, not an asymptotic change, but allocation is often the dominant cost in that setting. Path copying in persistent trees develops the accounting.

For ephemeral in-memory use the extra word is a real cost with no compensating benefit unless the workload uses split or join, which most ordered-map workloads do not. That is the honest summary of the trade: weight balance is a specialized design that wins when the operations are bulk or functional, and loses slightly when they are single-key and ephemeral.