I have some partial order $\preceq \,\,\subset A \times A$, I'd like a data structure with the following operations:

  • $Insert(a, x, T)$: add $(a, x)$ to the collection $T$
  • $Find(x, T)$: find the element $(a, y)$ in $T$ such that $y \preceq x$ and $y$ is the largest such value (e.g. the greatest lower bound of $x$.

If this was a total order I'd use a self balancing binary tree. Is there a data structure that works for partial orders? I realize this might not have enough structure to find a satisfactory solution so I'll add that I'm interested in specialized sub-cases of this as well. For instance what if $\preceq$ is just $\subseteq$ and $A$ is $\mathcal{P}(B)$ and we have some fast way to check if one is a subset of the other? Is there a different special case that exists?

The case of subsets seems like it would allow you to create a tree where at each node you asked "is this node's element an element of x?" and you could branch off into the tree that way but it isn't clear to me that any kind of self-balancing technique exists.

I should also add that periodic reblancing of a tree is probably viable for my use case.

  • $\begingroup$ "Partial Order" implies, there could be several, even isolated (linear) chains, even consisting of single elements? $\endgroup$ Commented Mar 24, 2022 at 19:25
  • $\begingroup$ In general sure. If it helps you can assume the induced graph is connected as a special case. I don't really expect the general case to be solvable in less than linear time in the size of the collection, you need extra structure I think to be more efficient. I'm interested in learning what special cases might be solvable using existing data structures. $\endgroup$
    – Jake
    Commented Mar 24, 2022 at 19:29
  • $\begingroup$ uh, I don't know what a half order is but any DAG induces a partial order by its transitive closure. The "induced graph" of a partial order is just the directed graph where an edge exists between any two nodes if the relation holds between those nodes. A tree is never the induced graph of a partial order unless its very small (size 0 to 2 I think). $\endgroup$
    – Jake
    Commented Mar 24, 2022 at 21:09
  • 2
  • 1
    $\begingroup$ Absolutely fantastic answer D.W.!! There is so much good info there. I wasn't able to type in the right words to find those but that's a perfect answer. $\endgroup$
    – Jake
    Commented Mar 27, 2022 at 1:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.