Как эффективно искать эту иерархическую структуру?

Question

У меня есть структура данных, которая выглядит следующим образом:

public class Node 
{ 
    public string Code { get; set; } 
    public string Description { get; set; } 
    ... 
    public List<Node> Children { get; set; } 
} 

Я хочу написать метод, который будет возвращать конкретный узел, заданный указанным Code. Обычно я просто делал рекурсивную прогулку по иерархии, чтобы найти узел, но меня беспокоит производительность. В иерархии будет несколько тысяч узлов, и этот метод будет называться много раз.

Как структурировать это, чтобы сделать его быстрее? Могу ли я использовать существующую структуру данных, которая, возможно, выполняет двоичный поиск по Code, сохраняя при этом иерархическую структуру без повторной реализации какой-либо формы бинарного поиска?

Answer 1

Добавьте все узлы в словарь с кодом в качестве ключа. (вы можете сделать это один раз), поиск в словаре в основном O (1).

void FillDictionary(Dictionary<string, Node> dictionary, Node node) 
{ 
    if (dictionary.ContainsKey(node.Code)) 
    return; 

    dictionary.Add(node.Code, node); 

    foreach (Node child in node.Children) 
    FillDictionary(dictionary, child) 
} 

Если вы знаете корень, использование будет:

var dictionary = new Dictionary<string, Node>(); 
FillDictionary(dictionary, rootNode); 

Если вы не можете вызвать метод FillDictionary() на все узлы с тем же словарем.

Answer 2

Если вы можете изменить порядок узлов, вы можете сделать Binary Search Tree.

Answer 3

Без какой-либо организации на основе сравнения для кода вы ничего не можете сделать, чтобы предотвратить прохождение O (n) дерева. Однако, если вы создадите другую структуру данных (либо доступ к словарю для O (1), либо доступ к списку для вывода (log n)), в то же время вы читаете через свой XML-файл, чтобы построить дерево узлов, вы можете создать дополнительную структуру для быстрого доступа без дополнительных накладных расходов.

Answer 4

This SO answer ссылки на библиотеку, которую вы должны уметь использовать?

Answer 5

Почему бы не использовать SortedSet<Node> для создания BST, содержащего все экземпляры вашего узла? Компаратор будет основан на Code - контейнер должен быть ограничен таким, чтобы он был уникальным для всех участников.

Answer 6

Храните их в словаре, это дает вам O (1) время поиска.

var dict = new Dictionary<string, Node>(); 
dict.Add(n.Code, n); 

Предполагая n является гидратированный Node объектом. Затем, чтобы получить конкретный элемент узла, вы можете сделать

var node = dict["CODEKEY"]; 

, который вернет ваш конкретный узел в соответствии с предоставленным ключом. Вы даже можете проверить узел существует с помощью:

if (d.ContainsKey("CODEKEY")) 
{ 
    //Do something 
} 

Для того, чтобы знать, где узел был в оригинальной коллекции вам нужно будет добавить какое-то иерархия указателей на свой класс Node таким образом, чтобы он имел знание предыдущего узел

Answer 7

Буду честным; Мне очень трудно понять, как Itay's suggestion не имеет никакого смысла.

Вот это требование, что вы заявили:

Я хочу написать метод, который будет возвращать конкретный узел, заданный указанным Code.

Значит, Code уникален, я понимаю? Тогда нет ничего, что помешает вам помещать все ваши объекты Node в Dictionary<string, Node>.

В своих комментариях к ответу Итайте ты сказать:

Я понимаю, что словарь представляет собой плоский индекс, я просто не понимаю, но как этот показатель будет лезет в иерархическую структуру данных и получить правильный узел.

Если вы имеете в виду вы не понимаете, как словарь будет знать, где ваш Node в структуре данных , это потому, что это не так. Это имеет значение? Вы не указали в своих требованиях, что хотите знать, где находится узел в структуре данных; вы указали только, что хотите получить узел. Чтобы сделать это, словарь должен знать только, где находится узел в памяти, а не в какой-то полностью отдельной структуре данных.

Чтобы упростить пример (и я прошу прощения, если я оскорбляю ваш интеллект здесь, но неся со мной, поскольку это может по крайней мере прояснить смысл для кого-то другого), предположим, что у вас есть простой LinkedList<int>, содержащий все уникальные целые числа. Затем вы перечисляете этот список и используете его для построения Dictionary<int, LinkedListNode<int>>, предполагая, что вы хотите быстро найти узел на основе его значения.

Нужно ли в словаре знать, где в связанном списке у каждого узла есть? Конечно, не только там, где он находится в памяти. После того, как вы нашли свой узел на основе его значения в O (1) с помощью словаря, вы, конечно, можете легко пересечь связанный список вперед или назад, используя сам узел, который, как известно, известен (по дизайну) связанного списка содержащий его.

