我正在尝试实现 augmented interval tree通过使用按“区间的‘低’值”排序的平衡二叉搜索树。
在普通的旧搜索树中，当尝试插入树中已存在的键时，通常会忽略重复项(不插入)。
但是在存储间隔时，我可能有 (1,2) 和 (1,3)，它们具有相同的“低”值但不同。
如何处理增广区间树中重复的“低”值？我的意思是，我应该允许插入多个相同的“低”值吗？按什么顺序？如果有重复的键，如何在树中搜索？
最佳答案
链接的文章建议使用每个区间的高值作为二次排序。然后你有一个间隔的总订单，你可以正常搜索。交集查询不需要具有相同低值的间隔之间的特定顺序；一旦您编写代码，这一点就会变得很明显。
关于algorithm - 增广区间树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33464403/