我有这样一个文件
A 100 200
A 120 220
B 140 250
另一个文件是这样的
A 130 210
A 133 215
B 180 270
然后我必须将第一个文件的每一行与第二个文件的每一行进行比较，并找出哪些行具有相交坐标
输出是这样的
A 100 200 A 130 210
A 100 200 A 133 215
A 100 200 A 180 270
然后就是这样。
在我的代码中，它的代码是这样的，我从第一个文件中获取第一行并与第二个文件的所有行进行比较。
所以我想知道如何实现树状数据结构来执行此操作，以便复杂度达到对数级。
最佳答案
您不需要树状数据结构。如果您的文件按第一个坐标排序，您可以在线性时间内轻松完成。只需为您保存当前相关行的每个文件维护一个缓冲区，您只需要为两个文件同步推进缓冲区。关键是，与另一个文件的给定线相交的线将始终彼此相邻，因此您知道一旦丢弃线就不必再检查它(因为文件是排序)。
关于algorithm - 在这种情况下如何实现树状数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13060130/