[Do it! 알고리즘 코딩테스트 with C++] 7장. 트리

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 7장. 트리

7-1. 트리
7-2. 이진 트리
7-3. 세그먼트 트리
7-4. LCA

---

📌 7-1. 이진 트리

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

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

---

📌 7-2. 이진 트리

* 이진 트리
- 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리

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

* 이진 트리의 순차 표현
- 배열이 가장 직관적이면서 편리한 트리 자료구조 형태다.
- 0번째 index는 사용하지 않는다.
- 루트 노드 index: 1
- 부모 노드 index: ci / 2
- 왼쪽 자식 노드 index: 2 * pi + 0
- 오른쪽 자식 노드 index: 2 * pi + 1

---

📌 7-3. 세그먼트 트리

* 세그먼트 트리 (인덱스 트리)
- 주어진 데이터의 쿼리(구간 합 or 최대, 최소값)와 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 형태

* 세그먼트 트리 종류
- 구간 합 구하기
- 최대, 최소 구하기

* 세그먼트 트리 동작 원리
1. 트리 초기화 - 트리 배열 크기 = 2^k * 2 (2^k >= N), 리프 노드 = 원본 데이터 배열 (시작 index = 2^k)
2. 세그먼트 트리 구성
- 구간 합: A[N] = A[2N] + A[2N + 1]
- 최대: A[N] = max(A[2N], A[2N + 1])
- 최소: A[N] = min(A[2N], A[2N + 1])
3. 질의 인덱스를 세그먼트 트리 인덱스로 변경 - 질의 index + 2^k - 1
4. 질의값 구하기 (주어진 범위에서 값 구하기)
4-a. start_index % 2 == 1일 때 해당 노드 선택
4-b. end_index % 2 == 0일 때 해당 노드 선택
4-c. start_index depth 변경: start_index = (start_index + 1) / 2 연산 실행
4-d. end_index depth 변경: end_index = (end_index - 1) / 2 연산 실행
4-e. a~d를 반복하다가 end_index < start_index가 되면 종료 - 선택된 노드들의 최종 값 도출
5. 데이터 업데이트하기 - 해당 노드와 쌍이되는 자식 노드와 업데이트 -> 부모 노드 -> 루트 노드까지 업데이트

---

📌 7-4. LCA

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

* 일반적인 LCA 동작 원리 - 트리의 높이가 크지 않을 때
1. 루트 노드에서 탐색(DFS or BFS) 시작 -> 모든 노드의 부모 노드와 깊이 저장
2. 두 노드의 깊이가 서로 다른 경우 더 깊은 노드의 노드를 부모 노드로 1개씩 올리는 것을 반복
3. 두 노드가 같을 때(= 최소 공통 조상) 탐색 종료
4. 두 노드가 같지 않고 깊이가 서로 같은 경우 두 노드를 부모 노드로 1개씩 올리는 것을 반복
5. 두 노드가 같을 때(= 최소 공통 조상) 탐색 종료

* 빠르게 찾는(최적화된) LCA 동작 원리 - 2^K칸씩 올라가는 방식, 동적 계획법 사용
1. 부모 노드 저장 행렬 생성
1-a. P[K][N] = N번 노드의 2^K번째 부모의 노드 번호
1-b. 점화식 P[K][N] = P[K - 1][P[K - 1][N]]
1-c. K는 트리의 깊이 > 2^K를 만족하는 최대값
2. 두 노드의 깊이 맞추기 - 둘의 깊이 차이 2^K 만큼 한 번 점프
3. P[K][A] != P[K][B] 인 K 값을 찾을 때까지 1씩 감소 - 찾으면 위로 이동, K가 0이 될때까지 반복
4. K가 0이 되었을 때 같은 노드면 해당 노드가 최소 공통 조상, 다르면 바로 위 노드가 최소 공통 조상

---