Tree Structure 노트4 - 집합연산트리, Segment Tree

집합 연산(Set Operation)과 트리(Tree)

 

Forest = a Union of { trees }

 

집합에 필요한 연산

ㆍUnion (x, y) - 원소 y를 포함하고 있는 Si를 원소 x를 포함하는 집합 Sj와 합친다. Si는 사라지고 Sj의 크기는 커진다.

ㆍFind (x) - 원소 x가 S집합의 i번인 경우 집합의 index i를 출력. (원소를 포함한 집합을 find)

 

Directed Rooted Tree를 이용한 집합(Set)의 표현

- union(3,5), union(2,4), union(5,7), find(7), union(10,13), find(9), union(3,10)

 ③ <- ⑤ / ② <- ④ / ③ <- ⑤ <- ⑦ / ⑩ <- ⑬ / ③ <- ⑤ <- ⑦ & ③ <- ⑩ <- ⑬ 

 

간단 rule : Union(i,j) != Union(j,i)

가중치 규칙(weighted rule) : Depth가 낮은 트리를 Depth가 깊은 트리에게 매다는 rule 인듯

Collapsing rule : Union 할때가 아닌 find할때 사용./ find(x)를 한다고 가정. 첫번째로 root를 찾고, x가 달린 부분의 노드들을 하나씩 떼서 root에 붙힘. 찾기좋은 트리모양으로 만든다(짜그러트린다?). => Find 작업을 할때 전체 tree의 높이를 최대한 짧게 만들어 다음 find를 준비시킨다.

 

Segment Tree

- 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법 (데이터의 합을 가장 빠르고 간단하게 구할수 있는 자료구조)

 

배열에서 특정 구간의 합을 구하는 방법 

① 단순 배열을 이용해 Linear하게 구하기 => 데이터 개수가 N일 떄, 시간복잡도는 O(N). 속도 느림.

② 트리 구조를 이용해 구하기 => O(logN)이면 됨.

 

세그먼트 트리 순서

1. 구간 합 트리 생성 - 원래 데이터의 범위를 반씩 분할하며 그 구간의 합들을 저장하도록 초기 설정을 하는 것(반복하면 전체노드 구해짐)/ 구간 합 트리에 한해서는 인덱스 번호가 1부터 시작(1부터 시작하면 2를 곱했을때 왼쪽 자식 노드를 가리키므로 효과적)/ 데이터의 개수가 N개일 때, N보다 큰 가장 가까운 N의 제곱수를 구한 뒤에 그것의 2배까지 미리 배열의 크기를 만들어 놓아야 함.

2. 구간 합 구하는 함수 만들기 - 트리 구조라서 데이터 탐색에 들이는 시간은 항상 O(logN). 구간의 합은 범위 안에 있는 경우에 한해서만 더해줌.

3. 특정 원소의 값을 수정하는 함수 만들기 - 특정원소값 수정할때 해당 원소를 포함하는 모든 구간합 노드들을 갱신.