Reproduce “Dynamically optimal weight-balanced binary search trees” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
John Iacono, Akash Pareek
PopTree adapts a balanced search tree after each search by promoting the key through a structure and repairing conflicts. It maintains BB[1/20] balance after searches and BB[1/729] after every unit-cost operation. For sequences of length Ω(n log n), its pointer-operation cost is within a constant factor of the offline optimum among rotation-based BB[α] trees, establishing optimality only within that balanced class.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.