-1
$\begingroup$

Show how to augment dictionary of intervals (insert, delete, search) in order to make possible answer to following questions:

  1. Check if given interval $[a, b]$ intersects with some interval in a dictionary
  2. Check if given interval $[a, b]$ belongs to some interval $[c,d]$ in a dictionary (it means that $[a,b]\cap [c,d] = [a,b]$)
  3. Check if given interval $[a, b]$ intersects with some interval $[c,d]$ in a dictionary, such that $[c, d]\cap [a,b] \neq [a,b]$ and $[c,d]\cap [a,b] \neq [c,d]$.
  4. Check if is there in dictionary pair of intervals $[a,b];[c,d]$ such that $[a,b]\cap [c,d]\neq\emptyset$

Now, I say what I tried and why I am in stuck.
I use AVL tree. Key is left end of interval. Additional info in each node is maximum right end of intervals in subtree (of this node).
Moreover I include information about intersection in subtree (true or false) Then 1., 2., 4. are easy. However it is difficult to deal with 3.

Could you help me ? (don't throw out my thread, please)

Edit
dictionary = $\{[1,5], [2,7], [13,97], [213, 321]\}$
And now examples for 3. :
$[3,5]\to no$
$[95,100]\to yes$
$[5,10]\to yes$
$[215, 321]\to no$
$[215, 322]\to yes$
$[4,6]\to yes$
$[2,7]\to yes$
$[2,5]\to no$

$\endgroup$
  • $\begingroup$ Tell me why I did get -1 ? $\endgroup$ – M.Swe Aug 28 '15 at 17:14
  • $\begingroup$ Still does not work? $\endgroup$ – Evil Aug 29 '15 at 14:28
1
$\begingroup$

Try to read this one: Interval Tree
I wouldn't store intersections.

When you augment tree you should place nodes in some order to avoid conflicts in searches. Try different scheme as in the link, there will be no need to choose which way to go during search.

$\endgroup$
  • $\begingroup$ Yeah, It is increduble :) So let's make summary. One solution for 3. is create two AVL trees (in one of them key is left bound of interval, in second of them key is right bound). Queries of type 3. don't require additional information. Nevertheless I don't understand why would you like to add predecessor pointer or make two searches $\endgroup$ – M.Swe Aug 28 '15 at 20:17
  • $\begingroup$ Ok, unfortunately I can see that it is incorrect. Look at following example: You try find intersection on right bound. (we consider interval [a,b]). And root of our tree contains interval [c,d] such that a < c < d < b. How to decide what subtree choose ? left or right ? There is no answer. $\endgroup$ – M.Swe Aug 29 '15 at 11:48
  • $\begingroup$ So let's suppose, that max right bound in left tree is upper then b. We still can't make decision - left subtree or right ? $\endgroup$ – M.Swe Aug 29 '15 at 12:32
  • $\begingroup$ So in our discussion there is no proper solution, yes ? $\endgroup$ – M.Swe Aug 29 '15 at 13:18
  • $\begingroup$ It was, just it seems that you did not changed tree structure or I did not stated at first how should insertion look like. This is the same solution but it will ensure the above. $\endgroup$ – Evil Aug 29 '15 at 13:21

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.