알고리즘 정리 - 트리
트리란?
- 트리는 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다.
- 나무(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)
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
- 루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.