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

👉 트리(Tree)

• 트리는 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조
• 나무(tree)의 형태를 뒤집은 것과 같이 생김
• 루트 노드 (root node) : 부모가 없는 최상위 노드
• 단말 노드 (leaf node): 자식이 없는 노드
• 트리에서는 부모와 자식 관계가 성립한다.
• 형제 관계: 5 값을 가지는 노드와 23 값을 가지는 노드사이의 관계

• 깊이(depth): 루트 노드에서의 길이(length)
• 이때 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수를 의미
• 트리의 높이(height)는 루트 노드에서 가장 깊은 노드까지의 길이를 의미

 

👉 이진 트리(Binary Tree)

• 이진 트리는 최대 2개의 자식을 가질 수 있는 트리를 말함

👉 우선순위 큐(Priority Queue)

• 우선순위에 따라서 데이터를 추출하는 자료구조
• 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현
• 컴퓨터 운영체제, 온라임 게임 매칭 등에서 활용

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

 

• 우선순위 큐는 다양한 방법으로 구현 가능

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

 

• 일반적인 형태의 큐는 선형적인 구조
• 반면에 우선순위 큐는 이진트리 (binary queue)구조를 사용함 (비선형적인 자료구조)

👉 포화 이진 트리(Full Binary Tree)

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

👉 완전 이진 트리(Complete Binary Tree)

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

👉 높이 균형 트리(Height Balanced Tree)

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

👉 힙 (Heap)

• 힙은 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
• 최대 힙(max heap): 값이 큰 원소부터 추출
• 최소 힙(min heap): 값이 작은 원소부터 추출
• 힙은 원소의 삽입과 삭제를 위해 O(log N)의 수행시간을 요구
• 단순한 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 - O(NlogN)

👉 최대 (Max Heap)

• 최대 힙(max heap)은 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미
• 그래서 최대 힙의 루트 노드는 전체 트리 중 가장 큰 값을 가진다

 

👉 힙 (Heap)의 특징

• 힙은 완전 이진 트리 자료구조를 따른다
• 힙에서는 우선순위가 높은 노드가 루트(root)에 위치한다
• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다
  • 루트 노드가 가장 크며, 값이 큰 데이터가 우선순위를 가진다
• 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다
  • 루트 노드가 가장 작으며,값이 작은 데이터가 우선순위를 가진다

👉 최소 힙 구성 함수 : Heapify

• 힙에 새로운 원소가 삽입될 때
  • (상향식) 부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우에 위치를 교체
  • 새로운 원소가 삽입되었을 때 O(log N)의 시간 복잡도로 힙 성질을 유지 

• 힙에 새로운 원소가 삭제될 때 (1) 
  • 원소가 제거됐을 때 O(log N)의 시간 복잡도로 힙 성질을 유지할 수 있음
  • 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록함
  • 루트 노드를 삭제하고 마지막 노드가 루트 노드의 위치에 옴

• 힙에 새로운 원소가 삭제될 때 (2)
  • 원소가 제거되었을 때 힙 성질을 유지하도록 함
  • 이후 루트 노드에서 하향식으로(더 작은 자식 노드로) heapify()를 진행함

👉 힙(Heap)의 특징

• 힙의 삽입과 삭제 연산을 수행할 때를 고려해보자
• 직관적으로, 거슬러 갈 때마다 처리해야 하는 범위에 포함된 원소의 개수가 절반씩 줄어든다
• 따라서 삽입과 삭제에 대한 시간 복잡도는 O(logN)이다 

 

 

우선순위 큐 라이브러리

var PriorityQueue = require('priorityqueuejs');

var queue = new PriorityQueue(function(a, b) {
  return a.cash - b.cash;
});

queue.enq({ cash: 250, name: 'Valentina' });
queue.enq({ cash: 300, name: 'Jano' });
queue.enq({ cash: 150, name: 'Fran' });
queue.size(); // 3
queue.peek(); // { cash: 300, name: 'Jano' }
queue.deq(); // { cash: 300, name: 'Jano' }
queue.size(); // 2

https://github.com/ndb796/priorityqueuejs/tree/master

GitHub - ndb796/priorityqueuejs: A simple priority queue data structure for Node.js

 

 

 

출처: https://fastcampus.co.kr/dev_online_upjscodingtest

JavaScript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스