algorithm - 在这种情况下如何实现树状数据结构

Question

我有这样的文件

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

它就像这样。

在我的代码中，它的代码是这样的，我从第一个文件中获取第一行并与第二个文件的所有行进行比较。

所以我想知道如何实现一个树状的数据结构来做到这一点，这样复杂性就会达到对数规模。

Answer 1

您不需要树状数据结构。如果您的文件按第一个坐标排序，您可以在线性时间内轻松完成。只需为您保存当前相关行的每个文件维护一个缓冲区，您只需为两个文件同步推进缓冲区。关键是，与另一个文件的给定行相交相关的行将始终彼此相邻，因此您知道一旦丢弃一行，您就不必再检查它了（因为文件是排序）。