无界区间树

Rust实现的一种区间树，基于Cormen等人在《算法导论》（第3版，第14.3节：区间树，第348-354页）中描述的。区间树用于高效查询区间数据库。该实现是泛型的，因为它可以处理实现Ord+Clone特质的值的区间。边界可以是包含的、排除的或无界的。以下是有效区间的示例

• [5, 9] <- 包含/包含的整数
• [-2.3, 18.81) <- 包含/排除的浮点数
• ("abc", "hi"] <- 排除/包含的字符串
• (-inf, 2019年11月7日] <- 无界/包含的日期
• [(1, 5), (2, 9)] <- 包含/包含的整数元组

如何使用

建议查看文档中的示例部分（因为它们由Rust生态系统测试），但这里有一个当前的示例。

use unbounded_interval_tree::IntervalTree;
use std::ops::Bound::{Included, Excluded, Unbounded};

// Default interval tree.
let mut tree = IntervalTree::default();

// Ranges are defined as a 2-ple of Bounds.
let interval1 = (Included(5), Excluded(9));
let interval2 = (Unbounded, Included(-2));
let interval3 = (Included(30), Included(30));

// Add intervals to the tree.
tree.insert(interval1);
tree.insert(interval2);
tree.insert(interval3);

// Iterate through the intervals inorder.
for (start, end) in tree.iter() {
  println!("Start: {:?}\tEnd: {:?}", start, end);
}

// Get overlapping intervals.
let overlaps = tree.get_interval_overlaps(&(0..30));

// Get the difference between the database
// of intervals and the query interval.
let diff = tree.get_interval_difference(&(0..=30));

路线图

接下来是什么...

• 允许从树中删除区间（在delete分支中开始）。
  • 我已经向API添加了一个remove_random_leaf方法。使用此数据结构删除叶子节点要简单得多，因此我首先着手解决这个问题。
• 通过在插入/删除期间旋转来保持树平衡
• 断言区间起始边界小于或等于相同区间的结束边界。