[Javascript] 자료구조 - 트리(Tree), 우선순위 큐(Priority Queue)

트리(Tree) : 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조

 

트리 용어 정리

• 루트 노드(root node) : 부모가 없는 최상위 노드
• 단말 노드(leaf node) : 자식이 없는 노드
• 트리에서는 부모와 자식 관계가 성립
• 형제관계가 존재 - 루트 또는 부모가 같을때 같은 층에 존재하는 노드와의 관계
• 깊이(depth) : 루트 노드에서의 길이
  길이 : 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수
• 트리의 높이(height)는 루트 노드에서 가장 깊은 노드까지의 길이

 

이진 트리(Binary Tree)

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

 

포화 이진 트리(Full Binary Tree)

- 리프 노드를 제외한 모든 노드가 두 자식을 가진 트리

 

완전 이진 트리(Complete Binary Tree)

- 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리

 

높이 균형 트리(Height Balanced Tree)

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

 

우선순위 큐(Priority Queue)

• 우선순위 큐는 우선순위에 따라서 데이터를 추출하는 자료구조
• 컴퓨터 운영체제, 온라인게임 매칭 등에서 활용
• 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현
• 데이터 개수가 N개일 때, 구현 방식에 따른 시간 복잡도

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

 

** 일반적인 큐는 선형적인 구조인 반면에 우선순위 큐는 이진트리 구조를 사용하는것이 일반적

 

힙(heap)

• 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
• 최대 힙(max heap) : 값이 큰 원소부터 추출, 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리
  루트 노드는 전체트리에서 가장 큰 값을 가진다.
• 최소 힙(min heap) : 값이 작은 원소부터 추출
• 힙은 원소의 삽입과 삭제를 위해 O(logN)의 수행시간을 요구
• 단순 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 - 시간 복잡도는 O(NlogN)

힙의 특징

• 완전 이진 트리 자료구조
• 우선순위가 높은 노드가 루트에 위치
• 힙의 삽입과 삭제 연산을 수행하면, 거슬러 갈 때마다 처리해야하는 범위에 포함된 원소의 개수가 절반씩 줄어든다.
• 따라서 삽입과 삭제에 대한 시간 복잡도는 O(logN)

 

1. 최대 힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.
• 루트 노드가 가장 크며, 값이 큰 데이터가 우선순위를 가진다.

 

2. 최소 힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
• 루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.

 

최소 힙 구성함수 : Heapify

• 상향식 - 부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우에 위치를 교체
• 새로운 원소가 삽입 됐을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.
• 원소가 제거 되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지
• 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
• 이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) heapify()를 진행

** Javascript 에서는 우선순위 큐를 라이브러리로 제공 X
따라서 최단 경로 알고리즘 등에서 힙이 필요한 경우 별도의 라이브러리를 사용해야한다.

https://github.com/ghd6840/priorityqueuejs <- index.js 소스 참조