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

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

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

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

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

algorithm

interval-tree