区间树(interval tree)是一种对动态集合进行维护的扩张红黑树,因此可在实验二红黑树的基础上进行扩张。为此,本实验(实验三)在实验二的基础上对红黑树的节点增加新的附加信息,并设计新的操作。从而熟悉并实现区间树上的重叠区间查找算法,分析该算法的性能。
具体问题测试用例:尝试构造一个区间树。可依次插入下列区间:[41,49] [38,44] [31,35] [12,20] [19,25] [8,10]
查找重叠区间:“find [37,40]”、“find[9,30]”、“find [26,29]”