区间树 概述 区间树（Interval Tree）是在 红黑树 上添加 max 属性的扩张数据结构，用于维护一个动态的区间集合，支持 O(lgn) 时间的 区间重叠查询（Interval Overlap Search）。区间树是 数据结构扩张 的经典应用之一，广泛应用于计算几何、日程管理、资源分配等领域。 定义 区间树 区间树是一棵红黑树，其中： 每个节点 x 关联一个闭区间 x.int=[x.low,x.high] 树按区间的低端点 x.low 作为关键字进行排序（即中序遍历按 low 值递增） 每个节点 x 额外维护一个域 x.max，定义为： x.max=max{x.high,x.left.max,x.right.max} 即以 x 为根的子树中所有区间的最大端点值。 哨兵节点 nil[T] 的 max 为 −∞。 max 属性的递归定义 x.\text{high} \\ x.\text{left}.\text{max} \\ x.\text{right}.\text{max} \end{cases}$$ 这意味着 $x.\text{max}$ 是 $x$ 的区间右端点与其左右子树中最大端点值中的最大者。 ### 生活化类比 想象你管理一栋大楼的会议室预订系统。每个预订就是一个"区间"——从开始时间到结束时间。你把所有预订按开始时间排序放在一个文件柜里（这就是红黑树，按 `low` 排序）。 现在有人来问："下午2点到3点之间，有没有空闲的会议室？"（即查找与 $[14:00, 15:00]$ 重叠的预订）。 如果不用区间树，你需要翻遍整个文件柜。但如果你在每个文件夹外面贴一张标签，写着"这个文件夹里所有预订的**最晚结束时间**"（这就是 `max`），你就可以快速跳过那些不可能重叠的文件夹： - 如果某个文件夹的"最晚结束时间"早于你的开始时间（2点），那这个文件夹里**所有**预订都不可能和你重叠——直接跳过！ - 只有"最晚结束时间"晚于2点的文件夹才需要仔细查看。 这就是区间树利用 `max` 属性进行**剪枝**的核心思想。 ## 核心性质 ### 性质1：max 的维护开销为 O(1) 每节点 根据 [[算法导论/concepts/红黑树扩张定理]]，`max` 满足可聚合性条件（可从左右子节点的 `max` 和自身 `high` 在 $O(1)$ 内计算），因此旋转操作后可在 $O(1)$ 时间内维护。插入和删除操作中，沿路径更新 `max` 的总开销为 $O(\lg n)$。 ### 性质2：INTERVAL-SEARCH 的期望时间为 O(lg n) INTERVAL-SEARCH 利用 `max` 属性进行剪枝，在大多数情况下不需要遍历两棵子树。其期望时间复杂度为 $O(\lg n)$，最坏情况为 $O(n)$（当所有区间都重叠时）。 ### 性质3：保持红黑树的所有性质 区间树仍然是合法的红黑树，所有红黑树的基本操作（INSERT、DELETE、SEARCH 等）的时间复杂度不变。 ### 性质4：支持动态区间集合 区间树支持区间的动态插入和删除，每次操作后 `max` 属性自动更新，查询始终基于最新的区间集合。 ## INTERVAL-SEARCH 操作 INTERVAL-SEARCH$(T, i)$：在区间树 $T$ 中查找与区间 $i$ 重叠的任意一个区间。如果不存在这样的区间，返回 $\text{nil}[T]$。 ``` INTERVAL-SEARCH(T, i) 1 x = T.root 2 while x != nil[T] and i does not overlap x.int 3 if x.left != nil[T] and x.left.max >= i.low 4 x = x.left // 左子树可能包含重叠区间 5 else 6 x = x.right // 左子树不可能有重叠，搜索右子树 7 return x ``` ### 执行逻辑详解 1. **从根节点开始**：检查当前节点 $x$ 的区间是否与查询区间 $i$ [[算法导论/concepts/区间重叠|重叠]]。 2. **如果重叠**：直接返回 $x$（找到答案）。 3. **如果不重叠**：需要决定搜索左子树还是右子树： - **检查左子树**：如果 $x.\text{left}.\text{max} \geq i.\text{low}$，说明左子树中**至少存在一个区间**，其高端点 $\geq i.\text{low}$。根据 [[算法导论/concepts/区间重叠]] 的判定条件（$a \leq d$ 且 $c \leq b$），这个区间有可能与 $i$ 重叠，因此需要搜索左子树。 - **剪枝左子树**：如果 $x.\text{left}.\text{max} < i.\text{low}$，说明左子树中**所有区间**的高端点都 $< i.\text{low}$，即所有区间的右端点都在 $i$ 的左端点之前，因此左子树中不可能有任何区间与 $i$ 重叠，直接跳过。 4. **递归搜索**：根据上述判断，选择一个子树继续搜索。 ### 剪枝的关键原理 剪枝的核心在于以下逻辑： $$x.\text{left}.\text{max} < i.\text{low} \implies \forall \text{ interval } j \text{ in left subtree},\; j.\text{high} < i.\text{low} \implies j \text{ 不与 } i \text{ 重叠}$$ 这是因为对于左子树中的任意区间 $j = [j.\text{low}, j.\text{high}]$，有 $j.\text{high} \leq x.\text{left}.\text{max} < i.\text{low}$。根据区间重叠的判定条件，$j$ 与 $i$ 重叠需要 $j.\text{high} \geq i.\text{low}$，但此条件不满足，因此 $j$ 不与 $i$ 重叠。 ### 示例演示 考虑以下区间树（节点格式为 `[low, high] max`），查找与 $i = [22, 25]$ 重叠的区间： ``` [16, 21] 26 / \ [8, 9] 9 [25, 30] 30 / \ / \ [5, 8] 8 [15, 23] 23 [17, 19] 19 [26, 27] 27 ``` 查找 INTERVAL-SEARCH$(T, [22, 25])$： | 步骤 | 当前节点 $x$ | $x.\text{int}$ 与 $i$ 重叠？ | $x.\text{left}.\text{max} \geq i.\text{low}$？ | 动作 | |:---:|:---|:---:|:---:|:---| | 1 | [16, 21] 26 | $21 < 22$，不重叠 | $23 \geq 22$，是 | 搜索左子树 | | 2 | [8, 9] 9 | $9 < 22$，不重叠 | $8 < 22$，否 | 搜索右子树 | | 3 | [15, 23] 23 | $15 \leq 25$ 且 $22 \leq 23$，**重叠** | — | 返回 **[15, 23]** | 验证：区间 $[15, 23]$ 与 $[22, 25]$ 的重叠部分为 $[22, 23]$，确实重叠。 ## max 的维护 ### 旋转操作中的维护 在左旋和右旋中，只有两个节点的 `max` 需要更新： ``` LEFT-ROTATE(T, x) ... // 标准左旋操作完成后，更新 max y.max = max(y.int.high, y.left.max, y.right.max) x.max = max(x.int.high, x.left.max, x.right.max) ``` 注意更新顺序：先更新 $x$（旋转后变为子节点），再更新 $y$（旋转后变为父节点）。 ### 插入操作中的维护 在红黑树的插入过程中，新节点的 `max` 初始化为 `max`$(i.\text{high}, -\infty, -\infty) = i.\text{high}$。然后从新节点的父节点沿路径向上回溯，对每个祖先节点执行： $$x.\text{max} = \max(x.\text{high},\; x.\text{left}.\text{max},\; x.\text{right}.\text{max})$$ ### 删除操作中的维护 与插入类似，从实际被删除节点的位置沿路径向上回溯，更新路径上每个节点的 `max`。 ## 复杂度分析 | 操作 | 时间复杂度 | 说明 | |:---|:---:|:---| | INSERT | $O(\lg n)$ | 红黑树插入 + `max` 维护 | | DELETE | $O(\lg n)$ | 红黑树删除 + `max` 维护 | | INTERVAL-SEARCH（期望） | $O(\lg n)$ | 利用 `max` 剪枝 | | INTERVAL-SEARCH（最坏） | $O(n)$ | 所有区间都重叠时 | ## 参见 - [[算法导论/concepts/红黑树]] — 区间树的基础数据结构 - [[算法导论/concepts/数据结构扩张]] — 区间树是数据结构扩张的典型案例 - [[算法导论/concepts/数据结构扩张四步法]] — 系统化推导区间树的四步方法论 - [[算法导论/concepts/红黑树扩张定理]] — 保证 `max` 属性在旋转后可 $O(1)$ 维护的理论基础 - [[算法导论/concepts/区间重叠]] — 区间重叠的判定条件，是 INTERVAL-SEARCH 的基础 - [[算法导论/concepts/顺序统计树]] — 红黑树扩张的另一经典案例