我试图在Java中实现Bentley-Ottmann算法，但在实际实现交换操作时遇到了困难(请参阅：维基百科上的Bentley Ottmann(，这是处理交叉点时所需要的。
如果我正确理解算法，有3种不同类型的事件点：
- 起点：这是线段的最左端，将该线段添加到树中，并检查它是否与该线段正上方和正下方的线段相交(如果存在(
- 终点：这是线段的最右点，从树中删除该线段，并检查正上方和正下方的线段是否相交
- 交点：这是两个线段的交点，交换两个线段在树中的位置[…]
(我省略了很多细节，因为它们在这里不是很相关(
我使用TreeMap作为我的数据结构来存储我的分段。我不认为TreeMaps有一个swap操作可以让你只交换两个元素，所以这就是我的问题所在。
当人们试图实现Bentley-Ottmann时，会出现很多这种情况。例如，请参阅使用AVL树实现Bentley–Ottmann算法。
tl；dr：对于Bentley-Ottmann中的状态结构，不能使用标准的自平衡二叉树实现，如TreeMap。
当大多数人使用像AVL树或红黑树这样的平衡二叉树时，它与树中元素的不可变顺序相结合。3总是大于2。永远不需要交换它们。但对于Bentley-Ottmann，排序是扫描点的函数，这意味着算法需要直接与树一起对元素进行重新排序。在一些树中，可以破解可变比较器，但即使这样，说服树重新思考其排序的唯一方法也是删除元素、更新比较器并重新插入元素——这比它应该的慢得多
此外，由于直接访问树中元素的频率很高，使用独立(挤出(树结构会使实现优化变得更加困难。线段结束时，您希望直线到达O(1(中树中该线段的节点，而不是沿着树蜿蜒到达O(logn(中的节点。这意味着您的Segment结构应该作为树节点发挥双重作用，而不是通过某种方式导航到树节点。
好消息是：你可以实现自己的平衡二叉树了！玩得开心如果您以前没有实现过，我建议使用AA树。但是，如果你正在寻找更多的挑战，并且想要一个更具异国情调的结构，它往往与Bentley Ottmann的正常访问模式完美匹配，那么试试Treap。
从另一个方向来看，如果你想让一些东西快速工作，而不在乎技术上的渐进边界，可以考虑只使用状态结构的链表，通过线性扫描而不是树遍历来定位节点。根据我的经验，定位状态节点的时间很少是涉及Bentley-Ottmann的系统的瓶颈，如果你只处理数百或数千个段，那么二叉树的对数查找将不会很重要。