《算法导论》第2版习题14.3-4：区间树重叠区间查询算法疑问

你指出的问题完全正确——原算法中右子树的访问条件是必要非充分的，它只能保证右子树有可能存在重叠区间，但无法确保一定存在，就像你举的例子那样。不过这并不影响算法满足题目要求的时间复杂度，原因如下：

1. 条件的本质 #

区间树是基于红黑树实现的，节点按区间的low值排序：左子树所有区间的low≤当前节点的low，右子树所有区间的low≥当前节点的low。

• 左子树的访问条件max[left[x]] ≥ low[i]：左子树中存在区间的high≥i的low，结合左子树区间low≤当前节点low，有可能存在重叠区间，需要遍历。
• 右子树的访问条件max[right[x]] ≥ low[i] 且 low[int[x]] ≤ high[i]：
  • max[right[x]] ≥ low[i]保证右子树存在区间的high≥i的low；
  • low[int[x]] ≤ high[i]保证i的high≥当前节点的low，而右子树区间low≥当前节点low，所以i的high有可能≥右子树区间的low。
    这两个条件是右子树存在重叠区间的必要条件——如果不满足，右子树一定没有重叠区间；但满足的话，只是存在可能性，不一定真的有。

2. 时间复杂度的保证 #

即使我们访问了像你例子中那样没有重叠区间的右子树，遍历该子树的时间是O(lg n)（树的高度）。而整个算法中，这样的“无效”子树访问次数不会超过O(lg n)次，再加上遍历所有k个重叠区间的时间O(k lg n)，总时间依然符合O(min(n, k lg n))的要求：

• 当k很小时，总时间是O(lg n)；
• 当k接近n时，遍历所有节点的时间是O(n)，符合min(n, k lg n)的上限。

3. 算法的修正（可选） #

如果想要减少不必要的子树访问，可以利用区间树的BST性质，在访问右子树时额外判断i.high ≥ min_low[right[x]]（即右子树区间的最小low≤i的high），但区间树通常不维护min_low属性，维护它会增加树的更新成本。因此原算法的条件是在不修改树的前提下的最优选择——用已有的max属性和节点low值做必要判断，平衡了时间开销和实现复杂度。

内容的提问来源于stack exchange，提问作者Maor Cohen