# augmenting AVL, intervals

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$

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