Is there a search tree where union is associative, so $a \cup (b \cup c) = (a \cup b) \cup c$ gives a tree with the same structure?

A complete binary tree would be such a tree, but for example a red-black tree has several possible constructions for a given set of elements.

Is there such a tree that does better than $O(n)$ for common operations such as insert or delete?

  • $\begingroup$ What exactly do you mean by "gives the same tree"? Does joining $a \cup b$ only work when the biggest key of $a$ is smaller than the smallest key of $b$? $\endgroup$
    – Curtis F
    Jul 14 '18 at 17:44
  • $\begingroup$ @CurtisF updated the text with red-black tree as an example where it might not give the same tree. $\endgroup$
    – user239558
    Jul 14 '18 at 17:52
  • $\begingroup$ See if the data structures in the linked duplicates meet your needs. If not, can you edit the question to identify the specific requirements that aren't met by those approaches, clarify what you mean by "$\cup$" and "$=$" more precisely, and then flag the question for re-opening? (It's not 100% clear to me exactly what you mean by $\cup$ and $=$. Does $=$ mean that the trees have the same structure, or is it enough to have a hash value that lets us test whether two trees are equivalent? Are we allowed to define the $\cup$ operator however we like? Can you answer Curtis F's question?) $\endgroup$
    – D.W.
    Jul 14 '18 at 17:58
  • $\begingroup$ @CurtisF "Does joining a∪b only work when the biggest key of a is smaller than the smallest key of b?" no, let's say a = fromList [1,2,3] and b = fromList [2,3,4], then a union b = fromList [1,2,3,4] $\endgroup$
    – user239558
    Jul 14 '18 at 18:06
  • $\begingroup$ @D.W. I think the linked duplicates meet my needs. Although they don't spell it out, the answer is basically NO. $\endgroup$
    – user239558
    Jul 19 '18 at 22:41