PopTree enables efficient dynamically balanced binary search trees
Dynamically optimal weight-balanced binary search trees
Data Structures and Algorithms
Summary
Binary search trees organize data so you can find things quickly, but keeping them balanced is tricky. The authors look at a special kind of balanced tree called a weight-balanced tree that keeps nodes sized just right. They introduce a new tree, the PopTree, which stays balanced dynamically using rotations after each search, without drifting too far from optimal. This means it performs searches nearly as well as the best possible balanced tree even without knowing future queries ahead of time.
What this means in practice
- •For database developers: Build faster search structures that keep data balanced dynamically with near-optimal efficiency for large datasets.
- •For file system engineers: Improve on-the-fly rebalancing of directory indexes to maintain quick access times during frequent file operations.
A theory result. No direct application yet.
Authors
John Iacono, Akash Pareek
Abstract
In STOC 1972, J{ü}rg Nievergelt and Edward M.~Reingold introduced the $BB[α]$-tree, also known as a \emph{weight-balanced} tree, which for any $α\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 $α(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 $α$, its performance on search sequences of length $Ω(n \log n)$ is proved to be within a constant factor (which can depend on $α$) of the optimal offline rotation-based binary search tree that maintains the $BB[α]$ balance invariant.