트리(Tree)
- 트리는 계층적인 구조를 표현할 때 사용하는 자료구조
- 나무를 뒤집은 것과 같이 생겼다.
트리 용어 정리
- 루트 노트 (root node) : 부모가 없는 최상위 노드
- 단말 노드 (leaf node) : 자식이 없는 노드
- 깊이 (depth) : 루트 노드에서의 길이(length)
- 길이 : 출발 노드에서 목적지 노드까지 거쳐야하는 간선의 수
- 높이 : 루트에서부터 가장 깊은 노드까지의 길이
이진 트리 (Binary Tree)
- 이진 트리는 최대 2개의 자식을 가질 수 있는 트리
- 포화 이진 트리 (Full Binary Tree)는 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 이진 트리
- 완전 이진 트리 (Complete Binary Tree)는 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리이다.
- 높이 균형 트리 (Height Balanced Tree)는 왼쪽/오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리이다.
우선순위 큐(Priority Queue)
- 우선순위에 따라 데이터를 추출하는 자료구조
- 일반적으로 힙(트리를 이용해 구현)을 이용해 구현한다.
우선순위 큐 구현 방법 별 시간 복잡도
리스트 자료형 : 삽입 시간 O(1), 삭제 시간 O(N)
힙 : 삽입 시간 O(logN), 삭제 시간 O(logN)
때문에 힙을 이용해서 삽입, 삭제 시간을 logN으로 보장하는 구조를 사용한다.
힙(Heap)
- 원소중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
- 최대/최소 힙은 각각 값이 크거나 작은 원소부터 추출
- 삽입/삭제 O(logN)
- 단순히 N개 데이터를 힙에 삽입했다가 모두 꺼내는 것이 정렬과 동일하다. 이는 O(NlogN)
- 완전 이진 트리 구조를 가진다.
- 우선 순위가 높은 노드가 루트에 위치한다.
최대 힙 (Max Heap)
- 루트 노드가 전체 트리에서 가장 큰 값을 가지는 완전 이진 트리 구조
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.
최소 힙 (Min Heap)
- 루트 노드가 전체 트리에서 가장 작은 값을 가지는 완전 이진 트리 구조
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
최소 힙 구성 함수 : Heapify
상향식으로 부모를 거슬러 올라가며, 부모보다 자신이 더 작은 경우 위치를 교체한다.
JS의 힙 라이브러리
- 별도의 우선순위 큐를 라이브러리로 제공하지 않기 때문에 최단 경로 알고리즘 등에서 힙이 필요한 경우 별도의 라이브러리를 사용해야 한다.
https://github.com/ndb796/priorityqueuejs
index.js 소스 코드
그래프 (Graph)
- 사물을 정점(vertex), 간선(edge)으로 나타내기 위한 도구
- 노드간 접근에 비용(가중치)가 있을 수 있다.
그래프의 표현 방법은 두 가지 방식이 있다.
인접 행렬 (adjacency matrix)
- 2차원 배열을 사용하는 방식이다.
1. 무방향 무가중치 그래프
- 모든 간선이 방향성이 없고 모든 간선에 비용(가중치)이 없는 그래프
- 인접 행렬로 출력할 수 있다.
2. 방향 가중치 그래프
- 모든 간선이 방향성과 가중치가 있는 그래프
- 인접 행렬로 출력할 수 있다.
인접 리스트(adjacency list)
- 연결 리스트를 사용하는 방식
(0번 노드에선 1, 2번 노드를 갈 수 있으며 비용은 각각 3, 7과 같이 해석)
1. 무방향 무가중치 그래프
- 모든 간선이 방향성이 없고 모든 간선에 비용(가중치)이 없는 그래프
- 인접 리스트로 출력할 수 있다.
2. 방향 가중치 그래프
- 모든 간선이 방향성과 가중치가 있는 그래프
- 인접 리스트로 출력할 수 있다.
**
그래프의 시간 복잡도
- 인접 행렬 : 모든 정점들의 연결 여부를 저장하여 O(V^2)의 공간 복잡도를 요구하지만 연결 여부를 조회할 경우 O(1)에 확인할 수 있다.
- 인접 리스트 : 연결된 간선의 정보만을 저장하여 O(V + E)의 공간을 요고하지만 두 노드의 연결 여부를 확인하기 위해 O(V)의 시간이 필요하다.
최단 경로 알고리즘에서의 그래프
- 최단 경로 알고리즘을 구현할 때는 각각 근처의 노드와 연결되어 있는 경우가 많으므로 간선의 갯수가 적어 인접 리스트가 유리하다.
Hello World !