algorithm - 使用 BST 搜索多个字段

Question

假设我们需要创建一个通讯录，可以提供多字段的搜索功能，有大量的记录。结构非常简单——姓名、电话号码和城市名称。

我可以输入“从 Ron... 开始”或“从 202... 开始”或“从 Arling... 开始”

然后它会给我预期的结果。

我想到的第一个解决方案是，创建三个 BST，一个基于电话号码，一个基于姓名，第三个基于城市。

现在我在想，有没有一种方法可以创建一个 BST(或任何其他方法)，但仍然可以进行搜索，而无需每次都对其进行排序？

提前致谢。

Answer 1

您可以使用单个 BST 来完成。 BST 节点将是:

class BSTNode
{
    string Key;
    byte KeyType; // 0=Name, 1=City, 2=Phone
    AddressRec Record;
}

而AddressRec当然是对实际地址记录的引用。

对于每条记录，您最终在 BST 中拥有三个条目。所以给定一个地址记录:

rec0 = { Name = "Jim", City = "Austin", Phone="512-555-1212" }

您将添加记录:

BST.Add(rec0.Name, 0, rec0);
BST.Add(rec0.City, 1, rec0);
BST.Add(rec0.Phone, 2, rec0);

并且您的搜索会将记录类型作为参数。

这更容易管理，因为您只有一个 BST，但搜索速度会慢一些，但速度是一个常数。在 BST 中搜索的时间复杂度为 O(log n)，您的组合 BST 的节点数将是三棵专用树的三倍。尽管如此，它的速度并没有线性变慢。也就是说，如果您有 1,024 个地址条目，那么您的每棵专用树将有 1024 个节点。 log2(1024) 是 10。您的单棵树将有 3,072 个节点。 log2(3,072) 为 11.58。因此，单个搜索会稍微慢一些。

但请注意，它的速度稍微慢了一个常数。考虑这张表:

   n   log2(n)   log2(3n)
  16      4        5.58
 128      7        8.58
1024     10       11.58
2^20     20       21.58

平均而言，无论 BST 中有多少项目，单个树每次搜索都需要大约两个额外的探测。