트리

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

트리 용어 정리

• 노드: 트리를 구성하는 기본 원소
  • 루트 노드(root node): 부모가 없는 최상위 노드, 하나의 트리에는 하나의 루트가 존재
    위 사진에서 A 노드
  • 단말 노드(leaf node): 자식이 없는 노드
    위 사진에서 H, I, E, F, G 노드
  • 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
    위 사진에서 A 노드는 C 노드의 부모 노드이다.
  • 자식 노드(child node):우트 노드 반대 방향으로 직접 연결된 노드
    위 사진에서 B, C 노드는 A 노드의 자식 노드이다.
  • 형제 관계: 같은 부모 노드를 갖는 노드들
    위 사진에서 F, G와 같은 관계를 갖는 노드들
• 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
• 깊이(depth): 루트 노드에서의 길이
• 길이(length): 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수
• 높이(height): 루트 노드에서 가장 깊은 노드까지의 길이

이진 트리

최대 2개의 자식을 가질 수 있는 트리

이진 트리 순회 방법

전위 순회(Preorder)

노드 -> 왼쪽 자식 -> 오른쪽 자식 순서로 방문하는 순회 방법

중위 순회(Inorder)

왼쪽 자식 -> 노드 -> 오른쪽 자식 순서로 방문하는 순회 방법

후위 순회(Postorder)

왼쪽 자식 -> 오른쪽 자식 -> 노드 순서로 방문하는 순회 방법

순회 방법	노드
전위 순회	8 3 1 6 4 7 10 14 13
중위 순회	1 3 4 6 7 8 10 13 14
후위 순회	1 4 7 6 3 13 14 10 8

우선순위 큐

우선순위에 따라서 데이터를 추출하는 자료구조

컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용한다.
우선 순위 큐는 일반적으로 힙(heap)을 이용해 구현한다.

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority queue)	가장 우선순위가 높은 데이터

우선 순위 큐는 다양한 방법으로 구현할 수 있다.
데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도는 다음과 같다.

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트 자료형	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

우선 순위 큐 구현 방법

이진 트리

이진 트리는 최대 2개까지의 자식을 가질 수 있다.

포화 이진 트리

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

완전 이진 트리

완전 이진 트리는 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리다.

높이 균형 트리

왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이 나지 않는 트리다.

힙

원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조

힙의 종류

• 최대 힙(max heap): 값이 큰 원소부터 추출한다.
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.
  • 루트 노드가 가장 크며, 값이 큰 데이터가 우선순위를 가진다.
    
• 최소 힙(min heap): 값이 작은 원소부터 추출한다.
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
  • 루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.
    힙은 원소의 삽입과 삭제를 위해

힙의 특징

1. 힙은 완전 이진 트리 자료구조를 따른다.
2. 힙에서는 우선순위가 높은 노드가 루트에 위치한다.

힙의 시간 복잡도

힙은 원소의 삽입과 삭제를 위해 0(logN)의 수행 시간을 요구한다.
단순한 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이 경우 시간 복잡도는 0(NogN)이다.

힙 자바스크립트 라이브러리

https://github.com/ndb796/priorityqueuejs
index.is 소스 코드를 가져온 뒤에 다음과 같이 사용할 수 있다

최대힙 사용 예시

let pq = new PriorityQueue(function(a, b) {
	return a.cash - b.cash;
});
pa.enq({cash: 250, name: 'Doohyun Kim'});
pa.enq({cash: 300, name: 'Gildong Hong'});
pa.enq({cash: 150, name: 'Minchul Han'});
console.log(pq.size()); // 3
console.log(pa.deq()); // {cash: 300, name: 'Gildong Hong'}
console.log(pa.peek()); // {cash: 250, name: 'Doohyun Kim'}
console.log(pq.size()); // 2

절대값 힙 사용 예시

let pq = new PriorityQueue(function (a, b) {
  if (Math.abs(a) === Math.abs(b)) {
    return b - a;
  } else if (Math.abs(a) > Math.abs(b)) {
    return -1;
  } else {
    return 1;
  }
});

참고 사이트

1. https://velog.io/@roro/자료구조알고리즘-트리-힙#1-2-순서-트리-탐색
2. https://code-lab1.tistory.com/8
3. https://namu.wiki/w/트리(그래프)
4. https://code-lab1.tistory.com/12