algorithm - 为什么区间树需要存储子树的最大右端？

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

所以我们会递归右这是错误的，因为间隔与左子树重叠。