8

以下は、最初の共通の祖先を見つけるための私のアルゴリズムです。しかし、時間の複雑さを計算する方法がわかりません。誰か助けてもらえますか?

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    if (covers(root.left, p) && covers(root.left, q))
        return commonAncestor(root.left, p, q);
    if (covers(root.right, p) && covers(root.right, q))
        return commonAncestor(root.right, p, q);
    return root;
}
private boolean covers(Tree root, Tree p) { /* is p a child of root? */
    if (root == null) return false;
    if (root == p) return true;
    return covers(root.left, p) || covers(root.right, p);
}
4

2 に答える 2

10

では、このアルゴリズムの最悪のケースを特定することから始めましょう。coversはツリーを左から右に検索するため、検索しているノードが一番右のリーフである場合、またはサブツリーにまったく含まれていない場合、最悪のケースの動作が発生します。この時点で、サブツリー内のすべてのノードにアクセスしたことになります。O covers( n)も同様です。nはツリー内のノードの数です。

同様に、は、との最初の共通の祖先がツリーの右下にある場合に、commonAncestor最悪のケースの動作を示します。この場合、最初に2 回呼び出され、両方のケースで最悪の動作が発生します。次に、右側のサブツリーで再び自分自身を呼び出します。バランス ツリーの場合、サイズはです。pqcoversn/2

ツリーのバランスが取れていると仮定すると、再帰関係によって実行時間を記述できT(n) = T(n/2) + O(n)ます。T(n) = O(n)マスター定理を使用して、バランスの取れたツリーの答えを取得します。

ここで、ツリーのバランスが取れていない場合、最悪の場合、再帰呼び出しごとにサブツリーのサイズを 1 減らすだけで、 recurrence が生成されT(n) = T(n-1) + O(n)ます。この再発の解決策はT(n) = O(n^2).

ただし、これよりもうまくいく可能性があります。

たとえば、どのサブツリーにporqが含まれているかを単純に判断する代わりに、 andcoverへのパス全体を判断してみましょう。より多くの情報を保持しているだけです。次に、これらのパスを並行して横断し、分岐するところで停止します。これは常にです。pqO(n)coverO(n)

各ノードからその親へのポインターがある場合は、「ボトムアップ」のパスを生成することでこれを改善しO(log n)、バランスの取れたツリーを実現できます。

これは空間と時間のトレードオフであることに注意してください。コードがO(1)スペースを消費する一方で、このアルゴリズムはO(log n)バランスの取れたツリーのためにスペースをO(n)消費し、一般的にはスペースを消費します。

于 2011-05-11T12:20:32.100 に答える
0

hammar's answerが示すように、多くの操作が繰り返されるため、アルゴリズムは非常に非効率的です。

私は別のアプローチを行います: 2 つの指定されたノードが同じサブツリーにない場合 (したがって、最初の共通の祖先になる)、すべての潜在的なルート ノードをテストする代わりに、ルートから指定された 2 つのノードへのパスを決定します。ノードを比較します。ルートから下にあるパス上の最後の共通ノードは、最初の共通祖先でもあります。

Java での (テストされていない) 実装を次に示します。

private List<Tree> pathToNode(Tree root, Tree node) {
    List<Tree> path = new LinkedList<Tree>(), tmp;

    // root is wanted node
    if (root == node) return path;

    // check if left child of root is wanted node
    if (root.left == node) {
        path.add(node);
        path.add(root.left);
        return path;
    }
    // check if right child of root is wanted node
    if (root.right == node) {
        path.add(node);
        path.add(root.right);
        return path;
    }

    // find path to node in left sub-tree
    tmp = pathToNode(root.left, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    // find path to node in right sub-tree
    tmp = pathToNode(root.right, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    return null;
}

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    List<Tree> pathToP = pathToNode(root, p),
               pathToQ = pathToNode(root, q);
    // check whether both paths exist
    if (pathToP == null || pathToQ == null) return null;
    // walk both paths in parallel until the nodes differ
    while (iterP.hasNext() && iterQ.hasNext() && iterP.next() == iterQ.next());
    // return the previous matching node
    return iterP.previous();
}

pathToNodeとの両方commonAncestorが O(n) にあります。

于 2011-05-11T13:39:23.880 に答える