[종만북] 24장 구간 트리✍

알고리즘 문제 해결 전략

목록 보기

10/13

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

트리 위에서 두 노드간의 경로 길이를 계산하는 문제
-> 트리에서 두 노드의 최소 공통 조상(lowest common ancestor, LCA)를 찾는 문제와 밀접하다
트리에서 두 노드 u, v의 최소 공통 조상 LCA(u, v): 두 노드를 모두 자손으로 갖는 노드 중 가장 아래 있는 노드

구간 트리는 일렬로 늘어선 배열을 처리하는 자료 구조
-> 트리를 일렬로 펴야한다
-> 트리를 전위 순회하면서 방문하는 노드들을 순서대로 늘어놓는다
(재귀 호출이 끝나고 이전 노드로 돌아오는 것도 노드를 방문하는 것으로 친다)

P = {0, 1, 2, 1, 3, 4, 3, 5, 3, 1, 0, 6, 7, 6, 0, 8, 9, 10, 9, 11, 9, 8, 12, 8, 0}
n개의 노드를 가진 트리를 일렬로 핀 경로(P)의 길이: 2n - 1
-> 트리의 간선의 개수: n-1
-> 일렬로 핀 경로는 모든 간선을 따라 내려갔다가 올라온다: 2(n-1)
-> 처음에 루트를 방문하는 것도 경로에 포함된다: 2(n-1) + 1
어떤 노드 u에서 시작해서 다른 노드 v에서 끝나는 부분 경로를 떼어냈을 때,* 이 경로가 방문하는 최상위 노드는 항상 u와 v의 최소 공통 조상이다
u와 v는 항상 LCA(u, v)의 서로 다른 서브트리에 포함되어 있다
-> u를 포함하는 서브트리에서 v를 포함하는 서브트리로 넘어가려면 항상 LCA(u,v)를 방문해야 한다
-> LCA(u,v)에서 그 부모 노드로 이 경로가 올라가면 그 전에 LCA(u,v)를 루트로 하는 서브트리를 모두 돌아본 후여야 한다
따라서, LCA 문제는 P에서 u의 위치와 v의 위치가 주어질 때, 이 구간에서 가장 상위에 있는 노드는 무엇인가를 묻는 문제이다

구간 트리를 이용하면 최소 공통 조상의 번호를 O(lgn)에 찾을 수 있다
방법 1:
모든 노드마다 해당 노드의 깊이를 depth[] 배열애 계산
-> 구간 트리에서 두 숫자 i, j를 비교할 때 depth[i]와 depth[j]를 서로 비교한다
-> 구간 내에 depth[]가 가장 작은 노드가 그 구간에서의 최상위 노드(LCA(u, v))이다
방법 2:
상위에 있는 노드일수록 더 작은 번호를 갖도록 노드의 번호를 매긴다
-> 구간 최소 질의(range minimum query, RMQ)를 위한 구간 트리를 이용한다
트리를 전위 순회 할 때, 각 서브 트리의 루트를 가장 먼저 방문한다
-> 트리를 전위 순회하면서 각 노드가 방문되는 순서대로 번호를 매기면 자식 노드의 번호가 항상 부모 노드의 번호보다 작도록 노드의 번호를 매길 수 있다