我正在尝试在Java中实现Bentley-Ottmann算法，但被困在实际实现处理交点时所需的交换操作（请参阅：Wikipedia上的Bentley-Ottmann）。
如果我正确理解算法，则有3种不同类型的事件点：
（我在此省略了很多细节，因为它们在这里不太相关）
我使用aTreeMap作为数据结构来存储细分。我不认为有一个swap操作TreeMaps可以让您仅交换两个元素，所以这就是我要坚持的地方。
当人们尝试实施Bentley-Ottmann时，这会出现很多情况。例如，参见使用AVL树实现Bentley-Ottmann算法。
tl; dr：您不能像TreeMapBentley-Ottmann中的状态结构那样使用标准的自平衡二叉树实现。
当大多数人使用平衡的二叉树（如AVL树或红黑树）时，它会与树中元素的顺序保持不变。3始终大于2。永远不需要交换它们。但是对于Bentley-Ottmann，排序是扫描点的函数，这意味着算法需要直接与树一起参与元素的重新排序。在某些树中，可以侵入可变的比较器，但是即使如此，仍然说服树重新考虑其顺序的唯一方法是删除元素，更新比较器并重新插入元素-这要慢得多，而且要慢得多比应该的。
此外，由于您直接访问树中元素的频率，使用独立（可压缩）树结构会使实现最佳实现更加困难。当线段结束时，您想直接在O（1）中到达树中该节点的节点，而不是在O（log n）中沿着该树蜿蜒到该节点。这意味着您的细分结构应兼职作为树节点，而没有某种导航到树节点的方法。
好消息是：您可以实现自己的平衡二叉树！玩得开心。;-)如果您以前没有实现过，建议您使用AA树。但是，如果您正在寻找更多的挑战，并且想要一个更奇特的结构，它通常是Bentley-Ottmann正常访问模式的理想选择，请尝试使用Treap。
从另一个方向看，如果您想使某些事情快速运行并且您不关心技术的渐近边界，请考虑仅对状态结构使用链表，通过线性扫描而不是遍历树来定位节点。以我的经验，定位状态节点的时间很少是涉及Bentley-Ottmann的系统的瓶颈，并且如果仅处理数百或数千个段，则对二叉树的对数查找将不会很重要。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句