データ構造の設計

Question

ネストされたクラスがたくさんある大きなインフラストラクチャがあり、正しいデザインパターンを探しています。含まれていますが、模式的にタイトルを見ることができます 私は項目 Aのタイトルと呼ばれる「タイトル」と呼ばれるクラスとクラスが異なる項目が含まれてしまった、各項目が異なるデータが含まれている

も含まれていITEMLIST：

I説明しますが、より多くのアイテム。 各アイテムはアイテムを含むことができます。

：私は、インフラストラクチャの概略を追加している

は、それは

要件、私はこのオブジェクトのための最良のデータ構造を探しています非バイナリツリー

のように見えます

1. ノードIDとツリーノードでは、ノードを高速で見つけることができます
2. 良いコードの保守性
3. フラットからツリー、ツリーからフラットに切り替えることができます

Answer 1

あなたの質問は、階層に関係なくID値が与えられているとすぐにノードにアクセスするように要求されているようです。この場合、ルックアップ操作は階層を気にしないので、IDのフラットなリストを「検索する」ために最適化されたフラットなリストを作成するのが、おそらくダニエル・ガブリエル（Daniel Gabriel）が示唆しているように最適です。ツリー構造内にオブジェクトを持っているからといって、別の構造でそれらのオブジェクトをインデックスに登録することはできません。辞書はこれで非常に良いはずです - 鍵は整数（またはあなたのノードIDが何であれ）であり、値はノードオブジェクトインスタンスを参照することができます。この構造をツリー構造と同期させておくことを忘れないでください。ノードが削除されたときに辞書からキーを削除し、ノードが追加されたときに辞書が辞書に追加されます（構造が動的な場合）。

これは要件1とおそらく＃2（必要に応じて同じクラスのインデックスの同期をカプセル化する場合）を満たします。 ＃3の場合、より多くの情報が必要な場合がありますが、これらの構造を同期させておくと、変換の必要なしにいつでも両方の形式にアクセスできます。非常に簡単にする必要があります。ここで

は常にフラットインデックスとツリー構造の両方を提供できる構造をカプセル化する方法を示すいくつかのサンプルコードです：

class Program 
{ 
    static void Main(string[] args) 
    { 
    Node<int, string> node1 = new Node<int, string>(1, "One"); 
    Node<int, string> node2 = new Node<int, string>(2, "Two"); 
    Node<int, string> node3 = new Node<int, string>(3, "Three"); 
    Node<int, string> node4 = new Node<int, string>(4, "Four"); 
    node2.Parent = node1; 
    node3.Parent = node1; 
    node4.Parent = node2; 
    Console.WriteLine(node1.GetDump()); 

    Node<int, string> node5 = new Node<int, string>(5, "Five"); 
    // Test spliting the tree attaching it and it's subtree to another parent 
    node2.Parent = node5; 
    Console.WriteLine(node1.GetDump()); 
    Console.WriteLine(node5.GetDump()); 

    // Test re-attaching the detached parent as a child 
    node1.Parent = node2; 
    Console.WriteLine(node5.GetDump()); 

    // Test moving a node to another parent within the tree 
    node1.Parent = node5; 
    Console.WriteLine(node5.GetDump()); 
    } 
} 

/// <summary> 
/// Create a tree structure whose nodes are of type T and are indexed by ID type I 
/// </summary> 
/// <typeparam name="I">Type of the index</typeparam> 
/// <typeparam name="T">Type of the node</typeparam> 
class Node<I, T> 
{ 
    private Dictionary<I, Node<I, T>> rootIndex; // Shared flat index 
    public I Id { get; private set; } 
    public T Value { get; set; } 
    private Node<I, T> parent; 
    List<Node<I, T>> childNodes; 

    public Node(I id, T value) 
    { 
    this.Id = id; 
    this.Value = value; 
    this.childNodes = new List<Node<I, T>>(); 
    } 

