[자료구조] Priority Queue
정의 Queue는 각 요소들 간의 우선순위(Priority)가 없이 FIFO(First In First Out, 선입선출법) 방식으로 데이터를 처리하였다. 반면, Priority Queue의 모든 요소는 로 이루어져 있다. 그리고 이 Key가 요소들 간의 우선순위를 결정한다. 가령, Priority(Key)의 값이 낮을수록 더 높은 우선순위를 부여한다고 가정하자. {, , , } 와 같은 Priority Queue가 있을 때, remove 연산을 수행하면 가장 Key 값이 낮은 가 Priority Queue에서 제거되고, {, , }가 되는 방식이다. 구현 Priority Queue를 구현하는 방식에는 다음 두 가지가 있다. 1. Unsorted List로 구현 2. Sorted List로 구현 위 두 ..
2024. 1. 17.
[자료구조] Binary Search Tree
정의 다음과 같은 조건을 만족하는 binary tree를 binary search tree(BST) 라고 한다. 1. left subtree의 element들이 root element보다 작을 것. 2. right subtree의 element들이 root element보다 클 것. 가령, 1,2,3,4,5,6,7을 위 BST로 구현하면 다음과 같이 될 것이다. 특징 1. 앞서 binary tree를 포스팅하면서 binary tree의 순회 방식에는 pre-, in- , post- order의 3 가지 형태가 있다고 했었다. 이 중 inorder traversal은 root node의 방문 순서가 중간에 오는 방식이다. (left -> root -> right node 순서로 방문) 따라서, BST를 i..
2024. 1. 12.
