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

Question

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

解决方案一：

求出两个节点各自的深度：p,q
计算它们深度的增量
在较浅的节点设置一个指针，在较深的节点设置一个指针
将更深的节点指针向上移动增量，以便我们可以从相同的高度开始遍历
递归访问两个指针的部分节点，直到我们到达第一个共同祖先之外的相同节点

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;
    }
}

方案二：

验证两个节点 (p,q) 都存在于从根节点开始的树中
通过遍历它们的子树来验证 q 不是 p 的子节点并且 p 也不是 q 的子节点
递归检查 p 的连续父节点的子树，直到找到 q

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);

    }
}

Answer 1

这取决于问题的结构。

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

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

请注意，通常情况下，您可以通过以 space 换取速度来获得渐近更快的算法。维护一组节点。从两个起始节点交替向上遍历，添加到集合中，直到找到一个已经存在的节点。这就是共同的祖先。鉴于集合操作是 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;

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

Why does this common ancestor solution have better worst-case performance?

java

algorithm

tree

time-complexity

ancestor