pipette
ENEnglish

Dynamically optimal weight-balanced binary search trees

John Iacono, Akash Pareek

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.