3
$\begingroup$

I am struggling with exercise from the old algorithmic exam:
$d$ is const for the whole structure. Propose a structure for which you can do:

  • Init(S) //called only 1 time
  • Insert(x, S):: $ S := S \cup \{x\}$ in O(log(|S|)
  • Delete(x, S):: $ S := S \setminus \{x\}$ in O(log(|S|)
  • Get(S) = $| \{ a,b \} \subset S : a+b \le d|$ in O(1)

I am trying to that with AVL Tree with additional members like number of nodes such that $v.value+u.value \le d$.
Could somebody give me some hint?

Improve this question
$\endgroup$
0
2
$\begingroup$

It is on the right direction to try some kind of tree augmented with a global counter that stores the number of all unordered pairs of nodes $\{u,v\}$ such that $v.value+u.value \le d$.

The kind of tree you are looking for is a balanced (binary) search tree. Being balanced such as an AVL tree, it supports insertion, deletion and lookup of a number with $O(\log|S|)$ time. Being sorted as well, it can also update that global counter in $O(\log|S|)$ time if we can maintain some extra information on each node of the tree.

What should be those extra information? One approach is that each node $v$ will have a member $lcount$ that stores the number of nodes in its left subtree as well as a member $rcount$ that stores the number of nodes in its right subtree.

To simplify the explanation, let us use AVL tree. We will assume all values are distinct; otherwise, we can add a duplicity counter to each node.

Each insertion or deletion involves at most two tree rotations. Each rotation changes the edges between at most several nodes. So we can update all $lcount$ and $rcount$ in $O(\log|S|)$ time.

Before the insertion of node $n$, we should compute the number of nodes whose values are not greater than $d - n.value$, which is one plus the number of nodes to the left of the node $m$, whose value is the greatest but no greater than $d-n.value$. With the insertion of $n$, we will keep the global_counter intact if there is no such node $m$. Otherwise, letting $ancestor$ be $m$, we will do the following.

while ancestor is not null:
  if anc.value < m.value:
    global_counter := global_counter + ancestor.lcount + 1
  ancestor := ancestor.parent

The case of deletion is similar to the case of insertion.

Further explanation will be omitted.

Thanks to OP, who contributed to this answer.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I was thinking about that but I still don't have idea how to update nodes. In my opinion in node should be stored number of nodes $v.value+u.value \le d$ including me and both subtrees (left and right) but if I even have that information, how can I update that? $\endgroup$ – TurboGuma Jan 2 '20 at 17:34
  • $\begingroup$ Let say that I have $2$ children: $u$ and $v$, both of them have $value$ and $number$ of nodes satisfying given condition... after thinking there can't be a rule to calculate $me.number$. It will be $u.number$ + $v.number$ + number of nodes where $me.value + p.value < d$ + number of pairs created by choosing some $x$ from left subtree and some $y$ from right subtree $\endgroup$ – TurboGuma Jan 2 '20 at 17:38
  • $\begingroup$ Ahhhh I see, so the algorithm is as follows. We have AVL tree with number of elements not greater than me. And global counter for pairs. Now, we are going to find largest node that is no greater than x.value+ d, let say that this is $u$ ale the smallest node that is no smaller than x.value-d (let say $v$). Now our counter becomes: $c := c + (v.number - x.number) + (x.number - u.number)$, right? (for insert) $\endgroup$ – TurboGuma Jan 2 '20 at 17:52
  • $\begingroup$ I think that we should consider also if node $m$ is left or right child of its parent. $\endgroup$ – TurboGuma Jan 8 '20 at 15:44
  • $\begingroup$ In my opinion there should be rule like that: For each vertex on the path from m (including m) up to the first parent, which is to the right of the u (but we don't take him) we should perform global_counter: = global_counter + 1 + u.lcount $\endgroup$ – TurboGuma Jan 8 '20 at 18:42

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.