4

Trie各ノードが単語を表すデータ構造を開発しています。したがって、単語st、stack、stackoverflowおよびoverflowは次のように配置されます。

root
--st
---stack
-----stackoverflow
--overflow

My Trie はHashTable内部的に を使用しているため、すべてのノード ルックアップに一定の時間がかかります。以下は、アイテムをトライに挿入するために思いついたアルゴリズムです。

  1. トライでアイテムの存在を確認します。存在する場合は戻り、存在しない場合はステップ 2 に進みます。
  2. の各文字を繰り返しkey、単語の存在を確認します。新しい値を子として追加できるノードを取得するまで、これを行います。ノードが見つからない場合は、ルート ノードの下に追加されます。
  3. 挿入後、新しいノードが挿入されたノードの兄弟を再配置します。これにより、すべての兄弟がウォークスルーされ、新しく挿入されたノードと比較されます。いずれかのノードが新しいノードと同じ文字で始まる場合、そこから移動され、新しいノードの子として追加されます。

これがトライを実装する正しい方法かどうかはわかりません。提案や改善は大歓迎です。

使用言語：C++

4

2 に答える 2

7

トライは次のようになります

                      ROOT
             overflow/    \st
                    O      O
                            \ack
                             O
                              \overflow
                               O

通常、トライの一部としてハッシュ テーブルを使用する必要はありません。トライ自体はすでに効率的なインデックス データ構造です。もちろん、それはできます。

とにかく、ステップ (2) は、ハッシュ関数を照会するだけでなく、検索中に実際にトライを下降する必要があります。このようにして、挿入ポイントを簡単に見つけることができ、後で別の手順として検索する必要がなくなります。

ステップ（3）は間違っていると思います。トライを再配置する必要はありません。実際、トライに格納するのは追加の文字列フラグメントにすぎないため、再配置することはできません。上の写真を参照してください。

于 2010-02-11T15:00:56.290 に答える
1

以下は、挿入アルゴリズムの Java コードです。

public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 }

詳細なチュートリアルについては、こちらを参照してください。

于 2012-07-26T10:41:51.110 に答える