Searching in tree-like partial orders

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.