섹션 7. 트리(Tree)

알고리즘/Do it! 알고리즘 코딩테스트 C++

섹션 7. 트리(Tree)

아무키 2023. 4. 2. 21:49

트리 알아보기

트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다.

Tip) 그래프의 표현으로도 tree를 표현할 수 있다.

트리의 특징

순환 구조(cycle)를 지니지 않고, 1개의 루트 노드가 존재한다.
루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
트리의 부분 트리(subtree)역시 트리의 모든 특징을 따른다.
트리에서 임의의 두 노드를 이어주는 경로는 유일하다.

트리의 핵심 이론

트리의 구성 요소

노드 : 데이터의 index와 value를 표현하는 요소

에지 : 노드와 노드의 연결 관계를 나타내는 선

루트 노드 : 트리에서 가장 상위에 존재하는 노드

부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드

자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드

리프 노드 : 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)

서브 트리 : 전체 트리에 속한 작은 트리

코딩 테스트 Tip

그래프로 푸는 트리
1. 인접리스트로 표현 가능 → DFS, BFS 이용
tree만을 위한 문제
1. 이진 트리 & index tree & LCA(Lowest Common Ancestor)
2. 1차원 배열로 tree 표현가능

이진 트리

이진 트리(binary tree)는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리이다.

트리 영역에서 가장 많이 사용되는 형태이다.

이진 트리의 핵심 이론

이진 트리의 종류

이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다.

편향 이진 트리는 노드들이 한쪽으로 편향돼 생성된 이진 트리

포화 이진 트리는 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리

완전 이진 트리는 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리

편향 이진트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다.

일반적으로 코딩 테스트에서는 완전 이진 트리 형태를 떠올리면 된다.

이진 트리의 순차 표현

트리 자료구조 형태는 배열을 주로 사용한다.

트리의 노드와 배열의 인덱스 사이의 관계

ex) 트리 순회하기 (백준 1991)

전위 순회 : (루트)(왼쪽 자식)(오른쪽자식) ABDCEFG

중위 순회 : (왼쪽자식)(루트)(오른쪽자식) DBAECFG

후위 순회 : (왼쪽자식)(오른쪽자식)(루트) DBEGFCA

문제 분석하기
1. 자료구조 형태만 충실히 구현하면 된다.
2. 트리 형태의 자료구조에 적절하게 저장
3. 그 안에서 탐색을 수행하는 로직 구현, 2차원 배열을 이용해 구현하는 방식 선택

재귀함수 이용

#include<iostream>

using namespace std;

static int n;
static int tree[26][2];

void PreOrder(int now) {
	if (now == -1) {
		return;
	}

	cout << (char)(now + 'A');

	PreOrder(tree[now][0]);
	PreOrder(tree[now][1]);
}

void InOrder(int now) {
	if (now == -1) {
		return;
	}
	
	InOrder(tree[now][0]);

	cout << (char)(now + 'A');

	InOrder(tree[now][1]);
}

void PostOrder(int now) {
	if (now == -1) {
		return;
	}

	PostOrder(tree[now][0]);
	PostOrder(tree[now][1]);

	cout << (char)(now + 'A');
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		char node_char, left, right;

		cin >> node_char >> left >> right;

		int node = node_char - 'A';

		if (left == '.') {
			tree[node][0] = -1;
		}
		else {
			tree[node][0] = left - 'A';
		}

		if (right == '.') {
			tree[node][1] = -1;
		}
		else {
			tree[node][1] = right - 'A';
		}
	}

	PreOrder(0);
	cout << "\n";
	InOrder(0);
	cout << "\n";
	PostOrder(0);
	cout << "\n";
}

세그먼트 트리(인덱스 트리)

주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태로 더 큰 범위는 ‘인덱스 트리’가 있다. 코딩 테스트 영역에서는 큰 차이가 없다.

세그먼트 트리의 핵심 이론

세그먼트 트리의 종류는 구간 합, 최대최소 구하기로 나눌 수 있고, 구현 단계는 트리 초기화하기, 질의 값 구하기(구간 합 또는 최대최소), 데이터 업데이트하기로 나눌 수 있다.

트리 초기화하기
1. 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 생성
2. 2^k ≥ N을 만족하는 k의 최소값을 구한 후 2^k * 2를 트리 배열의 크기로 정함

ex) {5, 8, 4, 3, 7, 2, 1, 6} 인경우, 2^k를 시작 인덱스로 취해 준다.

2. 질의값 구하기

세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경

세그먼트 트리 index = 주어진 질의 index + 2^k - 1

질의 값 구하는 과정

start_index % 2 == 1 일때 해당 노드를 선택
end_index % 2 == 0 일때 해당 노드를 선택
start_index depth 변경 : start_index = (start_index + 1) / 2 연산을 실행
end_index depth 변경 : end_index = (end_index - 1) / 2 연산을 실행
과정 1 ~ 4를 반복하다 end_index < start_index가 되면 종료

과정 1, 2에서 해당 노드를 선택했다는 것은 해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 때문에 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고, 해당 노드의 부모 노드는 대상 범위에서 제외한다는 뜻이다.

