时间戳

首页 > 解决方案 > 为什么这个共同祖先解决方案具有更好的最坏情况性能？

java - 为什么这个共同祖先解决方案具有更好的最坏情况性能？

问题描述

我正在寻找两种解决方案来找到二叉树（不一定是二叉搜索树）中两个节点的第一个共同祖先。我被告知第二种解决方案提供了更好的最坏情况运行时间，但我不知道为什么。有人可以启发我吗？

解决方案1： 

import com.foo.graphstrees.BinaryTreeNodeWithParent;

/*
   Find the first common ancestor to 2 nodes in a binary tree.
*/
public class FirstCommonAncestorFinder {

    public BinaryTreeNodeWithParent find(BinaryTreeNodeWithParent p, BinaryTreeNodeWithParent q) {

        int delta = depth(p) - depth(q);
        BinaryTreeNodeWithParent first = delta > 0 ? q: p; // use shallower node
        BinaryTreeNodeWithParent second = delta > 0 ? p: q; //use deeper

        second = goUp(second, delta); // move up so they are level, if 1 node is deeper in the tree than the other, their common ancestor obviously cannot be below the shallower node, so we start them off at the same height in the tree


        //keep going up the tree, once first == second, stop
        while(!first.equals(second) && first !=null && second !=null) {
            first = first.getParent();
            second = second.getParent();
        }

        return first == null || second == null ? null : first;

    }

    private int depth(BinaryTreeNodeWithParent n) {
        int depth = 0;
        while (n != null) {
            n = n.getParent();
            depth++;
        }
        return depth;
    }

    private BinaryTreeNodeWithParent goUp(BinaryTreeNodeWithParent node, int delta) {

        while (delta > 0 && node != null) {
            node = node.getParent();
            delta--;
        }
        return node;
    }
}

解决方案2：

import com.foo.graphstrees.BinaryTreeNodeWithParent;

public class FirstCommonAncestorImproved {

    public BinaryTreeNodeWithParent find(BinaryTreeNodeWithParent root,
                                         BinaryTreeNodeWithParent a,
                                         BinaryTreeNodeWithParent b) {

        if (!covers(root, a) || !covers(root, b)) {
            return null;
        } else if (covers(a, b)) {
            return a;
        } else if (covers(b, a)) {
            return b;
        }

        var sibling = getSibling(a);
        var parent = a.getParent();

        while (!covers(sibling, b)) {
            sibling = getSibling(parent);
            parent = parent.getParent();
        }
        return parent;
    }

    private BinaryTreeNodeWithParent getSibling(BinaryTreeNodeWithParent node) {
        if (node == null || node.getParent() == null) return null;
        var parent = node.getParent();
        return node.equals(parent.getLeft()) ? node.getRight() : node.getLeft();
    }

    private boolean covers(BinaryTreeNodeWithParent root,
                           BinaryTreeNodeWithParent node) {

        if (root == null) return false;
        if (root.equals(node)) return true;
        return covers(root.getLeft(), node) || covers(root.getRight(), node);

    }
}

标签： javaalgorithmtreetime-complexityancestor

解决方案

这取决于问题的结构。

如果起始节点在一棵大树中很深，而祖先就在附近，那么第一个算法仍然需要遍历整个路径到根节点才能找到深度。第二个将通过仅检查一个小子树来成功。

另一方面，如果节点很深并且共同祖先非常靠近根，那么第一个只会遍历两条路径到根，而第二个可能会探索整个树。

请注意，通常情况下，您可以通过以空间换取速度来获得渐近更快的算法。维护一组节点。从两个起始节点以交替的步骤向上遍历，添加到集合中，直到找到一个已经存在的节点。那是共同的祖先。给定集合操作为 O(1)，该算法为 O(k)，其中 k 是从共同祖先到最远起始节点的路径长度。你不能做得更好。

Set<Node> visited = new HashSet<>();
while (a != null && b != null) {
  if (visited.contains(a)) return a;
  if (visited.contains(b)) return b;
  visited.add(a);
  visited.add(b);
  a = a.parent();
  b = b.parent();
}
while (a != null) {
  if (visited.contains(a)) return a;
  a = a.parent();
}
while (b != null) {
  if (visited.contains(b)) return b;
  b = b.parent();
}
return null;

推荐阅读