A balanced tree keeps its height shallow through structural organization. Here, balanced trees support persistent vectors: updates copy only the changed leaf, root, and connecting path while sharing other nodes. section 12.1
The demonstrated design has these practical properties:
- Uses 32-way branching and leaves containing up to 32 values, producing very shallow trees. section 12.1
- Modifies persistent vectors by copying the path from an element to the root rather than copying the entire structure. section 12.1
- Takes O(log n) time for element modification while behaving almost constantly in practice because the tree remains shallow. section 12.1
- Extends to Relaxed Radix Balanced Trees, which support concatenation and insertion at O(log n) rather than O(n). section 12.1
Persistent vector update
A vector such as [:a :b :c] can be updated with (assoc [:a :b :c] 2 :d), producing [:a :b :d] while retaining structural sharing internally. section 12.1
