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.