부모 노드를 대상 범위에서 제거하는 방법은 바로 과정 3, 4에서 질의 범위에 해당하는 부모 노드로 이동하기 위해 인덱스 연산을 index / 2 가 아닌 (index + 1) / 2, (index - 1) / 2로 수행하는 것이다.

질의에 해당하는 노드를 선택하는 방법은 구간 합, 최대값 구하기, 최소값 구하기 모두 동일하며 선택된 노드들에 관해 마지막에 연산하는 방식만 다르다.

질의에 해당하는 노드 선택 방법

구간 합 : 선택된 노드를 모두 더한다.
최대값 구하기 : 선택된 노드 중 MAX값을 선택해 출력
최솟값 구하기 : 선택된 노드 중 MIN값을 선택해 출력

ex) 2 ~ 6번째 노드의 구간 합을 구하는 경우

start = 2 + 7 = 9

end = 6 + 7 13

3. 데이터 업데이트하기

업데이트 방식은 자신의 부모 노드로 이동하면서 업데이트한다는 것 동일하다
어떤 값으로 업데이트할 것인지에 관해서는 트리 타입별로 조금씩 다르다.

세그먼트 트리 요약

1. 트리 초기화하기 = 크기 정하기 2^k ≥ n

ex) 7 2^k ≥ 7 → 2^3 x 2 = 16

2. 부모 노드 값 채우기

3. 질의 값 구하기

a. 질의 index를 트리에 맞게 변경

b. start % 2 = 1 선택

c. end % 2 = 0 선택

4. 업데이트

a. 트리의 특성을 살려 이진트리가 부모로 갈떄 / 2

데이터의 구간합을 구해야 하는데 중간 중간 데이터의 값이 변할때 인덱스 트리 사용 추천

ex) 구간 합 구하기 3 (백준 2042)

문제 분석하기
1. 중간에 수의 변경이 번번히 일어나고 부분합을 구할때는 합배열이 아닌 세그먼트 트리를 사용

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

static vector<long> tree;

void SetTree(int i) {
	while (i != 1) {
		tree[i / 2] += tree[i];
		i--;
	}
}

void ChangeValue(int index, long value) {
	long diff = value - tree[index];

	while (index > 0) {
		tree[index] = tree[index] + diff;
		index = index / 2;
	}
}

long GetSum(int s, int e) {
	long part_sum = 0;

	while (s <= e) {
		if (s % 2 == 1) {
			part_sum = part_sum + tree[s];
		}
		if (e % 2 == 0) {
			part_sum = part_sum + tree[e];
		}

		s = (s + 1) / 2;
		e = (e - 1) / 2;
	}
	return part_sum;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, k;
	cin >> n >> m >> k;

	int tree_height = 0;
	int length = n;

	while (length != 0) {
		length /= 2;
		tree_height++;
	}

	int tree_size = int(pow(2, tree_height + 1));
	int left_node_start_index = tree_size / 2;
	
	tree.resize(tree_size + 1);

	for (int i = left_node_start_index; i < left_node_start_index + n; i++) {
		cin >> tree[i];
	}

	SetTree(tree_size - 1);

	for (int i = 0; i < m + k; i++) {
		long a, s, e;

		cin >> a >> s >> e;

		if (a == 1) {
			ChangeValue(left_node_start_index - 1 + s, e);
		}
		else if (a == 2) {
			s = s + left_node_start_index - 1;
			e = e + left_node_start_index - 1;

			cout << GetSum(s, e) << "\n";
		}
	}
}

LCA 최소 공통 조상

트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할때 처음 공통으로 만나게 되는 부모 노드를 ‘최소 공통 조상(LCA : lowest common ancestor)이라고 한다.

LCA를 구하는 일반적인 방법과 빠르게 찾는 방법이 있다.

일반적인 최소 공통 조상 구하는 방법

트리의 높이가 크지 않을 때(시간 제한이 여유있을 때) 최소 고통 조상을 구하는 방법의 예시는 다음과 같다.

ex) 4번, 15번 노드의 최소 공통 조상을 구하기

루트 노드에서 탐색(BFS, DFS 사용)을 시작해 각 노드의 부모 노드와 깊이를 저장
Tip) 트리의 특징 : 바로 직전 탐색노드가 부모 노드가 된다. depth 구하기가 가능하다.

선택된 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춰준다. 이때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료

깊이가 같은 상태에서 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다. 이때 처음 만나는 노드가 최소 공통 조상이 된다.

트리의 높이가 커질 경우, 시간 제약 문제에 직면 할 수 있다.

위 문제를 해결한 ‘최소 공통 조상 빠르게 구하기’가 있다.

ex) 최소 공통 조상 구하기 1 (백준 11437)

문제 분석하기
1. 노드 개수가 50,000개로 비교적 데이터가 크지 않아 일반적인 방식의 LCA 알고리즘으로 구현
2. 인접 리스트로 트리 데이터를 구현
3. 탐색 알고리즘(DFS, BFS)을 이용해 각 노드의 깊이를 구함
4. 깊이를 맞춘후 공통 조상 찾기

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

