我正在阅读Cormen的《算法导论》第14章(增强数据结构),其中他谈到了区间树。以下是他提到的区间树设计方法。
步骤1:底层数据结构
我们选择一棵红黑树,其中每个节点x包含一个区间x:int,而x的键是区间的低端点x.int.low。因此,数据结构的中序遍历按照低端点排序列出区间。
这可以通过声明具有min和max的节点来完成。comparableTo函数应仅比较x.int.low。
步骤1:底层数据结构
我们选择一棵红黑树,其中每个节点x包含一个区间x:int,而x的键是区间的低端点x.int.low。因此,数据结构的中序遍历按照低端点排序列出区间。
这可以通过声明具有min和max的节点来完成。comparableTo函数应仅比较x.int.low。
我可以通过AVL树来实现这个,但是出于好奇想知道是否可以增强Java中现有的库,比如TreeSet或其他集合实体,以适应上述设计。如果可以的话,请提供一个示例代码或示例?步骤2:附加信息
除了区间本身之外,每个节点 x 都包含一个值 x.max,它是存储在以 x 为根的子树中的任何区间端点的最大值。
步骤3:维护信息
我们必须验证插入和删除在 n 个节点的区间树上需要 O(lg n) 的时间。我们可以通过给定区间 x.int 和节点 x 的子节点的 max 值来确定 x.max:
x:max = max(x.int.high; x.left.max; x.right.max)
步骤4:开发新操作
我们唯一需要的新操作是
INTERVAL-SEARCH
(T,i),它在树 T 中找到与区间 i 重叠的节点。如果树中没有与 i 重叠的区间,则该过程返回指向哨兵 T:nil 的指针。