3

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

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

另一种方法是递归方法，这意味着搜索对象的直接子级并重复该过程以进行下一个级别。不幸的是，树是单向的……没有直接接近孩子的方法，这只会比以前的方法稍微便宜一点。

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

谢谢，

尤瓦尔=8-)

4

4 回答 4

3

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

于 2008-10-16T16:19:58.050 回答
3

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

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

以下是我在 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) 之间。您可以保证查看列表中的每个节点，再加上一些操作来查找节点的所有后代 - 在最坏的情况下（如果您在根节点上运行算法），您正在查看列表中的每个节点列表两次。

于 2008-10-16T17:05:58.767 回答
0

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

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

于 2008-10-16T16:17:39.193 回答
0

构建一个对象指向其直系子级的树可能是最好的方法，尤其是在您需要进行未来查找时。建造树很大程度上取决于原始树的高度。最多需要 O(n^2)。

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

于 2008-10-16T17:00:11.620 回答