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.
