すべての提案がCでオートコンプリートされた3進検索ツリー

Question

単語が存在することを確認するために3進検索ツリーを変更することは可能でしょうか？ANDその単語で始まる 例えばdo =>dogdogs等

このsiteからのサンプルコードです。最初にすべての単語を3つのツリーにロードしてから、単語が存在するかどうかを調べるメソッドを使用できます。

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大きくする:(
言葉は何もすることができることを取得する方法。しかし、私はそのレベルでのアルゴリズムで苦手...
私は私が重複していないことを願っていますこのことについて質問。 私は理解されるであろう任意の提案。

Answer 1

そのための三元ツリーを使用することが可能であるが、私は（そうすることは容易ではない）ことをお勧めしていないと思います。

私はあると思いますあなたが使用できる2つの異なるアプローチ：

A.、使用標準トライの代わりに、三元ツリーは、そう、あなたのシーク時間は関係なく、あなたがトライを持っているどのように多くの項目、定数とみなされません。 C＃の実装は可能ですが、Trieはアルゴリズムの知識の平均/高レベルを必要としていることに注意してください。

B.標準の並べ替えられた配列（文字列[]）を使用します。プレフィックスに基づいてオートコンプリートを作成するだけで済みますので、すべての単語を文字列[]に格納し、binary searchを開始してください。 シーク時間は一定ではなく対数ですが、その配列に格納されているワード数が何百万であっても、各シークは数ミリ秒単位で測定できます（たとえば、あなたが探しているものを見つけるために操作が必要です）。バイナリ検索が成功しなかった場合でも、最も近い一致のインデックスを持ちます（しかし、インデックスは負の値になり、一致しなかったことを示します）。だから、この配列に：あなたはBを検索する場合

A 
C 
D 
E 

、あなたがステップアップを開始した場合、あなたは「B」の後にアイテムが表示されます（または「犬のA.を指し、インデックス0を取得しますあなたの例では）。

だから、でもあなたはバイナリ検索後に完全または部分一致を持って、検索されたキーワードは、辞書にある単語のat the beginningになるまでの配列から項目をリストアップしておきます。