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 中有多少项，每次搜索单个树都需要大约两个额外的探针。