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.