LCA(Lowest Common Ancestor)

LCA(Lowest Common Ancestor)란, 트리 상에서 두 노드의 가장 가까운 공통 조상 노드를 의미합니다. 이를 구하는 방법으로는 여러가지가 있지만, 가장 일반적인 방법은 최소 공통 조상을 찾는 알고리즘 중 하나인 Tarjan's off-line algorithm을 이용하는 방법입니다.

Tarjan's off-line algorithm은 DFS(Depth-First Search)를 이용하여 각 노드의 부모 노드와 깊이(depth)를 구하고, 두 노드의 깊이가 같아질 때까지 각 노드를 끌어 올리며 공통 조상을 찾는 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O(N+Q)로, N은 노드의 개수, Q는 쿼리의 개수입니다.

 

LCA using Tarjan's algorithm ( with Javascript )

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class LCA {
  constructor(root) {
    this.parent = new Map();
    this.visited = new Set();
    this.dsu = new Map();
    this.makeSet(root);
  }

  makeSet(node) {
    if (node) {
      this.parent.set(node, node);
      this.makeSet(node.left);
      this.makeSet(node.right);
    }
  }

  findSet(node) {
    if (node === this.parent.get(node)) {
      return node;
    }
    const p = this.findSet(this.parent.get(node));
    this.parent.set(node, p);
    return p;
  }

  unionSet(x, y) {
    const px = this.findSet(x);
    const py = this.findSet(y);
    this.parent.set(py, px);
  }

  lca(x, y) {
    this.dfs(x);
    this.dfs(y);
    return this.dsu.get(this.findSet(x));
  }

  dfs(node) {
    if (node && !this.visited.has(node)) {
      this.visited.add(node);
      this.dfs(node.left);
      this.unionSet(node, node.left);
      this.dfs(node.right);
      this.unionSet(node, node.right);
      this.dsu.set(this.findSet(node), node);
    }
  }
}

// 이진 트리 생성
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

// LCA 구하기
const lca = new LCA(root);
console.log(lca.lca(root.left.left, root.left.right.right)); // expected output: 5
console.log(lca.lca(root.left.left, root.right.left)); // expected output: 3

위 코드에서는 TreeNode 클래스를 이용해서 이진 트리를 생성하고, LCA 클래스에서는 부모 노드, 방문 여부, DSU(Dynamic Set Union)를 관리하는 변수들을 선언합니다. makeSet 메소드는 모든 노드에 대해 자신을 부모 노드로 초기화하는 함수입니다. find 메소드는 입력된 노드 x의 루트 노드를 반환하는 함수이며, 이 과정에서 경로 압축(Path Compression) 최적화 기법을 적용합니다.