LCA(Lowest Common Ancestor) 알고리즘

1. LCA(Lowest Common Ancestor) 알고리즘이란? 

두 개의 노드의 가장 가까운 공통된 부모를 찾는 알고리즘을 말한다.

 

 

2. 어떻게 찾을 수 있을까? 

위의 트리에서 9와 13의 공통 부모는 둘의 바로 위에 있는 2이다. 물론 9와 13과 같이 같은 Level에 있는 노드인 경우에 두 노드의 Level을 동시에 하나씩 줄여가며 찾을 수 있겠지만 만약 서로 다른 Level에 있는 경우 동시에 거슬러 올라간다 한들 공통 부모를 찾을 수 없다. 따라서 Level이 다른 경우에는 하나의 노드를 거슬러 올라가도록 하여 같은 Level로 맞춰줘야만 한다.

정리하자면, 더 깊은 Level에 있는 노드의 Level을 줄여 얕은 Level에 있는 노드와 동일하게 맞춰줘야 한다. 

 

2.1. Level과 부모 노드 구하기

우선 위의 로직을 구현하기 위해서는 당연하게도 각 노드의 Level과 부모 노드를 구해야만 한다.  BFS를 활용하면 모든 노드의 Level과 부모 노드를 구할 수 있다.  

 

Level과 부모 노드 구하기 부분을 코드로 직접 구현해보면 다음과 같다.

    private void initialized(int[] tree) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        levels[1] = 0;
        parents[1] = 0;
        while(!queue.isEmpty()) {
            int temp = queue.poll();
            int leftNode = temp*2;
            int rightNode = temp*2+1;
            if(leftNode < tree.length) {
                queue.add(leftNode);
                levels[leftNode] = levels[temp] + 1;
                parents[leftNode] = temp;
            }

            if(rightNode < tree.length) {
                queue.add(rightNode);
                levels[rightNode] = levels[temp] + 1;
                parents[rightNode] = temp;
            }
        }
    }

2.2. LCA 메인 로직

이제 필요한 데이터들을 모두 구했으니, 메인 로직 구현만 남았다. 

우리는 위에서 확인했다시피 같은 Level에 있는 노드들의 LCA를 구하는 것이 훨씬 쉽다는 것을 알고 있다. 그렇기 때문에 가장 먼저 둘 중 깊은 Level에 위치한 노드를 골라 얕은 Level의 노드와 동일한 Level로 옮겨줘야 한다.  즉, Level이 같아질 때 까지 깊은 Level에 위치한 노드는 부모 노드를 통해 위로 거슬러 올라가야 한다.

 

 코드로 직접 구현해보자. 

    private int lca(int a, int b) {
        int aDepth = levels[a];
        int bDepth = levels[b];

        while(aDepth > bDepth) {
            a = parents[a];
            aDepth--;
        }

        while(aDepth < bDepth) {
            b = parents[b];
            bDepth--;
        }

        while(a!=b) {
            a = parents[a];
            b = parents[b];
            aDepth--;
            bDepth--;
        }

        return a;
    }