宾利-奥特曼算法: Java中的交换操作
我试图在Java中实现Bentley-渥太华算法，但在处理交点时需要实际实现交换操作(请参阅：维基百科上的宾利-奥特曼)。
如果我对算法的理解是正确的，有3种不同类型的事件点：
- 起始点：这是段的最左边点，将此段添加到树中，并检查它是否与该段的上方和下面的段直接相交(如果它们存在)。
- 端点：这是段的最右边的点，从树中移除这个段，并检查这些段是否直接在节的上面和下面相交。
- Intersection-point：这是两个段的交点，交换两个段在树中的位置。
(我遗漏了很多细节，因为它们在这里不太相关)
我使用一个TreeMap作为数据结构来存储我的片段。我不认为有一个swap操作可以让您只交换两个元素，所以这就是我陷入困境的地方。
回答 1
Stack Overflow用户
发布于 2020-11-24 11:14:14
当人们试图实施宾利-奥特曼的时候，就会出现很多这样的情况。参见，例如，用AVL树实现宾利-奥特曼算法。
tl;dr:您不能使用标准的自平衡二叉树实现，如TreeMap，用于宾利-奥特曼中的状态结构。
当大多数人使用平衡的二叉树，比如AVL树或红黑树时，就会对树中的元素进行不变的排序。3总是大于2，永远不需要交换它们。但是对于Bentley-渥太华，排序是一个扫描点的函数，这意味着算法需要与树直接参与重排序元素。在某些树中，可以黑入可变的比较器，但即使这样，说服树重新考虑其顺序的唯一方法是删除元素、更新比较器并重新插入元素--这比它应该的速度要慢得多。
此外，使用独立(突出)树结构更难实现最优实现，因为直接访问树中元素的频率很高。当线段结束时，您希望直接到达O(1)中树中的该段的节点，而不是沿着树在O(log n)中蜿蜒而行。这意味着分段结构应该作为树节点提供双重功能，而不是导航到树节点。
所以好消息是:你可以实现你自己的平衡二叉树！玩得开心。-)如果您以前没有实现过，我建议您使用AA树。但是，如果你在寻找更多的挑战，并想要一个更异国情调的结构，这往往是一个完美的匹配本特利-奥特曼的正常访问模式，试试Treap。
从另一个方向看，如果你想让一些东西快速工作，而你不关心技术上的渐近界限，可以考虑只为你的状态结构使用一个链表，用线性扫描而不是遍历树来定位节点。根据我的经验，定位状态节点的时间很少是涉及Bentley-渥太华系统的瓶颈，而且如果您只处理数百个或数千个段，那么二叉树的对数查找就不会显着了。
https://stackoverflow.com/questions/64983782
复制相似问题
腾讯云开发者
