高效遍历单向树

Question

我有一个单向对象树，其中每个对象都指向其父对象。 给定一个对象，我需要获取其整个后代子树，作为对象的集合。 这些对象实际上并不在任何数据结构中，但我可以轻松获取所有对象的集合。

最简单的方法是检查批处理中的每个对象，查看给定的对象是否是祖先，然后将其放在一边。 这不会太高效...它会带来 O(N*N) 的开销，其中 N 是对象的数量。

另一种方法是递归方法，即搜索对象的直接子对象并在下一个级别重复该过程。 不幸的是，这棵树是单向的……没有直接到达子节点的方法，而且这只会比以前的方法稍微便宜一点。

我的问题：我在这里忽略了一种有效的算法吗？

谢谢，

尤瓦尔=8-)

Answer 1

正如其他人提到的，构建对象的哈希表/映射到其（直接）子对象的列表。

从那里您可以轻松查找“目标对象”的直接子对象列表，然后对于列表中的每个对象重复该过程。

下面是我在 Java 中使用泛型的方法，使用队列而不是任何递归：

public static Set<Node> findDescendants(List<Node> allNodes, Node thisNode) {

    // keep a map of Nodes to a List of that Node's direct children
    Map<Node, List<Node>> map = new HashMap<Node, List<Node>>();

    // populate the map - this is O(n) since we examine each and every node
    // in the list
    for (Node n : allNodes) {

        Node parent = n.getParent();
        if (parent != null) {

            List<Node> children = map.get(parent);
            if (children == null) {
                // instantiate list
                children = new ArrayList<Node>();
                map.put(parent, children);
            }
            children.add(n);
        }
    }


    // now, create a collection of thisNode's children (of all levels)
    Set<Node> allChildren = new HashSet<Node>();

    // keep a "queue" of nodes to look at
    List<Node> nodesToExamine = new ArrayList<Node>();
    nodesToExamine.add(thisNode);

    while (nodesToExamine.isEmpty() == false) {
        // pop a node off the queue
        Node node = nodesToExamine.remove(0);

        List<Node> children = map.get(node);
        if (children != null) {
            for (Node c : children) {
                allChildren.add(c);
                nodesToExamine.add(c);
            }
        }
    }

    return allChildren;
}

如果我记得如何计算的话，预期执行时间介于 O(n) 和 O(2n) 之间。 您一定会查看列表中的每个节点，再加上一些操作来查找节点的所有后代 - 在最坏的情况下（如果您在根节点上运行算法），您将查看列表中的每个节点列表两次。

Answer 2

数据库的工作方式相同，所以做数据库的事情。 建立一个从父级映射到子级列表的哈希表。 这需要 O(n)。 然后使用该哈希表将使查找和查询可能更加高效。

Answer 3

您的问题有点抽象，但是 嵌套集 （向下滚动，可能有点太特定于 mysql）可能是您的一个选择。 尽管任何修改都非常复杂（并且平均必须修改一半的树），但读取操作的速度非常快。

但这需要能够修改数据结构。 我想如果您可以修改结构，您也可以添加对子对象的引用。 如果你不能修改结构，我怀疑还有什么比你的想法更快的了。

Answer 4

构建一棵树，其中的对象指向其直接子对象可能是最好的方法，特别是如果您需要进行未来的查找。 建造树很大程度上取决于原始树的高度。 最多需要 O(n^2)。

在构建树时，构建一个哈希表。 哈希表将使未来搜索特定对象的速度更快（O(1) 与 O(n)）。