static int n, m;
static vector<vector<int>> tree;
static vector<int> depth;
static vector<int> parent;
static vector<bool> visited;

void BFS(int node) {
	queue<int> myqueue;
	myqueue.push(node);
	visited[node] = true;

	int level = 1;
	int now_depth_size = 1;
	int now_depth_node_count = 0;

	while (!myqueue.empty()) {
		int now_node = myqueue.front();
		myqueue.pop();

		for (int next : tree[now_node]) {
			if (!visited[next]) {
				visited[next] = true;
				myqueue.push(next);
				parent[next] = now_node;
				depth[next] = level;
			}
		}
		now_depth_node_count++;

		if (now_depth_node_count == now_depth_size) {
			now_depth_node_count = 0;
			now_depth_size = myqueue.size();
			level++;
		}
	}
}

int ExecuteLCA(int a, int b) {
	if (depth[a] < depth[b]) {
		int temp = a;
		a = b;
		b = temp;
	}

	while (depth[a] != depth[b]) {
		a = parent[a];
	}

	while (a != b) {
		a = parent[a];
		b = parent[b];
	}
	return a;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	tree.resize(n + 1);
	depth.resize(n + 1);
	parent.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < n - 1; i++) {
		int s, e;
		cin >> s >> e;
		tree[s].push_back(e);
		tree[e].push_back(s);
	}

	BFS(1);

	cin >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		int LCA = ExecuteLCA(a, b);
		cout << LCA << "\n";
	}
}

최소 공통 조상 빠르게 구하기

서로의 깊이를 맞추거나 같아지는 노드를 찾을때 기존의 한 단계씩 올려 주는 방식이 아닌 2^k씩 올라가 비교하는 방법이다. 따라서 기존에 자신의 부모 노드만 저장해 놓던 방식이 아닌 2^k번째 위치의 부모 노드까지 저장해야한다.

부모 노드 저장 배열 만들기
1. 부모 노드의 배열의 정의 P[K][N] = N번 노드의 2^k번째 부모의 노드 번호
부모 노드 배열의 점화식
1. P[K][N] = P[K -1][P[K - 1][N]]
2. N의 2^3번째 부모는 N의 2^2번째 부모의 2^2번째 부모
선택된 두 노드의 깊이 맞추기
최소 공통 조상 찾기
1. 2^k 단위로 점프, k 값을 1씩 감소하면서 찾는다.
2. K가 0이 될때까지 반복, 반복문이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다.

ex) 최소 공통 조상 구하기 2 (백준 11438)

문제 분석
1. 두 노드의 가장 가까운 공통 조상이 몇번인지 구하기
2. 노드의 개수가 10만, 노드의 쌍이 10만임으로 LCA 빠르게 구하기(제곱수) 사용
3. 인접리스트로 트리 데이터 구현
4. 탐색 알고리즘(DFS, BFS)이용하여 각 노드의 깊이 구하기
5. 점화식을 이용해 Parent배열 구하기
6. 부모 노드 배열 P[K][N] = P[K - 1][P[K - 1][N]]

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

static int n, m;
static vector<vector<int>> tree;
static vector<int> depth;
static int k_max;
static int parent[21][100001];
static vector<bool> visited;

void BFS(int node) {
	queue<int> myqueue;
	myqueue.push(node);
	visited[node] = true;
	int level = 1;
	int now_size = 1;
	int count = 0;

	while (!myqueue.empty()) {
		int now_node = myqueue.front();
		myqueue.pop();

		for (int next : tree[now_node]) {
			if (!visited[next]) {
				visited[next] = true;
				myqueue.push(next);
				parent[0][next] = now_node;
				depth[next] = level;
			}
		}
		count++;

		if (count == now_size) {
			count = 0;
			now_size = myqueue.size();
			level++;
		}
	}
}

int ExecuteLCA(int a, int b) {
	if (depth[a] > depth[b]) {
		int temp = a;
		a = b;
		b = temp;
	}

	for (int k = k_max; k >= 0; k--) {
		if (pow(2, k) <= depth[b] - depth[a]) {
			b = parent[k][b];
		}
	}

	for (int k = k_max; k >= 0; k--) {
		if (parent[k][a] != parent[k][b]) {
			a = parent[k][a];
			b = parent[k][b];
		}
	}

	int LCA = a;

	if (a != b) {
		LCA = parent[0][LCA];
	}
	return LCA;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	tree.resize(n + 1);

	for (int i = 0; i < n - 1; i++) {
		int s, e;

		cin >> s >> e;
		tree[s].push_back(e);
		tree[e].push_back(s);
	}

	depth.resize(n + 1);
	visited.resize(n + 1);

	int temp = 1;
	k_max = 0;

	while (temp <= n) {
		temp <<= 1;
		k_max++;
	}

	BFS(1);

	for (int k = 1; k <= k_max; k++) {
		for (int j = 1; j <= n; j++) {
			parent[k][j] = parent[k - 1][parent[k - 1][j]];
		}
	}
	cin >> m;

	for (int i = 0; i < m; i++) {
		int a, b;

		cin >> a >> b;

		int LCA = ExecuteLCA(a, b);

		cout << LCA << "\n";
	}
}