    public string GetDump() 
    { 
    System.Text.StringBuilder sb = new StringBuilder(); 
    if (parent == null) 
    { 
     foreach (KeyValuePair<I, Node<I,T>> node in rootIndex) 
     { 
      sb.Append(string.Format("{0}:{1} ", node.Key, node.Value.Value)); 
     } 
     sb.AppendLine(); 
    } 
    sb.AppendLine(string.Format("ID={0}, Value={1}, ParentId={2}", Id, Value, 
     (parent == null)?"(null)":parent.Id.ToString())); 
    foreach (Node<I, T> child in childNodes) 
    { 
     string childDump = child.GetDump(); 
     foreach (string line in childDump.Split(new string[] {Environment.NewLine}, 
      StringSplitOptions.RemoveEmptyEntries)) 
     { 
      sb.AppendLine(" " + line); 
     } 
    } 
    return sb.ToString(); 
    } 

    private void RemoveFromIndex(Dictionary<I, Node<I, T>> index) 
    { 
    index.Remove(Id); 
    foreach(Node<I, T> node in childNodes) 
     node.RemoveFromIndex(index); 
    } 

    private void ReplaceIndex(Dictionary<I, Node<I, T>> index) 
    { 
    rootIndex = index; 
    rootIndex[Id] = this; 
    foreach (Node<I, T> node in childNodes) 
     node.ReplaceIndex(index); 
    } 

    public Node<I, T> Parent 
    { 
    get 
    { 
     return parent; 
    } 
    set 
    { 
     // If this node was in another tree, remove it from the other tree 
     if (parent != null) 
     { 
      // If the tree is truly a separate tree, remove it and all nodes under 
      // it from the old tree's index completely. 
      if (value == null || (parent.rootIndex != value.rootIndex)) 
      { 
       // Split the child's index from the parent's 
       Dictionary<I, Node<I, T>> parentRootIndex = parent.rootIndex; 
       RemoveFromIndex(parentRootIndex); 
       rootIndex = new Dictionary<I, Node<I, T>>(); 
       ReplaceIndex(rootIndex); 
      } 

      // Remove it from it's old parent node's child collection 
      parent.childNodes.Remove(this); 
     } 
     // These operations only apply to a node that is not being removed 
     // from the tree 
     if (value != null) 
     { 
      // If parent does not already have an index, create one with itself listed 
      if (value.rootIndex == null) 
      { 
       value.rootIndex = new Dictionary<I, Node<I, T>>(); 
       value.rootIndex[value.Id] = value; 
      } 
      // If the index for the child node is separate form that of the parent 
      // node, merge them as appropriate 
      if (this.rootIndex != value.rootIndex) 
      { 
       // If this node has a complete index, merge the two tree indexes 
       // into the parent's index 
       if (this.rootIndex != null) 
       { 
       foreach (KeyValuePair<I, Node<I, T>> node in rootIndex) 
       { 
        if (value.rootIndex.ContainsKey(node.Key)) 
         throw new InvalidOperationException(string.Format(
         "Node Id {0} in child tree already exists in the parent", 
         node.Key)); 
        value.rootIndex[node.Key] = node.Value; 
       } 
       } 
       else 
       { 
       // If this node does not have an index, it is not a tree; 
       // just add it to the parent's index. 
       if (value.rootIndex.ContainsKey(this.Id)) 
        throw new InvalidOperationException(string.Format(
        "Node Id {0} already exists in the parent's tree.", Id)); 
       value.rootIndex[this.Id] = this; 
       } 
      } 
      // Make all nodes in a tree refer to a common root index. 
      this.rootIndex = value.rootIndex; 
      // Attach this node to the tree via the parent's child collection. 
      value.childNodes.Add(this); 
     } 
     // Attach this node to the tree via this node's parent property 
     // (null if removing from the tree) 
     this.parent = value; 
    } 
    } 


}