Searching in tree-like partial orders

 Authors: Brent Heeringa, Marius Cătălin Iordan, and Louis Theran Proc. of: Workshop on Algorithms and Data Structures WADS’11, 2011. Full text: arXiv • DOI

We give the first data structure for the problem of maintaining a dynamic set of n elements drawn from a partially ordered universe described by a tree. We define the Line-Leaf Tree, a linear-sized data structure that supports the operations: insert; delete; test membership; and predecessor. The performance of our data structure is within an $O(log w)$-factor of optimal. Here $w \le n$ is the width of the partial-order–a natural obstacle in searching a partial order.