Это то же самое, что и в вашей иерархической структуре, только немного сложнее, чем связанный список. Но тот же принцип применяется.

Answer 8

Вот полная реализация того, о чем я и другие говорили. Обратите внимание, что, имея индексный словарь, вы будете использовать немного больше памяти (только ссылки на узлы) в обмен на более быстрый поиск. Я использую события для динамического обновления индекса.

Редактировать: Добавлено комментариев и исправлено несколько вещей.

using System; 
using System.Collections.Generic; 
using System.Collections.ObjectModel; 
using System.Reflection; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      // Create the root node for the tree 
      MyNode rootNode = new MyNode { Code = "abc", Description = "abc node" }; 

      // Instantiate a new tree with the given root node. string is the index key type, "Code" is the index property name 
      var tree = new IndexedTree<MyNode, string>("Code", rootNode); 

      // Add a child to the root node 
      tree.Root.AddChild(new MyNode { Code = "def", Description = "def node" }); 

      MyNode newNode = new MyNode { Code = "foo", Description = "foo node" }; 

      // Add a child to the first child of root 
      tree.Root.Children[0].AddChild(newNode); 

      // Add a child to the previously added node 
      newNode.AddChild(new MyNode { Code = "bar", Description = "bar node" }); 


      // Show the full tree 
      Console.WriteLine("Root node tree:"); 
      PrintNodeTree(tree.Root, 0); 

      Console.WriteLine(); 

      // Find the second level node 
      MyNode foundNode = tree.FindNode("def"); 

      if (foundNode != null) 
      { 
       // Show the tree starting from the found node 
       Console.WriteLine("Found node tree:"); 
       PrintNodeTree(foundNode, 0); 
      } 

      // Remove the last child 
      foundNode = tree.FindNode("foo"); 
      TreeNodeBase nodeToRemove = foundNode.Children[0]; 
      foundNode.RemoveChild(nodeToRemove); 

      // Add a child to this removed node. The tree index is not updated. 
      nodeToRemove.AddChild(new MyNode { Code = "blah", Description = "blah node" }); 

      Console.ReadLine(); 
     } 

     static void PrintNodeTree(MyNode node, int level) 
     { 
      Console.WriteLine(new String(' ', level * 2) + "[" + node.Code + "] " + node.Description); 

      foreach (MyNode child in node.Children) 
      { 
       // Recurse through each child 
       PrintNodeTree(child, ++level); 
      } 
     } 
    } 

    public class NodeEventArgs : EventArgs 
    { 
     public TreeNodeBase Node { get; private set; } 

     public bool Cancel { get; set; } 

     public NodeEventArgs(TreeNodeBase node) 
     { 
      this.Node = node; 
     } 
    } 

    /// <summary> 
    /// The base node class that handles the hierarchy 
    /// </summary> 
    public abstract class TreeNodeBase 
    { 
     /// <summary> 
     /// A read-only list of children so that you are forced to use the proper methods 
     /// </summary> 
     public ReadOnlyCollection<TreeNodeBase> Children 
     { 
      get { return new ReadOnlyCollection<TreeNodeBase>(this.children); } 
     } 

     private IList<TreeNodeBase> children; 

     /// <summary> 
     /// Default constructor 
     /// </summary> 
     public TreeNodeBase() 
      : this(new List<TreeNodeBase>()) 
     { 
     } 

     /// <summary> 
     /// Constructor that populates children 
     /// </summary> 
     /// <param name="children">A list of children</param> 
     public TreeNodeBase(IList<TreeNodeBase> children) 
     { 
      if (children == null) 
      { 
       throw new ArgumentNullException("children"); 
      } 

      this.children = children; 
     } 

     public event EventHandler<NodeEventArgs> ChildAdding; 

     public event EventHandler<NodeEventArgs> ChildRemoving; 

     protected virtual void OnChildAdding(NodeEventArgs e) 
     { 
      if (this.ChildAdding != null) 
      { 
       this.ChildAdding(this, e); 
      } 
     } 

     protected virtual void OnChildRemoving(NodeEventArgs e) 
     { 
      if (this.ChildRemoving != null) 
      { 
       this.ChildRemoving(this, e); 
      } 
     } 

     /// <summary> 
     /// Adds a child node to the current node 
     /// </summary> 
     /// <param name="child">The child to add.</param> 
     /// <returns>The child node, if it was added. Useful for chaining methods.</returns> 
     public TreeNodeBase AddChild(TreeNodeBase child) 
     { 
      NodeEventArgs eventArgs = new NodeEventArgs(child); 
      this.OnChildAdding(eventArgs); 

      if (eventArgs.Cancel) 
      { 
       return null; 
      } 

      this.children.Add(child); 
      return child; 
     } 

     /// <summary> 
     /// Removes the specified child in the current node 
     /// </summary> 
     /// <param name="child">The child to remove.</param> 
     public void RemoveChild(TreeNodeBase child) 
     { 
      NodeEventArgs eventArgs = new NodeEventArgs(child); 
      this.OnChildRemoving(eventArgs); 

      if (eventArgs.Cancel) 
      { 
       return; 
      } 

      this.children.Remove(child); 
     } 
    } 

    /// <summary> 
    /// Your custom node with custom properties. The base node class handles the tree structure. 
    /// </summary> 
    public class MyNode : TreeNodeBase 
    { 
     public string Code { get; set; } 
     public string Description { get; set; } 
    } 

    /// <summary> 
    /// The main tree class 
    /// </summary> 
    /// <typeparam name="TNode">The node type.</typeparam> 
    /// <typeparam name="TIndexKey">The type of the index key.</typeparam> 
    public class IndexedTree<TNode, TIndexKey> where TNode : TreeNodeBase, new() 
    { 
     public TNode Root { get; private set; } 

     public Dictionary<TIndexKey, TreeNodeBase> Index { get; private set; } 

     public string IndexProperty { get; private set; } 

     public IndexedTree(string indexProperty, TNode rootNode) 
     { 
      // Make sure we have a valid indexProperty 
      if (String.IsNullOrEmpty(indexProperty)) 
      { 
       throw new ArgumentNullException("indexProperty"); 
      } 

      Type nodeType = rootNode.GetType(); 
      PropertyInfo property = nodeType.GetProperty(indexProperty); 

      if (property == null) 
      { 
       throw new ArgumentException("The [" + indexProperty + "] property does not exist in [" + nodeType.FullName + "].", "indexProperty"); 
      } 

      // Make sure we have a valid root node 
      if (rootNode == null) 
      { 
       throw new ArgumentNullException("rootNode"); 
      } 

      // Set the index properties 
      this.IndexProperty = indexProperty; 
      this.Index = new Dictionary<TIndexKey, TreeNodeBase>(); 

      // Add the root node 
      this.Root = rootNode; 

      // Notify that we have added the root node 
      this.ChildAdding(this, new NodeEventArgs(Root)); 
     } 

     /// <summary> 
     /// Find a node with the specified key value 
     /// </summary> 
     /// <param name="key">The node key value</param> 
     /// <returns>A TNode if found, otherwise null</returns> 
     public TNode FindNode(TIndexKey key) 
     { 
      if (Index.ContainsKey(key)) 
      { 
       return (TNode)Index[key]; 
      } 

      return null; 
     } 

     private void ChildAdding(object sender, NodeEventArgs e) 
     { 
      if (e.Node.Children.Count > 0) 
      { 
       throw new InvalidOperationException("You can only add nodes that don't have children"); 
       // Alternatively, you could recursively get the children, set up the added/removed events and add to the index 
      } 

      // Add to the index. Add events as soon as possible to be notified when children change. 
      e.Node.ChildAdding += new EventHandler<NodeEventArgs>(ChildAdding); 
      e.Node.ChildRemoving += new EventHandler<NodeEventArgs>(ChildRemoving); 
      Index.Add(this.GetNodeIndex(e.Node), e.Node); 
     } 

     private void ChildRemoving(object sender, NodeEventArgs e) 
     { 
      if (e.Node.Children.Count > 0) 
      { 
       throw new InvalidOperationException("You can only remove leaf nodes that don't have children"); 
       // Alternatively, you could recursively get the children, remove the events and remove from the index 
      } 

      // Remove from the index. Remove events in case user code keeps reference to this node and later adds/removes children 
      e.Node.ChildAdding -= new EventHandler<NodeEventArgs>(ChildAdding); 
      e.Node.ChildRemoving -= new EventHandler<NodeEventArgs>(ChildRemoving); 
      Index.Remove(this.GetNodeIndex(e.Node)); 
     } 

     /// <summary> 
     /// Gets the index key value for the given node 
     /// </summary> 
     /// <param name="node">The node</param> 
     /// <returns>The index key value</returns> 
     private TIndexKey GetNodeIndex(TreeNodeBase node) 
     { 
      TIndexKey key = (TIndexKey)node.GetType().GetProperty(this.IndexProperty).GetValue(node, null); 
      if (key == null) 
      { 
       throw new ArgumentNullException("The node index property [" + this.IndexProperty + "] cannot be null", this.IndexProperty); 
      } 

      return key; 
     } 
    } 
}