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

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

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

Изменить: Добавлены комментарии и исправлены некоторые вещи.

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;
        }
    }
}

Answer 3

Храните их в Словаре, это дает вам 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 4

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

Answer 5

Я буду честен;Мне очень трудно понять, как предложение Итая не имеет смысла.

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

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

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

В ваших комментариях к ответу Итая вы говорите следующее:

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

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

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

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

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

Answer 6

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

Answer 7

Если вы можете изменить порядок узлов, вы можете создать Дерево двоичного поиска .

Answer 8

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