우선순위 큐(Priority Queue) : 가장 높은 우선순위를 가진 항목에 접근과 삭제, 임의의 우선순위를 가진 항목 삽입을 지원하는 자료구조이다. 큐(Queue)라고 함은 먼저 들어오는 데이터가 먼저 나가는 자료구조인데, 앞에 우선순위가 붙어서 먼저 들어오는 데이터가 아닌 우선순위가 높은 데이터가 먼저나가는 구조인것이다. 힙(Heap)이란 우선순위 큐를 위해서 고안된 완전이진트리 형태의 자료구조이다. 또한 부모의 우선순위가 자식의 우선순위 보다 크다는 특징을 가지고 있어 우선 순위 큐를 구현하는데 힙을 주로 사용한다. 힙의 종류는 두가지가 있다. 최소 힙(Minimum Heap) : 키가 작을수록 높은 우선순위 Key(부모노드) < Key(자식 노드) 최대 힙(Maximum Heap) : 키가 클 ..
해시 테이블 트리 자료구조를 사용하여 삽입과 삭제 연산 시 수행 시간은 최소 O(logn)이 나오는데,(이 경우는 AVL 트리) 이보다 빠른 연산 속도를 위해 제시된 방법이 바로 해시 테이블이다. 해시 테이블은 키와 1차원 배열의 인덱스의 관계를 이용해 키(항목)을 지정한다. 키를 배열의 인덱스로 그냥 사용하면 되지 않냐고 할 수 있지만, 아래 예시처럼 키는 숫자가 아닌 일련의 문자열일 수 있다. 그렇기에 메모리 낭비를 줄이기 위해 우리는 해시 테이블을 사용한다. 해싱 : 키를 해시 함수를 사용해 변환한 해시 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 말한다. 용어 정리를 한번 해보자면, 해시 함수는 키들을 테이블의 인덱스로 변환하는 함수인데, 이때 가장 이상적인 해시 함수는 키들을 균등하게 인..
2-3 트리 2-3 트리 정의 2-3 트리는 내부 노드의 차수가 2 또는 3인 균형 탐색 트리 차수가 2인 노드는 2-노드라고 부르고, 차수가 3인 노드는 3-노드라고 부른다. 2-노드는 1개의 키를 가지며, 3-노드는 2개의 키를 가진다. 2-3 트리는 루트로부터 각 이파리까지 경로의 길이가 같고, 모든 이파리가 같은 층에 있는 완전 균형 트리이다. 2-3 트리가 2-노드들로만 구성되면 포화 이진 트리와 동일한 형태를 가진다. 2-3 트리에서 중위 순회를 수행하면 키들이 정렬된다. 2-3 트리의 연산 탐색 연산 루트에서 시작하여 방문한 노드의 키들과 탐색하는 키를 비교하며 다음 레벨의 노드를 탐색한다. 삽입 연산 먼저, 탐색과 같은 과정을 거쳐 새로운 키가 삽입될 이파리를 찾아야 한다. 이파리를 찾았다..
