红黑树能高效做区间查询，因其是自平衡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 需自行实现）
• 键类型必须可比较，且比较逻辑与插入时一致
• 并发环境下需外部加锁，红黑树本身不保证线程安全
• 若需反向区间（降序），可先正向查再逆序遍历，或使用反向迭代器