增强间隔树

Question

我试图通过使用按区间的“低”值排序的平衡二叉搜索树来实现augmented interval tree。

在普通的旧搜索树中，当试图插入已存在于树中的密钥时，通常忽略重复（无插入）。

但是，当存储间隔时，我可能有（1,2）和（1,3），它们具有相同的“低”值但不同。

如何处理扩增间隔树中重复的“低”值？我的意思是，我应该允许插入多个相同的“低”值吗？按什么顺序？以及如果有重复密钥，如何在树中搜索？

Answer 1

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