红黑树能高效做区间查询，因其是自平衡BST，中序遍历有序，支持O(log n)定位边界并O(k)遍历结果，总复杂度O(log n + k)，优于线性扫描和哈希表。
红黑树本身不直接提供“范围检索”接口，但它的有序性天然支持高效区间查询。只要底层实现保留了二叉搜索树的结构特性（左小右大、中序遍历有序），就能在 O(log n + k) 时间内完成范围查找——其中 log n 是定位区间起点和终点的开销，k 是结果数量。这比遍历整个容器快得多，尤其适合动态数据场景。
为什么红黑树能高效做区间查询
红黑树是二叉搜索树（BST）的自平衡变体，所有节点按键值严格排序。这意味着：
- 中序遍历结果天然升序，等价于对键的有序列表遍历
- 可快速定位任意键的 floor（≤目标的最大键）和 ceiling（≥目标的最小键）
- 一旦找到区间左边界，后续只需沿中序顺序向右遍历，直到超出右边界
- 无需预建索引或额外空间，所有操作复用原有树结构
典型区间操作的实现逻辑
标准库如 C++ std::map 或 Java TreeMap 均基于红黑树，已封装好常用区间方法：
-
lower_bound(key)：返回首个 ≥ key 的迭代器（O(log n)） -
upper_bound(key)：返回首个 > key 的迭代器（O(log n)） -
equal_range(key)：返回 [key, key] 区间的首尾迭代器对 - 自定义范围：调用
lower_bound(left)得起点，再用upper_bound(right)得终点，然后迭代器递增遍历中间节点
实际性能优势对比
假设需查 [100, 200] 内所有键值对，数据量为 10⁶：
- 线性扫描数组/链表：平均检查 5×10⁵ 个元素，O(n)
- 二分查找有序数组：O(log n) 定位起点，但插入删除 O(n)，不适合频繁更新
- 红黑树：O(log n) 找到起点，O(k) 收集结果，总耗时与结果数正相关，且增删查均为 O(log n)
- 哈希表：无法做范围查询，只能全量过滤，O(n)
使用时的关键注意点
不是所有红黑树实现都默认暴露完整区间能力，需确认：
- 是否支持
lower_bound/upper_bound等导航接口（C++ STL 和 Java TreeMap 支持；Linux 内核 rbtree 需自行实现） - 键类型必须可比较，且比较逻辑与插入时一致
- 并发环境下需外部加锁，红黑树本身不保证线程安全
- 若需反向区间（降序），可先正向查再逆序遍历，或使用反向迭代器
