Java树集-如何有效地插入然后轮询近邻

Question

正在寻找一个可以在没有库的Java 8上运行的解决方案

我正在尝试实现标准的线段相交算法。这涉及到跟踪当前"活动"的线段的排序集合(在y坐标上(。

算法的一部分是，假设树集actives和新线段s:

• 将s插入actives
• 在actives中查找s的近邻并计算

我已经将其实现为：

// left neighbor of s, as though already added
try {
Segment sa = actives.tailSet(s).first();
if (math(sa, s) {
...
}
} catch(NoSuchElementException ignore) {}
// right neighbor versus s, as though already added
try {
Segment sb = actives.headSet(s).last();
if (math(sb, s) {
...
}
} catch(NoSuchElementException ignore) {}   
// add s => actives
actives.add(s);

除了在first()或last()失败的情况下加重try/catch(这是与首先在变量中获取子集，然后检查它是否为空，如果不是则继续(之外，据我所知，真正的问题是效率低下，即：

tailSet()、headSet()和add()都在我的树集actives上产生O(log(N((功，而算法假设我可以在O中插入一次(log(N((，然后在O(1(中查找邻居。

我怎么能做类似的事情，但只进行一次O(log(N((二进制查找？我做的工作是必要的三倍。

Answer 1

也许先尝试将元素s添加到actives，然后调用actives.lower(s)和actives.higher(s)。TreeSet文档没有说明这些方法的复杂性，但在我看来，它们在源代码中是O(1(。

Answer 2

我稍微重写了一下您的代码：

// left neighbor of s, as though already added
SortedSet<Segment> trailSet = actives.tailSet(s);
if (!trailSet.isEmpty()) {
Segment sa = trailSet.first();
if (math(sa, s) {
...
}
}
// right neighbor versus s, as though already added
SortedSet<Segment> headSet = actives.headSet(s);
if (!headSet.isEmpty()) {
Segment sb = headSet.last();
if (math(sb, s) {
...
}
}
// add s => actives
actives.add(s);

不需要捕获任何内容(因为您可以在检索第一个(或最后一个(元素之前检查空性(。这更具性能，因为它不会导致生成堆栈跟踪。

但你甚至可以选择更好的。根据https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html，您可以调用

返回此集合中最大的元素，严格小于给定的元素，如果没有这样的元素，则返回null。

或最小值，严格意义上更大这些方法被称为lower和higher

Segment sa = actives.higher(s);
if (sa != null && math(sa, s) {
...
}
// right neighbor versus s, as though already added
Segment sb = actives.lower(s);
if (sb != null && math(sb, s) {
...
}
// add s => actives
actives.add(s);