Почему интервальное дерево должно хранить максимально правый конец поддерева?

Question

Я изучаю реализацию дерева интервалов, и мне интересно, могу ли я использовать красное черное дерево без сохранения максимального значения и использования следующего псевдокода?

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 

Answer 1

Если я правильно понимаю ваш псевдокод, это не сработает, например, для следующего дерева:

            30-40
        /           \
20-45                   null

Мы ищем i := 41-42

Мы получаем:

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

таким образом, мы вернемся вправо, что неверно, поскольку интервал перекрывается с левым поддеревом.