我有一個問題給你。我必須實施一個包含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。 –