Source-linked AI summary
Dynamically optimal weight-balanced binary search trees
John Iacono, Akash Pareek
TL;DR
The paper asks what search time is achievable by rotation-based BSTs that preserve weight balance, a setting whose optimal behavior had not been characterized. It derives a closed-form optimum and presents the PopTree, which matches that bound for sufficiently long sequences. The result establishes dynamic optimality within the balanced-tree class, not for unrestricted BSTs.
Problem
The best running time achievable by rotation-based BSTs that maintain a balance invariant had not been characterized, despite the study of dynamic optimality for general BSTs.
Source: §1 · pp. 1–2Method
The paper derives matching lower and upper bounds for BB[α] trees and constructs the rotation-based PopTree using a promotion-and-repair skip-list representation.
Source: §1 · p. 2, Lower bound · p. 3, Upper bound · p. 4Results
For sequences of length Ω(n log n), the PopTree runs in O(OPT(X)) time and is within a constant factor of the offline optimum for any constant α in the stated range.
Source: §1 · p. 2, Lower bound · p. 3Takeaways & Limitations
Within the BB[α] class, the paper characterizes when maintaining balance is sufficient and when performance may require leaving that class.
Source: §1 · p. 2The guarantee is for search sequences of length Ω(n log n), and the algorithm model requires the BB[α] invariant to hold throughout execution.
Source: §1 · p. 2, §2.3 · p. 9
Abstract
from arXiv · showhide
In STOC 1972, J{\"{u}}rg Nievergelt and Edward M.~Reingold introduced the $BB[\alpha]$-tree, also known as a \emph{weight-balanced} tree, which for any $\alpha \in (0,\frac{1}{2}]$ is a binary search tree where every node with induced subtree size $s$ has children with induced subtree sizes at least $\alpha(s+1)-1$. A new rotation-based binary search tree, the \emph{PopTree}, is introduced. The PopTree stores $n$ elements and is a $BB[\tfrac1{20}]$-tree after the execution of each search and a $BB[\tfrac1{729}]$-tree at all times, notably while rebalancing. For any constant $\alpha$, its performance on search sequences of length $\Omega(n \log n)$ is proved to be within a constant factor (which can depend on $\alpha$) of the optimal offline rotation-based binary search tree that maintains the $BB[\alpha]$ balance invariant.
1 Introduction
The paper characterizes the optimal running time of rotation-based BSTs that maintain the BB[α] balance invariant, introducing a new bound and the PopTree. Its results establish a matching lower and upper bound for sufficiently long search sequences and connect the structure to key-independent optimality.
1.1 Related work
- The paper frames its contribution as characterizing the best rotation-based BSTs under a balance invariant, a question distinct from maintaining the invariant itself.The unrestricted dynamic optimality conjecture remains open, while balanced skip lists and B-trees have related dynamic-optimality results.Source: §1 · p. 1, §1.1 · pp. 4, 6
Lower bound.
- The new OPT bound characterizes the asymptotic running time of offline optimal BB[α] trees and charges for recent searches near the current key and for keys near either extreme.The paper contrasts this with general rotation-based BST bounds, which reward key-space locality [ST85, DIL¨O13].Source: §1 · pp. 2–3, Lower bound · p. 3
- The PopTree runs in O(OPT(X)) time on sequences of length Ω(n log n), matching the lower bound for BB[α]-algorithms and making it dynamically optimal within that class.The lower-bound constant depends on α; the guarantee applies to any constant α in the stated range.Source: §1 · p. 2, Lower bound · p. 3
Upper bound.
- PopTree is presented as a skip list whose promotion of the searched item is followed by promotions and demotions restoring invariants; conversion via a B-tree yields a BB[1/20]-tree after each operation.BB[1/729] is needed only during transient states in the middle of an execution.Source: Upper bound · pp. 3–4
- Under a random bijection of keys, expected OPT is asymptotically equal to the working-set bound, making PopTrees key-independently optimal.The paper further concludes that BB[α] trees suffice for key-independent optimality.Source: Upper bound · p. 4, §1.1 · p. 6
1.1 Related work
- Unlike the working-set bound for balanced skip lists, the BB[α]-tree optimum penalizes recent searches near a key and includes a cost for items near the minimum or maximum.The PopTree’s promotion-based design takes inspiration from those skip-list structures.Source: Lower bound · p. 3, §1.1 · p. 6
2 Lower Bound
The section proves a lower bound of Ω(OPT(X)) for BB[α]-tree algorithms and develops the depth, level, and marking arguments used to establish it.
2.1 Depth lemmas
- Depth lemmas show that items near the extremes must be deep and that, for any two distinct items, at least one is deep relative to their key distance.These bounds follow from subtree weights and the balance condition.Source: §2.1 · p. 7
2.2 Levels
- The level definition tracks subtree weight, differs from depth by at most a constant factor, and gives a key-distance threshold for when one of two items must have high level.Levels change locally under rotations, unlike depths.Source: §2.2 · p. 8
2.3 Algorithm
- The algorithm model charges unit-cost pointer moves and rotations, requires touching each searched item, and requires the tree to remain BB[α]-balanced at all times.The set A records each operation together with the pointed-to item and its level, so its size equals execution cost.Source: §2.3 · p. 9
2.4 Levels and algorithm
- A pointer must touch every level below the searched item's level, while an item's level changes only through rotations involving that item.The level can decrease only in unit steps, so crossing a level entails a touch there.Source: §2.4 · pp. 9–10
2.5 Previous search
- For a repeated search, previ(r) denotes the most recent earlier search within key distance r; it is no earlier than the previous search of that same item.The definition is used for searches that are not the item's first occurrence.Source: §2.5 · p. 10
2.6 Marking scheme
- For i ∈ notFirst and nonnegative ℓ with xprevi(γ(ℓ)) ≠ xi, each pair marks a touch in A; no touch receives more than four marks, yielding a lower bound on |A| and algorithm execution time.Source: §2.6 · pp. 10–12
- Every BB[α]-tree algorithm, including offline algorithms, requires Ω(OPT(X)) time, with the constant depending on α.The marking argument bounds execution time through touched tree levels.Source: §2.6 · pp. 12–13
3 Upper Bound
The upper bound constructs a self-adjusting SkipPopList and transforms it into the PopTree through an intermediate multiway search tree. Its cost is tied to OPT(X), while the transformations preserve balance.
3 Upper Bound
- The SkipPopList-to-PopTree construction gives a BB[1/729]-algorithm with O(OPT(X)) running time for search sequences of length Ω(n log n).The conversion proceeds through the intermediate PopBTree.Source: §3 · p. 14, §3.1 · p. 17
3.1 SkipPopList
- SkipPopList levels partition keys into buckets, with occupancy and temporal invariants positioning recently searched items near the top when possible.Important buckets must hold their most recently searched item; unimportant buckets may be occupied or vacant.Source: §3.1 · pp. 14–15
- The structure's level for a searched item is bounded using its previous nearby search and its distance from the minimum or maximum key.The depth sum is asymptotically the same as the stated lower bound, and the first searches contribute O(OPT(X)) when the sequence length is Ω(n log n).Source: §3.1 · pp. 16–17
- After a search, clearing demotions, promotion, and gap repair restore the SkipPopList invariants; searching and restoring them at level ℓ takes O(ℓ) time.During restoration, adjacent buckets are never both occupied and no run exceeds seven vacant buckets.Source: §3.1 · pp. 18–19
4 Working Set
For search sequences of length m ≥ 2n, expected offline cost after a uniformly random key permutation is Θ(m plus the log working-set sum). The analysis relates this cost to access-pattern working-set numbers, which are unchanged by relabeling.
4 Working Set
- The working set W_i contains distinct items searched from the previous search of x_i through time i, and its size is unchanged by a key permutation.Source: §4 · p. 20
- Θ(m + sum_{i∈notFirst} log w(x_i)): expected OPT(f(X)) matches this quantity for m ≥ 2n.Source: §4 · pp. 20, 23
- The expected second term contributes Θ(m) when m ≥ 2n.Source: §4 · p. 21
- The passages state that the bounds under discussion also hold when w(x_i) = 1, and that log2 w(x_i) ≥ 1 with positive constants c1, C, C′ independent of i.Source: §4 · p. 23
A PopBTree
The leads describe the PopBTree’s construction and pointer-based maintenance during searches and restoration, along with its balance guarantees.
A PopBTree
- Each node groups consecutive items with the lowest top level in its key interval, splitting that interval into child gaps; every item is stored once in a valid search tree.Equivalently, at each level, maximal consecutive sets of items not already stored at the previous level form nodes.Source: A PopBTree · pp. 27–28
- Every PopBTree node has at most 4 keys and 5 children, and all leaves lie at depth ℓmax, making T a B-tree.An item whose SkipPopList top level is ℓ is a key at depth ℓ in T.Source: A PopBTree · pp. 28–30
- T is a BBB[1/12] tree: each child has weight at least 1/12 of its parent’s weight.This weight guarantee follows from the subtree-size bounds for nodes at consecutive levels.Source: A PopBTree · p. 31
- During restoration, every node has at most 12 keys (the root at most 4), at most 13 children, subtree size between n/3^(ℓ−1) and 9n/3^(ℓ−1), and child weight at least 1/81 of its parent’s.The root is at level 1 or 2; child levels exceed parent levels by at most two, and every gap below ℓmax contains a key. Uniform leaf depth can fail transiently: leaves may be at depths from ⌈ℓmax/2⌉ to ℓmax.Source: A PopBTree · pp. 32–33
- Promotion and demotion each take O(1) time by splitting or merging a constant number of constant-size nodes within one pointer hop.The pointer moves down after a demotion and up after a promotion, matching the skip-list cost model.Source: A PopBTree · pp. 33–34
- Every restoration operation acts within distance 14 of the searched key’s bucket at its level and at a level no higher than ℓi(xi).This locality places operation sites and modified nodes in a connecting subtree of O(ℓi) nodes, traversable with O(ℓi) pointer moves.Source: A PopBTree · pp. 33, 35
- After each search, PopBTree is a BB[1/12] tree; after each unit-cost operation, it satisfies the weight condition with α = 1/81, and sequences of length Ω(n log n) take O(OPT(X)) total time.The total-time bound applies to the online algorithm’s processing of the sequence X.Source: A PopBTree · pp. 35–36
- Search and restoration each cost O(ℓi): the pointer searches by descending, then performs clearing, promotion, and repair in three passes over the connecting subtree.The clearing and repair passes traverse the subtree; the promotion pass descends to the searched key and moves back up with each promotion.Source: A PopBTree · pp. 35–36
B PopTree
The PopTree converts the PopBTree into a binary search tree using right-leaning chains and rotation-based simulation. For search sequences of length Ω(n log n), it achieves O(OPT(X)) total time while maintaining BB[1/20] balance after searches and BB[1/729] balance after every unit-cost operation.
B PopTree
- Expanding each PopBTree node into a right-leaning chain yields a binary search tree, with item depth between ℓ and 4ℓ for PopBTree level ℓ.Each chain key receives its interval child subtree on the left, preserving the BST ordering.Source: B PopTree · p. 36
- Each PopBTree unit-cost operation is simulated on the PopTree with O(1) unit-cost operations, leaving exactly the expansion of the updated PopBTree.Promotions use rotations of the pointed key with its parent; demotions reverse the rotation sequence.Source: B PopTree · p. 37
- In the PopTree P, every node has both child subtrees of weight at least 1/20 of its own weight, so P is a BB[1/20] tree.Source: B PopTree · p. 38
- Even between rotations during rebalancing, every PopTree state is BB[1/729].The bound holds after every unit-cost operation, including each rotation in the rebalancing sequences.Source: B PopTree · pp. 36, 38
- For |X| = Ω(n log n), PopTree processes X in O(OPT(X)) total time, is BB[1/20] after each search, and remains BB[1/729] after every unit-cost operation.The algorithm uses only unit-cost operations in the BB[α]-algorithm model.Source: B PopTree · p. 39