如何有效地搜索此层次结构？

我有一个如下所示的数据结构：

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

在给定指定的Code ，我想编写一个返回特定节点的方法。 通常我会在层次结构中进行递归遍历以找到节点，但我关注性能。 层次结构中将有数千个节点，并且此方法将被多次调用。

如何构建它以使其更快？ 我是否可以使用现有的数据结构，可能在保留层次结构的同时对Code执行二进制搜索，而不是自己重新实现某种forms的二进制搜索？

Answer 1

将所有节点添加到字典中，并将代码作为键。 （你可以做一次），字典中的查找基本上是O（1）。

 void FillDictionary(Dictionary dictionary, Node node) { if (dictionary.ContainsKey(node.Code)) return; dictionary.Add(node.Code, node); foreach (Node child in node.Children) FillDictionary(dictionary, child) } 

如果你知道root，用法将是：

 var dictionary = new Dictionary(); 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("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; } } /// 
 /// The base node class that handles the hierarchy /// 
 public abstract class TreeNodeBase { /// 
 /// A read-only list of children so that you are forced to use the proper methods /// 
 public ReadOnlyCollection Children { get { return new ReadOnlyCollection(this.children); } } private IList children; /// 
 /// Default constructor /// 
 public TreeNodeBase() : this(new List()) { } /// 
 /// Constructor that populates children /// 
 /// A list of children public TreeNodeBase(IList children) { if (children == null) { throw new ArgumentNullException("children"); } this.children = children; } public event EventHandler ChildAdding; public event EventHandler 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); } } /// 
 /// Adds a child node to the current node /// 
 /// The child to add. /// The child node, if it was added. Useful for chaining methods. public TreeNodeBase AddChild(TreeNodeBase child) { NodeEventArgs eventArgs = new NodeEventArgs(child); this.OnChildAdding(eventArgs); if (eventArgs.Cancel) { return null; } this.children.Add(child); return child; } /// 
 /// Removes the specified child in the current node /// 
 /// The child to remove. public void RemoveChild(TreeNodeBase child) { NodeEventArgs eventArgs = new NodeEventArgs(child); this.OnChildRemoving(eventArgs); if (eventArgs.Cancel) { return; } this.children.Remove(child); } } /// 
 /// Your custom node with custom properties. The base node class handles the tree structure. /// 
 public class MyNode : TreeNodeBase { public string Code { get; set; } public string Description { get; set; } } /// 
 /// The main tree class /// 
 /// The node type. /// The type of the index key. public class IndexedTree where TNode : TreeNodeBase, new() { public TNode Root { get; private set; } public Dictionary 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(); // Add the root node this.Root = rootNode; // Notify that we have added the root node this.ChildAdding(this, new NodeEventArgs(Root)); } /// 
 /// Find a node with the specified key value /// 
 /// The node key value /// A TNode if found, otherwise null 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(ChildAdding); e.Node.ChildRemoving += new EventHandler(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(ChildAdding); e.Node.ChildRemoving -= new EventHandler(ChildRemoving); Index.Remove(this.GetNodeIndex(e.Node)); } /// 
 /// Gets the index key value for the given node /// 
 /// The node /// The index key value 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

没有任何基于比较的Code组织，你无法阻止树的O（n）演练。 但是，如果您在读取XML文件以构建节点树的同时构建另一个数据结构（O（1）访问字典或O（log n）访问列表），则可以构建快速访问的附加结构，无需更多开销。

Answer 4

将它们存储在字典中，这为您提供了O（1）查找时间。

 var dict = new Dictionary(); dict.Add(n.Code, n); 

假设n是一个水合Node对象。 然后获取您可以执行的特定节点项

 var node = dict["CODEKEY"]; 

它将根据提供的密钥返回您的特定节点。 您甚至可以使用以下命令检查节点

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

为了知道节点在原始集合中的位置，您需要向Node类添加某种指针层次结构，以便它了解前一节点

Answer 5

如果您可以更改节点的顺序，则可以创建二进制搜索树 。

Answer 6

这个SO答案引用了一个你应该可以使用的库？

Answer 7

我会说实话; 我很难理解Itay的建议是不是很完美。

以下是您所说的要求：

在给定指定的Code ，我想编写一个返回特定节点的方法。

所以Code是独一无二的，我接受了吗？ 然后没有什么能阻止你将所有Node对象放入Dictionary 。

在你对Itay的答案的评论中，你这样说：

我得知字典是一个平面索引，我只是不明白该索引将如何进入我的分层数据结构并检索正确的节点。

如果你的意思是你不理解字典将如何知道你的Node 在数据结构中的位置 ，那是因为它不是。 这有关系吗？ 您没有在要求中说明您想知道节点在数据结构中的位置; 您只指定要获取节点 。 为了做到这一点，字典只需要知道节点在内存中的位置，而不是一些完全独立的数据结构。

提供一个简化的例子（如果我在这里侮辱你的情报，我很抱歉，但是因为这可能至少澄清了其他人的观点），假设你有一个包含所有唯一整数的普通LinkedList 。 然后，您枚举此列表并使用它来构造Dictionary> ，这个想法是您希望能够根据其值快速查找节点。

字典是否需要知道每个节点在链表中的位置？ 当然不仅仅是它在记忆中的位置。 一旦您使用字典在O（1）中找到了基于其值的节点，您当然可以使用节点本身轻松地向前或向后遍历链表，这恰好意识到（按设计）链表包含它。

它与您的层次结构相同，只比链表更复杂。 但同样的原则也适用。

Answer 8

为什么不使用SortedSet 来构建包含所有Node实例的BST？ 比较器将基于Code – 容器必须具有范围，以使其在所有成员中是唯一的。