이진 트리에서 노드의 첫 번째 공통 조상을 찾는 방법은 무엇입니까?

Question

다음은 첫 번째 공통 조상을 찾는 알고리즘입니다. 그러나 시간 복잡성을 계산하는 방법을 모르겠습니다. 누구든지 도와 줄 수 있습니까?

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

Answer 1

좋아, 그럼이 알고리즘의 최악의 경우를 확인해 보겠습니다. covers은 트리를 왼쪽에서 오른쪽으로 검색하므로 검색중인 노드가 맨 오른쪽 리프이거나 최하위 트리에없는 경우 최악의 경우 동작을합니다. 이 시점에서 하위 트리의 모든 노드를 방문하게되므로 covers은 O (n)입니다. 여기서 n은 트리의 노드 수입니다.

마찬가지로 commonAncestor은 p과 q의 첫 번째 공통 조상이 트리의 오른쪽에 깊숙이있을 때 최악의 경우의 동작을 보입니다. 이 경우 먼저 covers을 두 번 호출하여 두 경우 모두 최악의 시간 동작을 얻습니다. 그런 다음 올바른 하위 트리에서 자체를 다시 호출합니다. 균형 트리는 크기가 n/2입니다.

트리 균형이 있다고 가정하면 반복 관계 T(n) = T(n/2) + O(n)으로 런타임을 설명 할 수 있습니다. 마스터 정리를 사용하면 균형 트리에 대한 대답은 T(n) = O(n)입니다. 나무가 균형 하지 경우

지금, 우리는 최악의 경우에만 재발 T(n) = T(n-1) + O(n)를 산출, 각 재귀 호출에 대해 1 씩 서브 트리의 크기를 줄일 수 있습니다. 이 재발에 대한 해결책은 T(n) = O(n^2)입니다.

그래도 이보다 나은 결과를 얻을 수 있습니다. 예를 들어

, 대신 단순히 하위 트리가 cover와 p 또는 q를 포함하는 결정,의는 p과 q에 전체 경로를 확인 할 수 있습니다. 이것은 O(n)을 cover과 똑같이 사용합니다. 더 많은 정보를 얻고 있습니다. 이제, 평행선에서 그 길을 가로 지르고 그들이 갈라진 곳에서 멈추십시오. 항상 O(n)입니다.

각 노드에서 상위 노드에 대한 포인터가있는 경우 "bottom-up"경로를 생성하여이 점을 향상시킬 수도 있습니다.이 경우 균형 트리에 O(log n)이 부여됩니다.

코드가 O(1)인데 반해,이 알고리즘은 균형 트리에 대해 O(log n) 공간을 사용하고 일반적으로 O(n) 공간을 사용하므로 공간 - 시간 트레이드 오프입니다.

Answer 2

hammar’s answer과 같이 알고리즘은 많은 작업이 반복 될 때 비효율적입니다.

나는 다른 접근법을 사용한다. 주어진 두 노드가 같은 하위 트리에 있지 않으면 모든 잠재적 루트 노드를 테스트하는 대신 (따라서 첫 번째 공통 조상으로 만든다) 루트로부터 경로를 결정할 것이다. 주어진 두 노드에 연결하고 노드를 비교합니다. 루트에서 아래쪽 경로의 마지막 공통 노드는 첫 번째 공통 조상입니다.

다음은 자바에서 (테스트되지 않은) 구현의 :

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)에 있습니다.