Go llrb 怎样按区间遍历有序树元素

如果你已经把元素放进 GoLLRB 的有序树，按一段范围读取时不需要自己写递归。直接调用 AscendRange，把下界作为 greaterOrEqual、把上界作为 lessThan，就能按升序遍历 [下界, 上界) 内的元素；回调返回 false 时会提前停止。

官方文档：https://pkg.go.dev/github.com/petar/GoLLRB/llrb

AscendRange 的边界先弄清

GoLLRB 的 LLRB 是基于 Item.Less 排序的左倾红黑树。范围接口的两个参数不是“起点和终点都包含”，而是明确对应“至少大于等于”和“严格小于”：greaterOrEqual 是包含下界，lessThan 是排除上界。

用 Item 和 AscendRange 读取一个区间

下面用整数演示完整调用。llrb.Int 已经实现了 Less，因此插入和范围参数都可以保持简单。示例把 20、30、40、50、60 放进树，再读取 30 到 60 之间的元素，预期范围是 30、40、50。

package main

import (
    "fmt"

    "github.com/petar/GoLLRB/llrb"
)

func main() {
    tree := llrb.New()
    tree.InsertNoReplaceBulk(
        llrb.Int(20), llrb.Int(30), llrb.Int(40),
        llrb.Int(50), llrb.Int(60),
    )

    lower, upper := llrb.Int(30), llrb.Int(60)
    tree.AscendRange(lower, upper, func(item llrb.Item) bool {
        fmt.Println(item)
        return true // 返回 true 才会继续访问下一个元素。
    })
}

这里的关键不是树里有多少个节点，而是比较关系：30 不小于下界，所以会被回调；60 不小于上界，因此被排除。若把上界改成 llrb.Int(61)，60 才会进入结果。

回调怎样收集结果并及时停止

ItemIterator 的签名是 func(i Item) bool。如果业务需要把元素放入切片，可以在回调中转换类型；如果只想取前几条，达到数量后返回 false，不必遍历完整个区间。

func firstItems(tree *llrb.LLRB, lower, upper llrb.Int, limit int) []llrb.Int {
    result := make([]llrb.Int, 0, limit)
    if limit 

真实项目中的自定义元素不一定能断言成 llrb.Int。更稳妥的做法是让业务类型实现 Less，再在回调中使用自己的类型；类型断言只适合确定树中始终放入同一种元素的场景。

运行手册：空区间、分页和时间窗口

把范围查询接入服务时，先把三个边界写成约定。第一，lower >= upper 时这是空区间，调用前直接返回通常更容易读；即使交给树处理，也不要期待回调被调用。第二，分页游标应让下一页从上一次的末尾之后开始，避免把最后一条重复返回。第三，时间窗口最好统一为左闭右开，例如本小时用 [09:00, 10:00)，相邻窗口就不会重复计算边界时刻。

func readWindow(tree *llrb.LLRB, start, end llrb.Int) []llrb.Int {
    if !start.Less(end) {
        return nil // start 等于或晚于 end 时，没有合法的左闭右开窗口。
    }

    values := make([]llrb.Int, 0)
    tree.AscendRange(start, end, func(item llrb.Item) bool {
        values = append(values, item.(llrb.Int))
        return true // 这里需要完整窗口，因此不提前停止。
    })
    return values
}

如果区间可能很大，不要无上限地把结果全部复制到切片。可以让回调直接写入分页响应、发送到下游，或在达到页面容量后返回 false。这能把“树的范围遍历”和“结果如何消费”分开，出现慢请求时也更容易定位是查找还是下游处理造成的。

常见问题

AscendRange 会包含上界吗？

不会。第二个参数命名为 lessThan，上界严格排除。需要包含某个整数上界时，可以把上界改成下一个可表达值，或根据业务改用更合适的范围约定。

下界和上界相等时会返回一条吗？

不会，[x, x) 是空区间。若要查询一个精确键，使用 Get 或 Has 更直接。

回调返回 false 会破坏树吗？

不会。它只表示停止本次遍历，不会删除或修改节点。下一次调用范围接口仍然从树的当前状态开始。