pipette
ESEspañol

Dynamically optimal weight-balanced binary search trees

John Iacono, Akash Pareek

Preprint

In the authors' words

In STOC 1972, J{\"{u}}rg Nievergelt and Edward M.~Reingold introduced the -tree, also known as a weight-balanced tree, which for any is a binary search tree where every node with induced subtree size has children with induced subtree sizes at least . A new rotation-based binary search tree, the PopTree, is introduced. The PopTree stores elements and is a -tree after the execution of each search and a -tree at all times, notably while rebalancing. For any constant , its performance on search sequences of length is proved to be within a constant factor (which can depend on ) of the optimal offline rotation-based binary search tree that maintains the balance invariant.

Main resultLimitation the authors admit

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.