[알고리즘/코딩테스트👩‍💻] Do it! 알고리즘 코딩테스트 C++ 9장 트리

교재 : Do it! 알고리즘 코딩테스트 c++ (김종관, 이지스퍼블리싱)
공부 깃허브 : https://github.com/yeonjae02/algorithmStudy_cpp

GitHub - yeonjae02/algorithmStudy_cpp: Do it! 알고리즘 코딩테스트 C++ 을 공부하며 작성한 코드 저장소

---

8.1 트리 알아보기

1) 개념

- 트리(tree) : 노드와 에지로 연결된 그래프의 특수한 형태
 

2) 특징

- 순환 구조(cycle)을 가지고 있지 않고, 1개의 루트 노드가 존재한다.
- 루트 노드를 제외한 노드는 단 한 개의 부모 노드를 가진다.
- 트리의 부분 트리 역시 트리의 모든 특징을 따른다.
 

3) 핵심이론

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드 (자식 노드가 없는 노드)
서브 트리	전체 트리에 속한 작은 트리

 
 

8.2 트라이 (trie)

1) 정의

- 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조
 

2) 핵심 이론

- 단어들을 사전의 형태로 생성한 후 트리의부모 자식 노드 관계를 이용하여 검색을 수행한다.
- 특징

• N진 트리 : 문자 종류의 개수에 따라 N이 결정된다. ex) 알파벳 : 26진 트리
• 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다.

 

3) 코드 (BOJ 14425)

#include <iostream>
using namespace std;

// BOJ 14425

class Node {
public:
	Node* next[26];
	bool isEnd;
	Node() : isEnd(false) {
		fill(next, next + 26, nullptr);
	}

	~Node() {
		for (auto& child : next)
			delete child;
	}

	void insert(const char* key) {
		if (*key == 0) isEnd = true;
		else {
			int next_index = *key - 'a';
			if (next[next_index] == nullptr)
				next[next_index] = new Node();
			next[next_index]->insert(key + 1);
		}
	}

	Node* find(const char* key) {
		if (*key == 0) return this;
		int next_index = *key - 'a';

		if (next[next_index] == nullptr)return nullptr;
		return next[next_index] -> find(key + 1);
	}
};

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

	int n, m, count=0;
	cin >> n >> m;
	Node* root = new Node();

	while (n > 0) {
		char text[501];
		cin >> text;
		root->insert(text);
		n--;
	}

	while (m > 0) {
		char text[501];
		cin >> text;
		Node* result = root->find(text);

		if (result && result->isEnd) count++;
		m--;
	}

	cout << count;
	return 0;
}

 
 

8.3 이진 트리 (binary tree)

1) 정의

- 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리
- 트리 영역에서 가장 많이 사용되는 형태
 

2) 핵심 이론

- 이진 트리의 종류

• 편향 이진 트리 : 노드들이 한쪽으로 편향돼 생성된 이진 트리
• 포화 이진 트리 : 트리의높이가모두 일정하며 리프 노드가 꽉 찬 이진 트리
• 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이채워져 있고 마지막 레벨은 왼쪽부터 채워진 트리

- 이진 트리의 순차 표현 : 배열 이용

이동 목표 노드	인덱스 연산	제약 조건 (N = 노드 개수)
루트 노드	index = 1	-
부모 노드	index /= 2	현재 노드가 루트 노드가 아님.
왼쪽 자식 노드	index *= 2	index * 2  ≤ N
오른쪽 자식 노드	index = index*2 + 1	index * 2 + 1 ≤ N

 
 

8.4 세그먼트 트리

1) 정의

- 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안한 자료구조
 

2) 핵심 이론

- 세그먼트 트리의 종류

• 구간 합
• 최대/최소 구하기

-  세그먼트 구현 단계

1. 트리 초기화하기
   • 리프 노드의 개수가 데이터의 개수(n)이상이되도록 트리 배열을 만든다.
   • 트리 배열의 크기 : 2^k*2 (k는 2^k ≥ n을 만족하는 k의 최솟값)
   • 리프 노드에 언본 데이터를 입력하는데, 이때 리프 노드의 시작 위치는 트리 배열의 인덱스 2^k이다.
   • 리프 노드를 제외한 나머지 노드의 값을 채운다. (2^k-1부터 1번 방향으로 채운다.)
2. 질의값 구하기
   • 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다.
     • 세그먼트 트리 index = 주어진 질의인덱스 + 2k -1
   • 질의값을 구하는 과정
     1. start_index % 2 == 1 : 해당 노드 선택
     2. end_index % 2 == 0 : 해당 노드 선택
     3. start_index depth 변경 : start_index = ( start_index + 1) /2 연산 수행
     4. end_index depth 변경 : end_index  = ( end_index  - 1) /2 연산 수행
     5. 1~4번을 반복하다가 start_index  < end_index가 되면 종료한다.
   • 질의에 해당하는 노드 선택 방법
     • 구간 합 : 선태괸 노드를모두더한다.
     • 최댓값 구하기 : 선택된 노드 중 MAX 값을 선택해 출력한다.
     • 최솟값 구하기 : 선택된 노드 중 MIN 값을 선택해 출력한다.
3. 데이터 업데이트하기
   • 구간 합 : 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경한다.
   • 최댓값 찾기 : 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 큰 값으로 업데이트
   • 최솟값 찾기 : 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 더 작은 값으로 업데이트

 
 

8.5 최소 공통 조상 (LCA ; lowest common ancestor)

1) 정의
- 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때처음 공통으로 만나게 되는 부모 노드
 
2) 핵심 이론
- 일반적인 최소 공통 조상 구하기

1. 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다.
2. 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춘다. 
   • 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료한다.
3. 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.
   • 이때 처음 만나는 노드가 최소 공통 조상이 된다.

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

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

1. 부모 노드 저장 배열 만들기
   • 부모 노드 배열의 정의 : P[K][N] = N번 노드와 2k번째 부모 노드의 번호
   • 부모 노드 배열의 점화식 : P[K][N] = P[K-1][P[K-1][N]]
2. 선택된 두 노드의 깊이 맞추기
   • P 배열을 이용해 기존에 한 단계씩 맞췄던 깊이를 2K 단위로 넘어가면서 맞춘다.
3.  최소 공통 조상 찾기
   1. 2k 단위로 점프하며 공통 조상을 찾는다.
   2. k값을 1씩 감소시키면서 P 배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.
   3. 최초로 달라지는 k에 대한 두 노드의 부모 노드를 찾아 이동한다.
   4. k가 0이 될 때까지 위 과정을 반복한다.
      • 반복문이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가 최소 공통 조상이 된다.
      • 반복문이 종료된 후 이동한 2개의 노드가 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 된다.