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

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(n) 遍历树。但是，如果您在读取 ​​XML 文件来构建节点树的同时构建另一个数据结构（用于 O(1) 访问的字典或用于 O(log n) 访问的列表），则可以构建额外的结构可以快速访问，而无需太多开销。

Answer 4

将它们存储在字典中，这为您提供了 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 5

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

Answer 6

这个答案引用了您应该能够使用的库？

Answer 7

我会说实话；我很难理解 Itay 的建议 没有完全意义。

这是您所说的要求：

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

所以 Code 是唯一的，我认为吗？然后就没有什么可以阻止您将所有 Node 对象放入 Dictionary 中。

在您对 Itay 的回答的评论中，您这样说：

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

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

提供一个简化的示例（如果我在这里侮辱了您的智力，我深表歉意，但请耐心等待，因为这至少可以向其他人澄清这一点），假设您有一个简单的 LinkedList 包含所有唯一整数。然后，您枚举该列表并使用它构造一个 Dictionary>，其想法是您希望能够根据节点的值快速找到节点。

字典是否需要知道每个节点在链表中的位置？当然不是——只是在记忆中。一旦您使用字典根据 O(1) 的值找到了节点，您当然可以使用节点本身轻松地向前或向后遍历链表，而节点本身恰好（通过设计）知道链表包含它。

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

Answer 8

为什么不使用 SortedSet构建一个包含所有 Node 实例的 BST？比较器将基于Code - 容器必须限定范围，以便这在所有成员中都是唯一的。