🦠Cell Algorithm : Tree

스택과 큐를 공부하다가 Tree로 넘어오게 된 이유는 알고리즘 강의들을 청강만 여럿 해보다 보니 결과적으로 도달하는 개념과 실제 프로젝트나 실무에서 가장 흔하게 접하는 개념이 바로 Tree라는 것을 느끼고 덥석 Tree 알고리즘을 먼저 포스팅하게 되었다. 물론 링크드 리스트와 같은 개념들을 순차적으로 배워가면 좋겠지만 알고리즘은 큰 개념 부터 작은 개념으로 쪼개지면서 배워 나가는 것이 나에게 맞겠다는 생각이들어서 공부 순서를 뒤집었다. Tree를 공부하고 나면 BFS와 DFS를 배울 것이다.

---

Tree

트리는 노드와 엣지로 연결된 그래프의 특수한 형태로, 주요 특징은 다음과 같다. 즉, 그래프의 표현으로도 tree를 표현 할 수 있다. (따라서 우리는 Tree를 알기 위해서 그래프를 알아야 한다.)

---

트리의 특징

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

예시 이미지 1

---

트리의 구성 요소

예시 이미지2 (아래 표 예시 이미지)

용어	정의	예시
노드 (node)	트리의 구성 요소. 위치에 따라 이름이 있는 원소들	F, B, G, A, D, I, C, E, H
엣지 (edge)	노드와 노드를 연결하는 선. 트리에서는 부모 노드와 자식 노드를 연결하는 선	F-B, B-A, B-D, D-C, D-E, F-G, G-I, I-H
루트 노드 (root node)	부모가 없는 노드. 뿌리라고도 한다.	F는 루트 노드
조상 노드 (ancestor node)	어떤 노드보다 위(루트쪽)에 위치한 노드(연결된 이어야 함)	F, B, D는 E의 조상 노드/G는 E의 조상 노드가 아니다.
부모 노드 (parent node)	어떤 노드 바로 위(루트쪽)에 연결되어 있는 노드	F는 B와 G의 부모 노드
자식 노드 (child node)	어떤 노드 바로 아래에 연결되어 있는 노드	I는 G의 자식 노드
형제 노드 (sibling)	같은 부모 노드의 자식들, 자매 노드라고도 한다.	A, D는 형제 노드
후손 노드 (descendant node)	조상 노드의 반대 - 노드 보다 아래에 위치한 노드	H는 F, G, I의 후손 노드
리프 노드 (leaf node)	자식이 없는 노드, 일종의 가장자리 노드	C, E, H는 리프 노드
내부 노드 (internal node)	리프 노드를 제외한 모든 노드, 자식이 있는 노드	F, B, G, A, D, I는 내부 노드
외부 노드 (external node)	자식이 없는 노드, 리프 노드와 같은 말	C, E, H는 외부 노드
서브트리 (subtree)	특정 노드와 그 노드의 모든 후손으로 이루어진 트리	B 노드와 그 자식 A, D, C, E로 이루어진 서브트리

---

코딩테스트에서의 Tree

1. 그래프로 푸는 tree (tree는 기본적으로 Node, Edge)
   1. 그래프 : 인접리스트로 표현
   2. 탐색 알고리즘 : DFS,BFS
2. tree 만을 위한 문제
   1. 이진 트리
   2. 세그먼트 트리&LCA(or index tree / 최소 공통 조상 : 난이도가 높은 편이다.)
3. tree 만을 위한 문제를 1차원 배열로 tree 표현(예시 이미지 1 참조) 
   
   

   index	0	1	2	3	4	5	6	7
   node	x	A	B	C	D	E	-	-
   부모 node	x	x	x	A	B	B	-	-

   * 항상 부모 자식을 따지는 것이 중요하다.
   1. 부모 node로 접근 공식 : index/2
   2. 자식 node로 접근 공식 : index * 2 + 1

---

SUMMARY

• tree는 그래프를 가지고 풀수도 있고 DFS,BFS,인접리스트로도 풀수 있으며 1차원 배열을 가지고 풀 수도 있다.

---

REFERNCE

• https://m.blog.naver.com/4717010/60209552604