# Suggest a Data Structure To Manage 2 Sets

I was given the following problem which really baffled me, and I would like some guidance in solving it.

I want to make a data-structure which represents two sets $$A,B\subseteq \mathbb{R}$$, so that I can Insert an element to a set of my choosing in $$O(\log n)$$ (where $$n$$ is the number of elements existing in both sets).

However, it is also required to be able to find in $$O(1)$$ some $$x \in A\cup B$$ such that the amount of elements in $$A$$ lesser than $$x$$, equates to the number of elements in $$B$$ greater than $$x$$, if exists:

$$\left | \left \{ y\in A: yx \right \} \right |$$

Now the obvious direction is to use balanced trees (say AVL). I can use the same tree for both sets or separate to 2 different trees. I also presume I should store more data in the nodes, However I'm not sure which. I thought about storing the number of elements smaller and greater but that would make the Insert method $$O(n)$$, since I have to update many nodes in the respective tree.

You are on the right approach to attach "more data" to a balanced search tree.

For all $$x\in A\cup B$$, let $$d(x)=\left | \left \{ y\in A: yx \right \} \right |,$$ which is an increasing function on $$x$$.

For simplicity, let us assume all elements are distinct first. We can use a balanced search tree $$T$$ to store all elements in $$A$$ and $$B$$, keeping track of whether each element comes from $$A$$ or $$B$$.

• We will also store $$(x_\ell, \delta_\ell)$$ , where $$x_\ell$$ is the largest element $$x$$ in $$T$$ such that $$d(x)\le0$$ and where $$\delta_\ell=d(x_\ell)$$.
• We will also store $$(x_r, \delta_r)$$ , where $$x_r$$ is the smallest element $$x$$ in $$T$$ such that $$d(x)\ge0$$ and where $$\delta_r=d(x_r)$$.

Either pair might not exist. However, at least one pair must be available, which is enough to identify the wanted $$x\in A\cup B$$, i.e., $$d(x)=0$$, if exists.

Suppose $$v$$ will be inserted into $$T$$. Here is a sketch of what to do to maintain the data structure. The idea is simply to move $$x_\ell$$ or $$x_r$$ to its neighbor one or two times. Several obvious boundary cases such as when $$d(x)>0$$ for all $$x$$ in $$T$$ before or after $$v$$ is inserted have been skipped.

1. Insert $$v$$.
2. Update $$(x_\ell, \delta_\ell)$$ as the following.

1. Do the following.
• find $$x_{-1}$$, the predecessor of $$x_\ell$$. Compute $$d(x_{-1})$$.
• find $$x_{-2}$$, the predecessor of $$x_{-1}$$. Compute $$d(x_{-2})$$.
• find $$x_{1}$$, the successor of $$x_\ell$$. Compute $$d(x_1)$$.
• find $$x_{2}$$, the successor of $$x_1$$. Compute $$d(x_2)$$.
2. Let $$x_{\text{new}}$$ be the largest element $$x$$ among $$x_{-2}, x_{-1}, x_\ell, x_{1}, x_{2}$$ such that $$d(x)\le0$$. Update $$(x_\ell, \delta_\ell)$$ to $$(x_{\text{new}}, d(x_{\text{new}}))$$
3. Update $$(x_r, \delta_r)$$ similarly, which should take $$O(\log n)$$ time as well.

Any kind of balanced search trees can be used as long as the insertion, finding the predecessor and finding the successor can be done in $$O(\log n)$$. In particular, we can use AVL tree or red-black tree.

• Step 1 takes $$O(\log n)$$ time.
• Each search for predecessor or successor in Step 2 takes $$O(\log n)$$ time. Each computation of $$d(*)$$ takes $$O(1)$$ time, as we know $$d(x_\ell)$$. For example, $$d(x_{-1})=d(x_\ell)-\lambda_A(x_{-1})-\lambda_B(x_\ell)$$, where $$\lambda_A(x_{-1})$$ is 1 if $$x_{-1}\in A$$ and 0 otherwise. $$\lambda_B(x_{\ell})$$ is 1 if $$x_{\ell}\in B$$ and 0 otherwise. Similarly, $$d(x_1)=d(x_\ell)+\lambda_A(x_\ell)+\lambda_B(x_1)$$. So step 2 takes $$O(\log n)$$ tims.
• Similarly, step 3 takes $$O(\log n)$$ time.

When there are duplicated elements in $$A$$ and $$B$$, the idea is similar but somewhat more complicated. A balanced search tree $$T$$ will store all distinct elements in $$A$$ and $$B$$. Each node will store

• a distinct element $$x\in A\cup B$$,
• how many time that element appears in $$A$$,
• and how many time that element appears in $$B$$.

The order of the node is determined by the order of that element. Attached to the whole $$T$$ are the two pairs $$(x_\ell, \delta_\ell)$$ and $$(x_r, \delta_r)$$ defined the same as above.

Exercise 1. Refine the algorithm so that at any point of time, only one of the pairs $$(x_\ell, \delta_\ell)$$ and $$(x_r, \delta_r)$$ is maintained.

Exercise 2. Refine the algorithm so that only 1 or 2 cases in step 2.1 are needed by considering $$v or not, $$v=x_{-1}$$ or not, $$v\in A$$ or $$v\in B$$, etc.

Exercise 3. Consider using one balanced search tree for elements in $$A$$ and another one for elements in $$B$$ instead of using one for both of them. Will it work?

• Thank you very much! Are you sure though I can compute the $d$s of the succesors and predecessors in $O(1)$ if at all? It seems impossible to update the $\delta$s at all. – Theorem May 17 '19 at 9:56
• $d(x_{-1})=d(x_\ell)-\lambda_A(x_{-1})-\lambda_B(x_\ell)$, where $\lambda_A(\cdot)$ is the characteristic function of $A$, i.e., $\lambda_A(u)=1 \Longleftrightarrow u\in A$. $\lambda_B(\cdot)$ is the characteristic function of $B$, i.e., $\lambda_B(u)=1 \Longleftrightarrow u\in B$. Similarly, $d(x_1)=d(x_\ell)+\lambda_A(x_\ell)+\lambda_B(x_1)$. – John L. May 17 '19 at 11:04
• Silly me, I figured I need to update $\delta$ along the path down to the successor. Can't thank you enough! – Theorem May 17 '19 at 11:06