增广区间树

Question

我正在尝试通过使用按“'low' 个区间值”排序的平衡二叉搜索树来实现 augmented interval tree。

在普通的旧搜索树中，当尝试插入树中已存在的键时，通常会忽略重复项（不插入）。

但是在存储间隔时，我可能有 (1,2) 和 (1,3) 具有相同的 'low' 值但不同。

如何处理增广区间树中的重复 'low' 值？我的意思是，我应该允许插入多个相同的 'low' 值吗？按什么顺序？如果有重复的键，如何在树中搜索？

Answer 1

链接文章建议使用每个区间的高值作为二次排序。然后你有一个间隔的总订单，你可以正常搜索。交集查询不需要具有相同低值的间隔之间的特定顺序；一旦您编写代码，这一点就会变得很明显。