c++ - 使用int数组作为键的二叉树（欧几里得距离）？

Question

编写了一个存储船舶数据的二叉搜索树，搜索的关键是它们的声学特征。

在搜索树时，我想返回具有正确签名的船或与搜索到的签名最匹配的船。（通过查看哪艘船的欧几里得距离最近）。

我遇到的问题是如何比较签名而不是它们的实际数值。那么这意味着执行的任何搜索都是顺序的而不是二进制的？

有任何想法吗？

Answer 1

您正在做的事情归结为多维度的最近邻搜索。你不能只用二叉树有效地解决这个问题；你需要一些空间分区结构。

如果您的数组长度 N 很小（个位数），您可以使用 2^N-ary 树（四叉树、八叉树、...）作为二叉树的推广。

一个流行的选择也适用于更高的维度是Kd-tree。