我有一个问题给你。我必须实施一个包含30000个姓名的商业地址簿。所有名字都包含名字和姓氏。 我必须实现一个自动完成文本框，它不仅可以搜索姓氏，还可以搜索姓氏。 谷歌搜索我已经看到，这个问题是使用patricia trie来解决的，但它只是前缀搜索，所以如果我使用firstname + lastname创建一个trie，我怎么可以不仅通过名字搜索，还通过姓氏搜索？地址簿和特里结构
是否必须重复插入两个字符串的条目？ 名字+姓氏 和 姓氏+名字
请帮帮我！
搜索必须非常有效。
谢谢。
是的，最简单的解决方案是插入两个变体。但是，这应该只复制搜索字符串，而不是条目。您可能想要以某种方式规范名字和姓氏之间的分隔（=删除地址簿和用户输入的标点符号），因此您可以在所有情况下找到条目以输入内容，例如“John Doe”，“Doe ，“John”，“Doe John”等。
我不会使用分支树，而只是一棵平衡树。在很多语言中，您会发现平衡树作为库中的排序映射实现（至少是Java和C++）。
另一种可能性是创建两次尝试。
第一个（假设它是T1）用于姓氏，第二个（假设它是T2）姓氏。
当你构建线索，从T1每个字终止（通常称为$号），加上指针的列表相关的条目T2，反之亦然。
I.E.如果李四是主菜：
T1:
J
|
O
|
H
|
N
|
$1
T2:
D
|
O
|
E
|
$2
$ 1进行持有一个列表，包含指向$ 2和$ 2将举行一个列表，包含$ 1
每个前缀搜索都将搜索这两个尝试，让你自动完成，然后使用指针获取全名（部分搜索只给你第一个/姓，第二个使用指针）。
搜索全称是由于两种尝试搜索完成（寻找的第一个名字在T1并为T2姓氏，并获得相关$1和$2分别），那么你需要检查指针比赛（名单l1在$1包含$2和名单l2在$2包含$1）。如果他们这样做 - 名字在字典中。
请注意，一旦您有一个指向$节点的指针，就可以简单地回到trie上，直到您到达根目录以获取此符号所代表的字。（需要指向父节点的指针）
另请注意：我解释了简单的尝试，但没有理由不使用patricia尝试，而是使用相同的方法。
谢谢你的回答！但是当我搜索一个字符串时，它可能会获得两个记录代表同一个人！例如marco marchi。所以如果我搜索marc，我会得到两个记录：marco marchi和marchi marco。那么该怎么办？ – Mapo
一棵平衡的树如何给他部分匹配？还要注意平衡树的效率较低 - 渐近地说是为了搜索字符串的存在。 – amit
您也可以将地址或出生日期的一部分添加到键，理想情况下可帮助用户选择正确的条目。为了确保你有一个唯一的键，你不需要一个列表作为价值，也追加一个唯一的记录ID。您可能想要隐藏用户的ID。 –