区间树(Interval Tree)

定义

区间树(Interval Tree)是一种存储区间集合的增强二叉搜索树,能在 O(log n) 时间内找到与给定点或区间重叠的区间,是《算法导论》中"数据结构的扩张"一章的经典示例。

原理

以区间左端点为键构建红黑树等平衡 BST,每个节点额外维护其子树中所有区间右端点的最大值 max。查询时,若左子树的 max 不小于查询区间的左端点,则左子树可能存在重叠区间,否则可整体剪枝,由此保证沿单一路径即可找到一个重叠区间;枚举全部 k 个重叠区间需要 O(min(n, k log n)) 时间。

应用

区间树用于日程冲突检测、内存区域管理(Linux 内核曾用红黑树增强结构管理虚拟内存区域)、基因组注释区间查询、GUI 中的一维碰撞检测等场景。

优缺点

优点是支持动态插入删除、查询高效;缺点是仅处理一维区间,实现需在旋转时正确维护附加信息,易与线段树、计算几何中的另一种同名结构混淆。