我正在寻找一种类似于CLR中的红黑区间树的区间树算法,但它默认支持合并区间,因此从不存在任何重叠区间.
换句话说,如果您有一个包含两个区间[2,3]和[5,6]的树,并且您添加了区间[4,4],则结果将是仅包含一个区间[2,6]的树.
谢谢
更新:我正在考虑的用例是计算传递闭包.间隔集用于存储后继集,因为它们被发现非常紧凑.但是,如果你将区间集表示为链表,我发现在某些情况下它们会变得非常大,因此找到插入点所需的时间也是如此.因此我对间隔树感兴趣.还有很多将一棵树与另一棵树合并(即一组OR操作) - 如果两棵树都很大,那么使用两棵树的顺序走路而不是每个间隔的重复插入来创建新树可能更好.