ETC./Data Structure

10 우선순위 큐

10.1 우선순위 큐 도로에서 사이렌을 울리는 구급차나 소방차가 일반 승용차보다 우선순위가 높은 것처럼, 컴퓨터에서도 우선순위의 개념이 필요할 때가 있다. 예를 들어 네트워크 패킷 중에서 네트워크 관리와 관련된 패킷은 다른 것들보다 우선순위를 가진다. 따라서 자료구조에서도 이러한 우선순위를 지원할 필요가 있다. 우선순위 큐Priority Queue는 이런 우선순위의 개념을 도입한 자료구조로, 마치 FIFO 원칙을 따르는 큐처럼, 우선순위를 가진 데이터들 중 높은 순 먼저 출력한다. 다양한 방법으로 구현이 가능하지만 가자 효율적인 구조는 힙heap이다. 따라서 우선순위 큐를 힙 트리Heap Tree라고도 부른다. 우선순위 큐 추상 자료형 우선순위 큐는 우선순위 값을 가진 요소들의 모임이다. 역시 요소의 삽..

09 이진 탐색 트리

9.1 이진 탐색 트리 자료구조의 관점에서 탐색search은 자료구조의 중요한 응용 분야 중 하나로 탐색을 위해 특화된 이진트리인 이진 탐색 트리에 대해 알아보자. 탐색 탐색은 레코드record의 집합에서 특정 레코드를 찾아내는 것으로, 레코드들의 집합을 테이블table이라고 한다. 즉 테이블에서 특정한 레코드를 찾는 것이 탐색이다. 레코드는 1개 이상의 필드field로 구성된다. 예를 들어, '학생'에 관한 레코드는 이름, 학번, 학과 등의 필드로 구성된다. 레코드들은 보통 키key라고 불리는 하나의 필드에 의해 구별된다. 키는 서로 중복되지 않는 고유한 값을 가지며 이 키를 사용해 레코드들을 구별할 수 있다. 이 키를 주요키primary key라고 부르며 탐색은 입력된 어떤 키를 사용해 레코드를 찾는..

08 트리

8.1 트리의 개념 스택, 큐, 리스트는 모두 자료들이 일렬로 나열된 형태인 선형 자료구조linear data structure이다. 하지만 자료들이 계층 구조를 가지고 있다면? 컴퓨터 폴더 구조나 가계도, 조직도 등의 자료를 표현하고 싶을 땐 선형 구조로는 충분하지 않다. 이렇게 계층적 구조hierarchical structure를 표현하는 데 이용되는 자료구조가 트리tree이다. 트리의 용어 트리의 구성 요소에 해당하는 A, B, C, ..., K, L을 노드node라고 한다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 계층 구조에서 가장 위에 있는 노드를 루트 노드root node라고 한다. 위의 그림 8.1에서의 루트 노드는 A이다. 루트를 뺀 나머지 노드들은 서브트리subtree라고 ..