2011-05-11 97 views
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); 
} 

回答

9

好吧,讓我們開始識別這種算法最糟糕的情況。 covers從左到右搜索樹,所以如果您正在搜索的節點是最右邊的樹葉,或者它根本不在子樹中,則會出現最壞情況的行爲。此時您將訪問子樹中的所有節點,因此coversO(n),其中n是樹中節點的數量。

同樣,commonAncestor展品最壞情況下的行爲時pq的共同祖先是內心深處到樹的權利。在這種情況下,它將首先調用covers兩次,在兩種情況下獲得最差的時間行爲。然後它會再次在右邊的子樹上調用自己,這在平衡樹的情況下大小爲n/2

假設樹是平衡的,我們可以通過重複關係T(n) = T(n/2) + O(n)來描述運行時間。使用主定理,我們得到了一個平衡樹的答案T(n) = O(n)

現在,如果樹是平衡,我們可能在最壞的情況下,只有通過各1個遞歸調用減少子樹的大小,產生復發T(n) = T(n-1) + O(n)。這種重複的解決方案是T(n) = O(n^2)

雖然你可以做得比這更好。

例如,而不是簡單地確定哪個子樹包含pqcover,讓我們確定pq的整個路徑。這需要O(n)就像cover,我們只是保留更多信息。現在,平行地遍歷這些路徑並停止他們分歧的地方。這總是O(n)

如果你有從每個節點到父母的指針,你甚至可以通過產生「自下而上」的路徑來改善,給你O(log n)一個平衡樹。

請注意,這是一個時空折衷,因爲雖然您的代碼需要O(1)空間,但此算法需要用於平衡樹的O(log n)空間和一般的O(n)空間。

+0

我有問題。在你的陳述中... _let's_ _determine_ __tire_ _path_ __ _ p _ _和_ q'。 _This_ _takes_'O(n)'_just_ _like_'cover' ...不應該從根節點到節點'p'的路徑取代'O(n)'而使用'O(log n)'? – Bhaskar 2011-05-11 22:11:38

+0

@Bhaskar。假設樹大致平衡,該路徑的長度確實是'O(log n)',但是由於必須從根搜索節點,因此_finding_路徑需要'O(n)',並且它可能位於任何位置在樹中,所以你必須在最壞的情況下搜索它。如果你有從父節點到節點的指針,你確實可以通過向上遍歷在'O(log n)'中找到這條路徑。 – hammar 2011-05-11 22:16:35

0

由於hammar’s answer演示,您的算法是相當低效的,因爲許多操作重複。

我會做一個不同的方法:如果兩個給定的節點不在同一個子樹中(因此使它成爲第一個共同的祖先),我將決定從根到兩個給定節點並比較節點。從根部向下的路徑上的最後一個公共節點也是第一個共同的祖先。

下面是一個(未經測試)實現在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(); 
} 

兩個pathToNodecommonAncestor是爲O(n)。