Searching in Dynamic Tree-Like Partial Orders
Preprint
Abstract
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 <= n is the width of the partial-order---a natural obstacle in searching a partial order.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Sorting and Selection in PosetsSIAM Journal on Computing, 2011
- On the Complexity of Searching in Trees: Average-Case MinimizationLecture Notes in Computer Science, 2010
- The Height of Increasing TreesAnnals of Combinatorics, 2009
- Edge ranking and searching in partial ordersDiscrete Applied Mathematics, 2008
- Optimal Search in TreesSIAM Journal on Computing, 1999
- Random labelled trees and their branching networksJournal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics, 1980
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978