1. 트리(Tree)
: 그래프의 일종으로 정점/간선을 이용해 데이터의 배치 형태를 추상화한 자료구조
서로 다른 두 노드를 연결하는 길이가 하나뿐인 그래프로, 힙을 구현하는 방법 중 하나
👉🏻 [특징]
- 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료구조
- 구조가 ‘데이터 저장’의 의미보다는 저장된 데이터를 ‘더 효과적으로 탐색’하기 위해 사용
- 리스트와 다르게 데이터가 단순히 나열되는 구조가 아니라 부모와 자식간의 계층적인 관계로 표시된다.
- 사이클이 없고 루트 제외한 모든 노드는 단 하나의 부모 노드만 가짐
👉🏻 [순회]
1. 전위 순회(Pre-order): 루트 노드 > 왼쪽 서브트리 > 오른쪽 서브트리, 깊이 우선 순회
2. 중위 순회(In-order): 왼쪽 서브트리 > 루트 노드 > 오른쪽 서브트리, 대칭 순회
3. 후위 순회(Post-order): 왼쪽 서브트리 > 오른쪽 서브트리 > 루트 노드
1-2. 이진 트리(Binary Tree)/이진 탐색 트리(Binary Search Tree)
1. 이진 트리: 2개 이하의 자식 노드를 가지는 트리
👉🏻 [성질]
- n개의 노드를 가진 이진 트리 -> n-1개의 간선
- 높이가 h인 이진 트리 -> 최소 h, 최대 2^h-1개의 노드를 가짐
- n개의 노드를 가진 이진 트리 -> 높이 최대 n, 최소 lg(n+1)
👉🏻 [종류]
- 포화 이진 트리: 각 레벨의 노드가 꽉 차 있는 이진 트리
- 완전 이진 트리: 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리(힙이 완전 이진 트리의 일종)
- 높이가 k일 때 레벨 1~k-1까지는 모든 노드가 채워져 있고 마지막 레벨에선 꽉 차 있지 않아도 되지만 왼쪽부터 오른쪽 순서로 채워져야 함
2. 이진 탐색 트리: 탐색을 위한 이진 트리 기반의 자료구조
👉🏻 [특징]
- left node < 부모 노드
- 부모 노드<=right node
- 모든 노드는 중복된 값을 가지지 않는다
- 원하는 값을 찾을 때까지 현재 노드값보다 찾고자 하는 값이 작으면 왼쪽, 크면 오른쪽으로 움직이며 더 빠르게 찾을 수 있게 됨
1-3. 신장 트리(Spanning Tree)
: 연결 그래프의 부분 그래프로, 그래프의 모든 정점을 포함
- 정점 간 서로 연결이 되어있어야 함 (n개 정점의 그래프의 신장 트리는 n-1개의 간선)
- 사이클이 존재하지 않는 그래프
- 연결 그래프에서 신장 트리는 1개가 아닌 다수일 수 있음
-> 위와 같은 조건을 만족하는 그래프가 신장 트리
1-4. 최소 신장 트리(MST - Minimum Cost Spanning Tree)
: 트리를 구성하는 간선들의 가중치를 합한 값이 최소가 되는 신장 트리(가중치 무방향 그래프일 때 구할 수 있음)
👉🏻 MST 구하는 방법: Kruskal, Prim
1. Kruskal: 탐욕법(Greedy Method: 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만 쫒아 해답에 도달하는 방법) 사용
[과정]
1. 간선들을 가중치의 오름차순으로 정렬
2. 정렬된 간선들을 하나씩 선택하되, 사이클을 형성하지 않는 간선만 선택(Union-Find 알고리즘)
3. 해당 간선을 현재 MST 집합에 추가
- Prim: 시작 노드에서부터 출발해 신장 트리 집합을 단계적으로 확장해 나가는 방법
[과정]
1. 시작 노드를 MST 집합에 추가
2. 앞 단계에서 만들어진 집합에 인접한 노드들 중 최소 간선으로 연결된 노드를 선택해 트리 확장
3. 위 과정을 트리가 (n-1)개의 간선을 가질 때까지 반복
