algorithminterval-tree

Why does an interval tree need to store maximum right end of subtree?

I'm studying the implementation of interval tree, and I'm wondering if I can use a red black tree without the maximum value being stored and using the following pseudo-code? 

i=input_interval
x=tree.root

while x!=None AND check_overlap(i,x)==False: 
    if x.left!=None AND i.high < x.low:
        x=x.left
    else:
        x=x.right
return x
Solution

  • If I understand your pseudocode correctly, this wouldn't work for e.g. the following tree:

                30-40
        /           \
20-45                   null

    We search for i := 41-42

    We get:

    -> check_overlap(i,root) = false 
-> x.left(20,45) != null AND i.high(42) < x.low(40) = false

    so we would recurse right which is wrong as the interval overlaps with the left subtree.