알고리즘 정리 - 트리

트리란?

- 트리는 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다.

- 나무(tree)의 형태를 뒤집은 것과 같이 생겼다.

---

트리 용어 정리

1) 루트 노드(root node): 부모가 없는 최상위 노드

2) 단말 노드(leaf node): 자식이 없는 노드

 

트리(tree)에서는 부모와 자식 관계가 성립한다.

3) 관계: 2을 값으로 가지는 노드와 4를 가지는 노드 사이의 관계

4) 깊이(depth): 루트 노드에서의 길이(length)

- 트리의 높이(height)는 루트 노드에서 가장 깊은 노드까지의 길이를 의미한다. (상단 그림의 높이는 1)

 

---

이진 트리(Binary Tree)

- 이진 트리는 최대 2개의 자식을 가질 수 있는 트리를 말한다.

 

우선순위 큐(Priority Queue)

- 우선순위에 따라서 데이터를 추출하는 자료구조, 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현한다.

- 우선순위 큐는 이진 트리(binary tree) 구조를 사용하는 것이 일반적이다.

 

포화 이진 트리(Full Binary Tree) 

- 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리다.

 

완전 이진 트리(Complete Binary Tree)

- 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리다. (오른쪽이 다 안채워져 있어도 왼쪽부터 다 채워져 있으면 ok)

---

힙(Heap)

- 힙은 완전 이진 트리 자료구조를 따른다.

- 힙(heap)은 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조다.

- 최대 힙(max heap): 값이 큰 원소부터 추출한다. / 최소 힙(min heap): 값이 작은 원소부터 추출한다.

- 힙은 원소의 삽입과 삭제를 위해 𝑂(𝑙𝑜𝑔𝑁) 의 수행 시간을 요구한다.

 

최대 힙(Max Heap)

- 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다

- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.

 

최소 힙(min heap) 

- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다. 

- 루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.