嘗試與三元搜索樹進行自動完成？

Question

我已經經歷了嘗試和三元搜索樹，我對它們有一些疑問。我已經谷歌搜索的答案，但我不能得到這些具體的答案。所以，這是我的問題。

1. 如果嘗試空間效率低下並且TST結合了BST的最佳效果並嘗試，這是否意味着嘗試實際上根本不被使用？

2. 假設TST用於自動完成，..如何在谷歌的情況下工作？我的意思是，我們實際上沒有一套固定的單詞等等，那麼TST樹將如何構建？

Answer 1

嘗試次數和三元搜索樹代表時間/空間權衡。如果您的字母表中有k個符號，則每個節點都有k個指針加上一個額外的位，以表示節點是否編碼一個字。查找長度爲L的字總是需要時間O（L）。三元搜索樹爲每個節點存儲三個指針，外加一個字符和一個位以表示節點是否編碼一個字。查找長度爲L的字需要時間O（L log k）。 （如果你有一個靜態的三元搜索樹，你可以建立使用weight-balanced trees的TST，提高了查找時間爲O（L +日誌K），但使得插入昂貴。）

對於情況：其中在特里樹的每個節點使用了大部分的孩子，Trie比三元搜索樹具有更高的空間效率和時間效率。如果每個節點存儲相對較少的子節點，則三元搜索樹的空間效率要高得多。通常來說，嘗試比三元搜索樹快得多，因爲需要更少的指針間接。

因此，在結構上，兩種結構都不比其他結構好。這取決於正在存儲的單詞。

爲了混合一點，簡潔的嘗試開始成爲上述兩種方法的可行替代方案。他們的空間使用比嘗試更好，儘管查找時間往往要慢得多。同樣，它取決於應用程序它們會比其他兩個選項好還是差。

至於如何構建它們 - 試圖和三元搜索樹都支持有效插入單個單詞。他們不需要事先建立一套固定的單詞。

希望這會有所幫助！