从邻接表创建树的最有效方法

Question

我有一个对象的邻接表（从 SQL 数据库中加载行及其父键），需要用它来构建一个无序树。保证不会有循环。

这太慢了（仅在约 5 分钟内处理了大约 3K 个节点中的 870K 个）。在我的工作站 Core 2 Duo 上运行，有足够的 RAM。

有什么想法可以让这个过程更快吗？

public class StampHierarchy {
    private StampNode _root;
    private SortedList<int, StampNode> _keyNodeIndex;

    // takes a list of nodes and builds a tree
    // starting at _root
    private void BuildHierarchy(List<StampNode> nodes)
    {
        Stack<StampNode> processor = new Stack<StampNode>();
        _keyNodeIndex = new SortedList<int, StampNode>(nodes.Count);

        // find the root
        _root = nodes.Find(n => n.Parent == 0);

        // find children...
        processor.Push(_root);
        while (processor.Count != 0)
        {
            StampNode current = processor.Pop();

            // keep a direct link to the node via the key
            _keyNodeIndex.Add(current.Key, current);  

            // add children
            current.Children.AddRange(nodes.Where(n => n.Parent == current.Key));

            // queue the children
            foreach (StampNode child in current.Children)
            {
                processor.Push(child);
                nodes.Remove(child); // thought this might help the Where above
            }
        }
    }
}

    public class StampNode {
         // properties: int Key, int Parent, string Name, List<StampNode> Children
    }

- Jeff Meatball Yang

---

你一定要用C#来做这件事吗？因为在SQL中按路径排序会更快，你可以在O(N)的时间内构建一棵树。 - Aaronaught

如何在SQL中按路径排序？我的数据类似于组织结构图...有很多子级和不规则的层级。 - Jeff Meatball Yang

Answer 1

1. 将节点放入一个有序列表或字典中。

2. 扫描该列表，选择每个节点，在同一列表中找到其父节点（二分查找或字典查找），将其添加到父节点的Children集合中。

不需要使用Stack将其放入树中。

- Ian Mercer

---

值得注意的是，在将节点放入排序列表之前按键排序可以大大提高速度。如果内存不是主要限制，则使用字典也是另一种选择。 - Codism

Answer 2

在这种情况下，SortedList不是一个好的容器。对于插入操作（Add()的重复调用），它的时间复杂度为O(n)，因为它内部表示为一个平面列表。使用Dictionary而不是SortedList会有很大的改进，因为它的插入时间复杂度为O(1)。

- Gary Linscott

---

啊，我还错过了current.Children.AddRange这一行。你不想重新扫描整个节点列表来搜索每个父节点。正如Hightechrider建议的那样，首先将节点放入字典中会极大地加快速度，因为你再次将一个O(n)操作变成了一个O(1)操作。 - Gary Linscott