2
$\begingroup$

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: y<x \right \} \right | = \left | \left \{ y\in B: y>x \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.

$\endgroup$
1
$\begingroup$

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: y<x \right \} \right | - \left | \left \{ y\in B: y>x \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<x_\ell$ 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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Theorem May 17 at 9:56
  • $\begingroup$ $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)$. $\endgroup$ – Apass.Jack May 17 at 11:04
  • $\begingroup$ Silly me, I figured I need to update $\delta$ along the path down to the successor. Can't thank you enough! $\endgroup$ – Theorem May 17 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.