treeviewブランチを追加する最も効率的なアルゴリズム

Question

ツリービューにブランチ（ノード）を追加する必要があります。私は最も低いO（n）技法が何であるかを決めるのに苦労しています。

次のように私のデータが提示：

Id ParentId Value 

0 null  Bob 
1 0   Amy 
2 1   Susan 
3 1   Matt 
4 2   Keith 
5 4   Craig 
6 4   Derrick 

だから、ツリーは次のようになります。

私が思い付くことができるすべては、すべてのエントリをスキャン用^ 2のアルゴリズムnはサブノードとして属しているかどうかを確認します。 アレイからエントリを削除して、追加時にスキャンします。だからメモリが（おそらくない）提供するならn^2より少し小さいです。

もっと良いテクニックはありますか？

Answer 1

あなたの言語がある種のリスト/ベクトル/サイズ変更可能な配列型を持っていると仮定すると、これはかなり簡単です。

IDごとに空のリストを作成します。各行を繰り返し、ParentIdがnullでない場合は、そのIDをParentIdのリストに追加します。

O（n）時間内に各エントリの子があります。