How to effectively look for this hierarchical structure?

Question

I have a data structure that looks like this:

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

I want to write a method that will return a specific node, given the specified Code . Usually I just took a recursive walk through the hierarchy to find the node, but performance bothers me. There will be several thousand nodes in the hierarchy, and this method will be called many times.

How can I structure this to make it faster? Can I use an existing data structure that possibly performs a binary search on Code , preserving the hierarchical structure, without processing the form of the binary search itself?

Answer 1

Add all nodes to the code key dictionary. (you can do this once), the search in the dictionary is mainly 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) } 

If you know the root, use will be:

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

If you do not, you can call the FillDictionary() method on all of your nodes with the same dictionary.

Answer 2

Here is the full realization of what I and others have been talking about. Please note that if you have an index dictionary, you will use a little more memory (only links to nodes) in exchange for a faster search. I use events to dynamically update the index.

Edit: Added comments and fixed some things.

 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

Without any organization based on comparisons for code, you cannot do anything to prevent the O (n) tree from going through. However, if you create a different data structure (either access to the dictionary for O (1) or access to the output list (log n)), at the same time you are reading through your XML file to build the Node tree, you can create additional structure for quick access without additional overhead.

Answer 4

Keep them in a dictionary, this gives you O (1) search time.

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

Assuming n is a hydrated Node object. Then, to get a specific node element, you can do

 var node = dict["CODEKEY"]; 

which will return your specific node according to the provided key. You can even check node using:

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

To find out where the node is in the source collection, you need to add some hierarchy of pointers to your node class so that it knows about the previous node

Answer 5

If you can reorder the nodes, you can do a binary search tree .

Answer 6

Does this SO answer reference the library you should use?

Answer 7

I will be honest; I have great difficulty understanding how the Itai sentence makes no sense.

Here is the requirement you specified:

I want to write a method that will return a specific node, given the specified Code .

So, Code is unique, as I understand it? Then it didn't hurt to put all of your Node objects in a Dictionary<string, Node> .

In your comments on Itay's answer, you say the following:

I get that the dictionary is a flat index, I still do not understand how this index gets into my hierarchical data structure and returns the correct node.

If you mean that you don’t understand how the dictionary will know where your Node is in the data structure, this is because it is not. Does it matter? You did not indicate in your requirements that you want to know where the node is in the data structure; you specified only that you want to receive node. For this, the dictionary needs to know only where the node is, and not in some completely separate data structure.

To provide a simplified example (and I apologize if I insult your intelligence here, but carrying with me, as this can at least clear up a point for someone else), suppose you had a simple LinkedList<int> containing all unique integers numbers, then you list this list and use it to create a Dictionary<int, LinkedListNode<int>> , assuming you want to quickly find a node based on its value.

Does the dictionary need to know where the node is in the linked list? Of course, not only where he is in memory. After you find your node based on its value in O (1) using the dictionary, you can of course easily traverse the linked list forward or backward using the node itself, which is known to have a linked list containing it.

The same thing with your hierarchical structure, only a little more complicated than a linked list. But the same principle applies.

Answer 8

Why not use a SortedSet <Node> to create a BST containing all of your Node instances? The comparator will be based on Code - the container should be limited so that it is unique to all members.