使用BST搜索多个字段

Question

假设我们需要创建一个地址簿,该地址簿可以在多个字段上提供具有大量记录的搜索功能.结构非常简单 - 姓名,电话号码和城市名称.

我可以输入"以罗恩开头......"或"从202开始..."或"从阿灵开始......"

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

我想到的第一个解决方案是,创建三个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中有多少项,单个树每次搜索都需要大约两个额外的探测.