C＃中的所有建議自動完成的三元搜索樹＃

我想知道是否有可能修改三元搜索樹來檢查該單詞是否存在AND找到以該單詞開始的所有單詞（或以該單詞結束？）？例如do =>dogdogs等C＃中的所有建議自動完成的三元搜索樹＃

從這site是一個示例代碼。首先將所有單詞加載到三元樹，然後我們可以使用方法來檢查單詞是否存在。

public class TernaryTree 
{ 
    private Node m_root = null; 

    private void Add(string s, int pos, ref Node node) 
    { 
     if (node == null) { node = new Node(s[pos], false); } 

     if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); } 
     else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); } 
     else 
     { 
      if (pos + 1 == s.Length) { node.m_wordEnd = true; } 
      else { Add(s, pos + 1, ref node.m_center); } 
     } 
    } 

    public void Add(string s) 
    { 
     if (s == null || s == "") throw new ArgumentException(); 

     Add(s, 0, ref m_root); 
    } 

    public bool Contains(string s) 
    { 
     if (s == null || s == "") throw new ArgumentException(); 

     int pos = 0; 
     Node node = m_root; 
     while (node != null) 
     { 
      int cmp = s[pos] - node.m_char; 
      if (s[pos] < node.m_char) { node = node.m_left; } 
      else if (s[pos] > node.m_char) { node = node.m_right; } 
      else 
      { 
       if (++pos == s.Length) return node.m_wordEnd; 
       node = node.m_center; 
      } 
     } 

     return false; 
    } 
} 

class Node 
{ 
    internal char m_char; 
    internal Node m_left, m_center, m_right; 
    internal bool m_wordEnd; 

    public Node(char ch, bool wordEnd) 
    { 
     m_char = ch; 
     m_wordEnd = wordEnd; 
    } 
}

這讓我在我的腦海loome大:(
任何方式獲取的話可以是任何東西，但我與該級別的算法弱..
我希望，我不重複這個我覺得有任何問題。任何建議，我會爲感激。

來源

2011-11-21 deadfish

它可以使用三叉樹對於這一點，但我不建議（不容易做到）。

您可以使用兩種不同的方法：

A.，使用標準特里而不是三元樹，使您的查找時間將被認爲是恆定的，不管你有多少條目在特里。 C＃實現是可以實現的，但請記住，Trie需要算法知識的平均水平/高水平。

B.，使用標準的排序數組（字符串[]）。由於您的要求只是基於前綴創建自動完成，請將所有單詞存儲在字符串[]中，然後在其上啓動一個binary search。尋道時間並不是恆定的，而是對數的，但即使您在該數組中存儲了數百萬個字，每個尋道都可以在幾分之一毫秒內測量（例如，如果該數組中有一百萬字，操作是需要找到你正在尋找的）。即使二分查找不成功，您也會得到最接近匹配的索引（但索引將爲負值，表示匹配不成功）。所以，這個數組中：

A 
C 
D 
E

如果搜索B，您將得到指數0，指向A.如果你開始加緊，你會看到「B」（或「狗」後事項在你的例子中）。

所以，即使你有一個完整的或部分匹配的二進制搜索後，保持上市從數組中的項目，直到所搜索的關鍵詞是字典字at the beginning。

來源

2012-01-25 09:53:36 Adam

C＃中的所有建議自動完成的三元搜索樹＃

回答

相關問題