Go llrb 升序遍历与降序遍历的边界有什么区别

Go llrb 的升序和降序遍历，关键不在方法名里的 Ascend 或 Descend，而在边界是否包含 pivot。需要“从某个值开始，包含它本身”时，用 AscendGreaterOrEqual；需要“只取小于某个值”时，用 AscendLessThan；需要一个范围时，AscendRange 表示下界包含、上界排除。反向读取时，DescendLessOrEqual 会按降序遍历不大于 pivot 的元素。

最容易写错的是把“升序/降序”当成唯一判断条件。实际选择要同时看方向、pivot 是否包含、是否需要上下界，以及回调返回 false 后是否应该提前停止。

• 升序起点：AscendGreaterOrEqual 包含 pivot，AscendLessThan 排除 pivot。
• 升序范围：AscendRange(lower, upper, iterator) 采用大于等于 lower 且小于 upper 的闭开区间。
• 降序边界：DescendLessOrEqual 只处理不大于 pivot 的元素，并从大到小回调。

先固定 llrb 的比较顺序和回调模型

GoLLRB/llrb 是基于左倾红黑树的有序树实现。元素需要满足 Item 接口，比较关系由 Less(than Item) bool 决定。因此，本文里的“大于”“小于”和“升序”都不是对某个字段硬编码，而是遵循你为 Item 定义的 Less 规则。

遍历方法接收一个 ItemIterator 回调。回调返回 true 表示继续，返回 false 表示停止继续遍历。它只是遍历控制信号，不会改变树里的元素，也不代表某个元素已经被删除。

type ItemIterator func(i Item) bool

// 这个示例只展示比较规则和回调意图，不把打印顺序当作接口契约。
type Score int

func (s Score) Less(than Item) bool {
	// 只有同一类型的分数才参与比较，调用方应保证数据类型一致。
	return s 

这里的 visit 只是说明回调形态。真正使用时，要把类型断言、重复键处理和停止条件设计好，尤其不要把“回调停止”误读成“边界自动包含”。边界由具体方法的契约决定。

两个升序方法到底差在哪里

升序遍历经常从两个看起来相近的方法里选错。AscendGreaterOrEqual(pivot, iterator) 会访问大于等于 pivot 的元素，pivot 如果存在，会被包含；AscendLessThan(pivot, iterator) 会访问小于 pivot 的元素，pivot 即使存在，也会被排除。

我在把“从某个分数开始展示”改成“展示某个分数以前的记录”时，最容易忽略的就是这个方向变化：前者是右侧集合并包含起点，后者是左侧集合并排除终点。方法名里的 GreaterOrEqual 和 LessThan 才是边界契约。

可以用下面的选择方式记忆：

用 AscendRange 表达闭开区间

AscendRange(greaterOrEqual, lessThan, iterator) 适合把两个单侧条件合并成一个范围：元素必须大于等于第一个参数，同时小于第二个参数。也就是常见的 [lower, upper)，下界进入结果，上界不进入结果。

tree.AscendRange(Score(60), Score(90), func(i Item) bool {
	// 这里接收到的是 [60, 90) 的静态范围语义，90 不属于结果。
	score := i.(Score)
	// 业务处理应放在回调里；返回 false 可在满足条件时停止。
	return score != 80
})

如果 lower 与 upper 相同，闭开区间没有可取元素；如果 lower 大于 upper，也不能把它当成“自动倒序范围”。需要倒序读取时应改用降序方法或重新表达边界，不要期待 AscendRange 帮你翻转参数含义。

降序遍历为什么只写一个 pivot

DescendLessOrEqual(pivot, iterator) 的语义是访问小于等于 pivot 的元素，并且按降序回调。它不是把升序方法的结果倒放，而是直接用一个上边界限定左侧集合：pivot 存在时会包含 pivot，然后依次向更小的元素走。

tree.DescendLessOrEqual(Score(90), func(i Item) bool {
	// 回调顺序是从不大于 90 的较大值向较小值移动。
	score := i.(Score)
	// 业务只要看到 70，就可以停止，不必继续访问更小的元素。
	return score != 70
})

降序方法只有一个 pivot，并不表示它支持任意双边区间。若需要“从 90 向下，但不低于 60”，可以在回调中遇到 60 之后返回 false；但这只是利用有序回调做提前停止，边界本身仍要由你的条件清楚表达。

把方法选择收敛成工程判断

先问四个问题，再写方法名：想要升序还是降序？pivot 要不要包含？是否同时存在下界和上界？回调遇到业务终点后要不要停止？这四个问题比背 API 名字更可靠。

还有两个实践提醒。第一，重复键是否允许取决于插入方法和 Item 的排序关系，不能用“遍历一次”推断每个业务 ID 只出现一次。第二，回调返回 false 只控制这次遍历是否继续，不会把树改成另一种状态。如果需要分页或游标，要把最后一个 Item 的边界语义单独记录下来。

Go llrb 遍历边界常见问题

AscendRange 的上界会被包含吗？

不会。官方方法契约使用大于等于下界且小于上界的语义，因此它是闭开区间 [lower, upper)。若业务需要包含 upper，需要重新设置范围或在业务层处理边界。

DescendLessOrEqual 会返回大于 pivot 的元素吗？

不会。它只遍历小于等于 pivot 的元素，并按降序回调。需要 pivot 以上的集合时，应回到升序方法或重新定义查询方向。

回调返回 false 是不是等于删除当前元素？

不是。返回 false 只是停止继续遍历，不改变树中的元素。删除应使用树提供的删除方法，并单独考虑遍历期间修改结构的风险。

Go llrb 的遍历选择可以压缩成一句话：先看比较方向，再看边界包含，最后看回调停止。记住 AscendGreaterOrEqual 包含 pivot、AscendLessThan 排除 pivot、AscendRange 使用闭开区间，以及 DescendLessOrEqual 按降序包含上限，就能避开大多数“结果多一条或少一条”的问题。